|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
19.11.2010, 20:16 | #1 |
Пользователь
Регистрация: 15.12.2009
Сообщений: 69
|
Поиск подмножества
Доброго времени суток!
Помогите с решением задачи: Найти в массиве натуральных чисел самое большое подмножество элементов, в котором любые два элемента имеют одинаковое множество простых делителей. Код:
5 25 125 678 12 то в конце правильно выводит 5 25 и 125 но вот если 5 12 45 55 144 = выдать должен 12 и 144 а так выдает заковырестое число... Многие советуют алгоритм перебора всех сочетаний = можно узнать про него? Последний раз редактировалось Lodyr; 19.11.2010 в 20:22. |
19.11.2010, 21:20 | #2 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Найти для каждого числа количество простых делителей, и взять все числа с тем количеством, которое встречается больше всего раз. Тогда сложность будет порядка О(N*maxN^(1/3)), а не О(2^N), как при переборе сочетаний (если правильно понял относительно сочетаний, то эта идея "подвиснет" уже при 25 числах, а при 50 числах не выполнится и за год)...
Последний раз редактировалось LeBron; 19.11.2010 в 23:37. |
20.11.2010, 15:05 | #3 |
Пользователь
Регистрация: 15.12.2009
Сообщений: 69
|
а что если у нас в массиве каждое число имеет одинаковое количество простых делителей
например 45 55 15 135 3 3 3 3 должен выдать 45 55 135 и что делать в таком случае? |
20.11.2010, 19:14 | #4 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
Тогда действительно перебор сочетаний - самый очевидный вариант. Не факт, что самый быстрый, но быстрее с ходу не придумать. Суть перебора - просматриваем все числа от 1 до 2^N-1, и для каждого числа формируем проверяемый набор за таким принципом: если в числе на итой позиции в двоичной записи единица, то берем итый элемент, иначе - не берем. Проверяем набор, если подходит - значит подходит, иначе - не судьба. Среди всех подходящих выбираем максимальный. |
|
20.11.2010, 19:17 | #5 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Можно быстрее, придумал)
Можно "сливать в блоки"... Берем первое число... Ищем все "подходящие". Если числа подходят к первому, то они подходят и между собой (если я правильно понял задание). Получаем максимальный набор с первым числом. Далее аналогично для остальных. Сложность такая же, как в моем первом варианте - О(N*maxN^(1/3)), если предположить, что числа достаточно большие относительно их количества. |
20.11.2010, 21:53 | #6 |
Пользователь
Регистрация: 15.12.2009
Сообщений: 69
|
а можно посмотреть как это все будет выглядеть в коде?
вы предлогаете сравнивать 1 со всеми последующими = найдем все подходящие = сформируем первое стартовое множество = вдруг остальные комбинации не подойдут... а дальше то как делать? посмотрел тут варианты = для трех элементов нужно 5 сравнений, для 4 более 15... у меня такое предложение = если у меня два элемента с одинаковым множеством стоят рядом = то не проблема = все находит пусть даны числа 5 12 15 30 60 для них кол-во прост делит 2 3 3 4 4 берем первыую пару 2 и 3 = они неравны = идем дальше, 3 и 3= одинаковы ищем НОД(12 и 15) если он неравен ни одному из чисел (ни 12 и ни 15) - то и их множества разные, соответственно наоборот если равен 12 или 15 - то точняк множества одинаковы и их берем за наше подмножество но в нашем случае это не так поэтому переходим к следующей паре потом дальше 3 и 4 = неравны берем другую пару 4 и 4 = подходит НОД (30 и 60) = 30 = значит их множества одинаковы = берем их за наше подмножество и все олрайт =) следующую пару ведь уже не можем взять значит на выходе 30 и 60 Но ведь нужна универсальная формула.... |
20.11.2010, 23:16 | #7 | |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Цитата:
Для 20 чисел условно 400 (на самом деле даже 200) сравнений. А если полный перебор сочетаний, то для 20 чисел будет более миллиона сравнений. Прикол с НОД не совсем катит. Допустим, есть числа 18 и 12. Их множества простых делителей одинаковые (2,3). Но НОК не равно ни 18, ни 12. |
|
21.11.2010, 17:48 | #8 |
Пользователь
Регистрация: 15.12.2009
Сообщений: 69
|
Тогда я просто не представляю как их можно сравнивать...
вся работа только на смарку |
21.11.2010, 18:26 | #9 |
Форумчанин
Регистрация: 10.10.2009
Сообщений: 680
|
Заводим, допустим, для каждого числа массивчик, в котором хранятся все его различные простые множители в порядке возростания (можно легко прикрутить это к стандартной факторизации за корень квадратный). Когда проверяем, подходят ли друг другу два числа, то достаточно проверить, равное ли у них количество делителей в наборах, и каждая ли пара в этих наборах совпадает.
|
21.11.2010, 20:42 | #10 |
Пользователь
Регистрация: 15.12.2009
Сообщений: 69
|
Я правильно поинмаю вашу идею?
Код:
Например 6 элементов 5 1 5 0 0 0 12 1 2 3 0 0 18 1 2 3 0 0 25 1 5 0 0 0 6 1 2 3 0 0 10 1 2 5 0 0 |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Нахождение максимального подмножества | Lodyr | Общие вопросы C/C++ | 0 | 10.11.2010 23:09 |
Поиск по БД | jaxik | БД в Delphi | 8 | 08.09.2010 03:41 |
поиск | spree | Microsoft Office Excel | 22 | 16.11.2009 15:08 |
Поиск | Volkogriz | Общие вопросы Delphi | 5 | 22.04.2008 10:59 |
Помогите! Множества, подмножества в Bisual C++ 6 | VBlond | Помощь студентам | 1 | 28.11.2007 20:00 |