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

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

Восстановить пароль Регистрация
 
Ammaximus
3 / 3 / 1
Регистрация: 15.01.2009
Сообщений: 26
22.06.2011, 04:49     Сравнение массивов с погрешностью #1
Нужно сравнить два массива с погрешностью 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++
C++ сравнение массивов
сравнение массивов C++
Сравнение 2х массивов в С++ C++
C++ Сравнение массивов: найти максимальное перебором массивов
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2769 / 1582 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 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
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
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++
 Аватар для valeriikozlov
4660 / 2486 / 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     Сравнение массивов с погрешностью
Еще ссылки по теме:

C++ Сравнение массивов
Сравнение двух массивов C++
Сравнение массивов C++

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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
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     Сравнение массивов с погрешностью
Ответ Создать тему
Опции темы

Текущее время: 03:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru