Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Ammaximus
3 / 3 / 1
Регистрация: 15.01.2009
Сообщений: 26
#1

Сравнение массивов с погрешностью - C++

22.06.2011, 04:49. Просмотров 675. Ответов 6
Метки нет (Все метки)

Нужно сравнить два массива с погрешностью i, т.е. если элементы отличаются не более чем на i - они одинаковые.

Нужно рекурсивно перебрать все возможные варианты, и найти тот, при котором количество совпадающих элементов наибольшее.

Например погрешность 10

массивА 3 10
массивБ 18 12

3=12
10=18
Возможен вариант 10=12, тогда 3!=18 и его нужно отсеить.

Помогите пожалуйста с функцией
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.06.2011, 04:49     Сравнение массивов с погрешностью
Посмотрите здесь:

Сравнение массивов - C++
заданы два массива целых чисел с одинаковой размерности. Сравнить их соответствующие элементы и вывести на экран массив, составленный из...

Сравнение 2х массивов в С++ - C++
Ребята, помогите пожалуйста написать вот такую прогу: Запросить и считать два массива у пользователя (две последовательности целых чисел...

Сравнение массивов - C++
Здраствуйте, как можно сравнить два элемента buffer и asd? Вот код: char* buffer = new char ; char sas = {"123xxx"}; ...

Сравнение массивов - C++
нужно сравнить весь массив из 6 элементов ,,кроме последнего,равны ли элементы массива 0 и вывести на экран равны ,или нет.

Сравнение массивов - C++
После заполнения динамического массива числами,в моем случае 1 и 0,компилятор не производит действий,останавливает работу.Спасибо#include...

Сравнение массивов - C++
Добрый день! Не удается сравнить два массива q и с. Алгоритм шифрует по алгоритму CRC и необходимо расшифровать сообщение, но при...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 1
22.06.2011, 13:52     Сравнение массивов с погрешностью #2
Цитата Сообщение от Ammaximus Посмотреть сообщение
Нужно рекурсивно перебрать все возможные варианты, и найти тот, при котором количество совпадающих элементов наибольшее.
Как насчёт того, чтобы отсортировать оба массива и один раз всё сравнить?
Ammaximus
3 / 3 / 1
Регистрация: 15.01.2009
Сообщений: 26
22.06.2011, 14:50  [ТС]     Сравнение массивов с погрешностью #3
Пробовал, вероятность правильного сравнения составляет тогда около 70% и сильно зависит от размеров массива. Мне нужен полный перебор.

Добавлено через 26 минут
Не обязательно писать мне код, помогите хотя бы идеями
grizlik78
Эксперт С++
1903 / 1435 / 109
Регистрация: 29.05.2011
Сообщений: 2,990
23.06.2011, 11:27     Сравнение массивов с погрешностью #4
Ну, с псевдокодом идея простая.
Создаём массив индексов
C
1
idx[N] = { 0, 1, 2, ..., N-1 }; // Тут циклом, конечно. Лень :)
Далее, вычисляем очередную перестановку индексов. Думаю реализацию перестановок найти не сложно, хотя не пробовал. Я бы сам написал
Для очередной перестановки сравниваем так:
C
1
2
3
4
5
6
7
for (i = 0; i < N; ++i)
{
  if (Compare (arrayA[i], arrayB[idx[i]]))
  {
    // обрабатываем результат сравнения пары элементов
  }
}
Сложность полного перебора — факториальная.

Добавлено через 19 часов 48 минут
Вот пример, с использованием алгоритма next_permutation из STL
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
 
template <typename TYPE>
inline
bool compare(TYPE a, TYPE b, TYPE eps)
{
    return std::abs(a - b) <= eps;
}
 
using namespace std;
 
int main()
{
    int const N = 5;
    float arr1[N] = { 83, 34, 10, 51, 13 };
    float arr2[N] = { 21, 4, 60, 71.6, 43 };
    float eps = 10;
 
    vector<int> idx;
    for (size_t i = 0; i < N; ++i)
        idx.push_back(i);
    
    vector<int> idx_match(idx);
    int max_matches = 0;
    while ( next_permutation(idx.begin(), idx.end()) )
    {
        int count = 0;
        for (size_t i = 0; i < N; ++i)
            if (compare(arr1[i], arr2[idx[i]], eps))
                ++count;
        if (count > max_matches)
        {
            max_matches = count;
            copy(idx.begin(), idx.end(), idx_match.begin());
        }
    }
    cout << "Number of matches: " << max_matches << endl;
    for (size_t i = 0; i < N; ++i)
    {
        float v2 = arr2[idx_match[i]];
        cout << arr1[i] << (compare(arr1[i], v2, eps) ? " == " : " != ") << v2 << endl;
    }
 
    return 0;
}
Мне кажется, что всё-таки возможно получить эффективную реализацию на основе сортированных массивов. Просто она получится не такой тривиальной, как представляется на первый взгляд. Но уверенности нет.
Ammaximus
3 / 3 / 1
Регистрация: 15.01.2009
Сообщений: 26
24.06.2011, 20:15  [ТС]     Сравнение массивов с погрешностью #5
Количество перестановок (n!)? Я не очень понимаю как работает next_permutation, он перебирает вообще все возможные комбинации?

Смею попросить словесное описание алгоритма, т.к. не полностью понял программу, особенно участок
C++
1
2
3
4
5
        if (count > max_matches)
        {
            max_matches = count;
            copy(idx.begin(), idx.end(), idx_match.begin());
        }
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
24.06.2011, 21:15     Сравнение массивов с погрешностью #6
Ammaximus, Полный перебор намного медленнее чем рекурсивно перебрать все возможные варианты на отсортированных массивах.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.06.2011, 19:22     Сравнение массивов с погрешностью
Еще ссылки по теме:

Сравнение 2х массивов за 1 просмотр - C++
Доброго времени суток, уважаемые форумчане:) Будьте любезны, подскажите как решить задачку. Никак не могу понять как это можно сделать...

