Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.02.2014, 18:05   #1
Puhovoi
Пользователь
 
Аватар для Puhovoi
 
Регистрация: 16.10.2010
Сообщений: 47
Вопрос Поиск оптимального пересечения сотен массивов

Доброго времени суток!

Раздумываю над задачей, суть такова:

дан одномерный массив чисел, скажем, на 100 элементов. Также даны еще 1000 таких же массивов, все с разными числами на борту, разумеется.

Что необходимо - найти 8 или N элементов исходного массива, которые бы присутствовали в максимальном количестве остальных массивов.

Прошу помощи в решении задачи, пока мыслей никаких.

С уважением.
Puhovoi вне форума Ответить с цитированием
Старый 17.02.2014, 19:52   #2
009
Пользователь
 
Регистрация: 09.02.2014
Сообщений: 33
По умолчанию

диапазон чисел в массивах какой?
язык на котором собираетесь писать?
009 вне форума Ответить с цитированием
Старый 17.02.2014, 19:59   #3
Puhovoi
Пользователь
 
Аватар для Puhovoi
 
Регистрация: 16.10.2010
Сообщений: 47
По умолчанию

Диапазон - не фиксирован. На Delphi.
Puhovoi вне форума Ответить с цитированием
Старый 17.02.2014, 20:04   #4
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,431
По умолчанию

Предположу:
Сортируем исходный массив по возрастанию
Заводим массив для учета количества
Проходим по остальным массивам и ищем число бинарным поиском в исходном
Если нашли, то увеличили счетчик (наверное, имеет смысл увеличивать его только 1 раз для каждого массива, то есть ставить флаг, что такое число уже встречалось в текущем массиве)
После прохода всех массивов сортируем исходный массив по количеству встреч
Выводим необходимое количество элементов из него
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 17.02.2014, 20:25   #5
009
Пользователь
 
Регистрация: 09.02.2014
Сообщений: 33
По умолчанию

Цитата:
Сообщение от BDA Посмотреть сообщение
Предположу:
Сортируем исходный массив по возрастанию
Заводим массив для учета количества
Проходим по остальным массивам и ищем число бинарным поиском в исходном
Если нашли, то увеличили счетчик (наверное, имеет смысл увеличивать его только 1 раз для каждого массива, то есть ставить флаг, что такое число уже встречалось в текущем массиве)
После прохода всех массивов сортируем исходный массив по количеству встреч
Выводим необходимое количество элементов из него
может быть это самый быстрый способ )
Если считать, что элемент, встретившийся в одном массиве дважды и более засчитывается столько же раз, то здесь нужно рассмотреть два случая (какой быстрее):
- быстрая сортировка первого массива в 100 элементов, затем перебор 100*1000 элементов и бинарный поиск этих элементов в первом массиве
- быстрая сортировка 100*1000 элементов, затем бинарный поиск 100 элементов первого массива в отсортированном массиве [100*1000] (найдя такой элемент, вычислить сколько раз всего встречается не составит дальше труда).
Оценивать сложность приведенных алгоритмов не буду (никогда не любил, обычно практикой проверял)
009 вне форума Ответить с цитированием
Старый 17.02.2014, 20:35   #6
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,431
По умолчанию

Опять же предположу, что бинпоиск дешевле быстрой сортировки, поэтому первый вариант будет быстрее, но при правильной реализации легко протестировать оба варианта, просто написав пару циклов по-другому.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 17.02.2014, 20:57   #7
Puhovoi
Пользователь
 
Аватар для Puhovoi
 
Регистрация: 16.10.2010
Сообщений: 47
По умолчанию

Приведу пример, как в теории хочется, чтобы работало. Первая строка - исходный массив, нужно найти такие три числа, которые будут присутствовать в максимальном количестве других массивов. Т.е. перебрать все возможные комбинации, что есть, с учетом того, что исходный массив и дочерние состоят из 100+ абсолютно разных элементов.

84 51 87 23 57

94 10 88 48 32
50 44 65 60 21
37 32 34 88 10
60 94 30 18 27
27 89 78 31 14
67 23 84 51 43
32 78 98 29 96
11 69 84 51 23
30 45 91 93 29
28 10 29 56 93

Изначально думал сделать как:
- генерация NNNNN сочетаний из N чисел из исходного массива
- поиск во всех дочерних всех чисел из полученных сочетаний с записью, на какое сочетание больше всего 100%-х совпадений в дочерних массивах

Но тут случилось страшное - сочетаний для 80-элементного массива получается ровно 28.987.537.150. И это вот число сочетаний надо проверить по 1000 массивам, что крайне затруднительно. Собственно, затруднительно это еще на этапе генерации. А дочерних массивов на практике может быть и миллион.

P.s.: в приведенном выше примере всего 10 сочетаний, это еще терпимо. Вот далее уже, простите, полная задница.

Последний раз редактировалось Puhovoi; 17.02.2014 в 21:09.
Puhovoi вне форума Ответить с цитированием
Старый 17.02.2014, 23:50   #8
BDA
МегаМодератор
СуперМодератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Сообщений: 7,431
По умолчанию

Да уж, интересная задачка, нам нужен математик
Похоже, что Вы считаете некую статистику какой-то игры (чтобы найти наилучшие числа). Я угадал?
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
BDA вне форума Ответить с цитированием
Старый 18.02.2014, 00:08   #9
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 18,922
По умолчанию

Подозреваю, что для таких цифр решение задачи перебором не имеет практического смысла. В смысле время очень большое потребуется
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 18.02.2014, 00:13   #10
Puhovoi
Пользователь
 
Аватар для Puhovoi
 
Регистрация: 16.10.2010
Сообщений: 47
По умолчанию

Да уж, не для моей технической базы...

BDA, не совсем. Эта задача встала в ходе оптимизации OCR.
Puhovoi вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск оптимального пути из точки A в точку Б spirit-ua Общие вопросы Delphi 5 14.02.2014 13:36
создание списка; поиск оптимального плана estoneman Microsoft Office Excel 11 18.03.2013 20:32
Поиск оптимального решения Lamborghini Помощь студентам 4 12.10.2012 23:24
Паскаль. Поиск оптимального решения TuuuZ Помощь студентам 5 26.07.2010 16:54
Поиск оптимального решения Uchiha Общие вопросы Delphi 12 19.02.2008 23:04