|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
10.11.2010, 23:09 | #1 |
Пользователь
Регистрация: 15.12.2009
Сообщений: 69
|
Нахождение максимального подмножества
Задали задачку на С++следующего содержания:
Дан массив натуральных чисел, найти самое большое подмножество элементов, в котором любые два элемента имеют одинаковое множество простых делителей. Нахождение всех простых делителей числа я нахожу без проблем. Беда только в том, каким способом находить это максимальное подмножество. Я так полагаю: если дан к примеру массив: 1 5 15 30 и 45 из 5 элементов. Для каждого из них: 1(1), 5(1,5), 15(1,3,5), 30(1,2,3,5), 45(1,3,5) множества простых делителей. Значит максимальное подмножество = {15 и 45}. Кроме как отсортировать массив по возрастанию в зависимости от простого делителя каждого элемента я предложить ничего не могу. Подкиньте идею поиска =( Вот что высянил = с помощью нахождения НОДа двух чисел можно определить = одинаковое ли у них множество простых делителей или нет. так можно понять у чисел 15, 45 и 55 = 3 простых делителя но вот 55 отличается тем, что отличается элементом 11 тогда как у двух впереди идущих он 3 НОД(15 и 45) = 15, одному из чисел по которому имкали НОД = значит множество простых делителей у них одно и тоже а вот при нахождении НОД(15 и 55) и НОД(45 и 55) он будет равен 5, значит множества простых делителей отличаются и такие два элемента нам не подойдут. Последний раз редактировалось Lodyr; 10.11.2010 в 23:43. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Нахождение максимального потока транспортной сети (где ошибка) | d3mon4eg | Помощь студентам | 4 | 13.06.2015 15:05 |
Нахождение максимального элемента в стрингриде.. либо в подпрограммах что то дописать.. не наю..( | Cheshire Cat | Помощь студентам | 1 | 09.11.2010 17:52 |
Нахождение максимального потока в сетях Delphi | ftp123 | Помощь студентам | 2 | 02.06.2010 07:26 |
Нахождение и вывод максимального слова в файле на СИ | Sultan237 | Помощь студентам | 5 | 05.03.2010 01:18 |
нахождение максимального элемента в дереве. Haskell | densan | Помощь студентам | 4 | 01.06.2009 13:23 |