Сравнение двух массивов - C++
что не так,, введеный массив должен быть равен заданому,.. #include &lt;iostream.h&gt; int main() { int arr; int i=0; int...

Сравнение 2-ух char массивов - C++
Помогите. Имеется 2 char массива. Один содержит слово вводимое пользователем, а второй это же слово, только наоборот. Необходимо сравнить...

Сравнение числовых массивов - C++
Есть два числовых массива в одном 4 элемента в другом 5 (то есть разное количество) Как с помощью C++ можно сравнить эти массивы Нужно...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт С++
1903 / 1435 / 109
Регистрация: 29.05.2011
Сообщений: 2,990
25.06.2011, 19:22     Сравнение массивов с погрешностью #7
Цитата Сообщение от Ammaximus Посмотреть сообщение
Количество перестановок (n!)? Я не очень понимаю как работает next_permutation, он перебирает вообще все возможные комбинации?
Да, количество перестановок именно факториал от количества чисел (так как они все разные). Если начинать с упорядоченного по возрастанию массива, то next_permutation() будет перебирать все возможные перестановки, пока массив снова не станет упорядоченным (в этом случае алгоритм возвращает ложь).


Цитата Сообщение от Ammaximus Посмотреть сообщение
Смею попросить словесное описание алгоритма, т.к. не полностью понял программу, особенно участок
C++
1
2
3
4
5
if (count > max_matches)
{
    max_matches = count;
    copy(idx.begin(), idx.end(), idx_match.begin());
}
В этом участке просто запоминается комбинация, с которой совпадений оказалось больше, чем предыдущий максимум. То есть содержимое массива idx копируется целиком в массив idx_match. Ну и, соответственно, запоминается новый максимум.

Добавлено через 21 час 41 минуту
В вышеприведённой программе у меня есть небольшая ошибка: комбинация для исходного порядка пропускается. Цикл по комбинациям while {...} надо заменить циклом do {...} while с тем же условием.
Yandex
Объявления
25.06.2011, 19:22     Сравнение массивов с погрешностью
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru