Удаление И Сортировка Чисел В Массиве

akisha

New Member
13.10.2013
1
0
#1
Есть задачка:
Даны N положительных целых чисел, которые не делятся ни на какие простые числа, кроме 2 и 3. Требуется выкинуть минимально возможное количество чисел так, чтобы из любых двух оставшихся одно делилось на другое.
Никак не могу понять алгоритм действий(
Как можно решить эту задачку?
 

guinevra

New Member
15.10.2013
2
0
#2
Можно попробовать так: найти минимальный элемент, найти все элементы массива, на него делящиеся (не считая сам элемент, но учитывая равные ему), назначить "потомками". Далее повторять эту процедуру для "потомков". Очевидно, процесс закончится. Получится дерево, из которого нам надо оставить самую длинную ветвь.
 

Whatka

Well-Known Member
09.10.2011
428
4
#3
guinevra неплохая идея,но процесс не закончится,что возможно неочевидно)
пример: 2 3 4 9 27

то есть,если доработать,то: отсортировать массив,завести массив того же размера типа bool (все значения изначально = false)
проделать,то же,что говорилось раньше,помечая использованные хотя бы один раз числа как true
создать новое дерево для элемента с индексом,равным индексу числа в булевом массиве со значением false.


и мой вариант (тоже с деревом):
отсортировать массив и(начиная с меньшего) строить бинарное дерево по правилу:
если элемент делится на вершину,то в правое поддерево,если нет в левое,если нет
соответствующего поддерева -создать.
Найти самую глубокое правое поддерево.