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

Тема в разделе "C/C++/C#", создана пользователем akisha, 13 окт 2013.

  1. akisha

    akisha New Member

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

    guinevra New Member

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

    Whatka Well-Known Member

    Регистрация:
    9 окт 2011
    Сообщения:
    433
    Симпатии:
    4
    guinevra неплохая идея,но процесс не закончится,что возможно неочевидно)
    пример: 2 3 4 9 27

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


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

Поделиться этой страницей