0

введите сюда описание изображения

Задание:

Проложите такие маршруты от основания до вершины числовой пирамиды, чтобы суммы чисел, которые будут на каждом из них, равны соответственно 35, 45, 55.

Как я понимаю эту пирамиду нужно реализовать в форме двоичного дерева, отсортировать его, а после выбрать нужную ветку ?

7
  • 1
    Что-то навскидку ничего, кроме перебора 2^6=64 вариантов, не придумывается... Дерево в этом случае не надо: просто выбор левого пути, скажем, 0, правого - 1, вот и все...
    – Harry
    21 дек 2016 в 17:48
  • @Harry пирамиду нужно реализовать в форме двоичного дерева - не вижу запретов на движение "вбок", и даже на самопересечение. Так что не 2^6, а немножко больше. Ну и в дополнение - от вершины к основанию строить проще.
    – Akina
    21 дек 2016 в 18:06
  • @Akina по поводу реализации в формате дерева - это всего лишь мое предположение, а не условие задания.
    – Hardc0re
    21 дек 2016 в 18:08
  • Двоичное дерево тут наверное не подойдет. Поскольку иного не оговорено, то в 7 на уровне 4 (сверху, считая вершину уровнем 1) можно попасть как из 9, так и из 4 с уровня 3 (это если просматривать путь в обратном направлении). Наверное тут лучше представить данные в виде матрицы (левый нижний треугольник) и идти от вершины вниз - вправо - влево (накапливая пути в очереди), пока не достигнете основания с нужным результатом. Понятно, что перебор (и очевидный недобор) можно сразу отбрасывать.
    – avp
    21 дек 2016 в 18:11
  • 1
    @Hardc0re Будьте добры, уточните разрешенные перемещения...
    – Harry
    21 дек 2016 в 18:23

1 ответ 1

2

Используйте любой стандартный алгоритм поиска пути. Я бы использовал полный перебор и простую рекурсию. Условие окончания - текущая сумма не меньше заданной, критерий вывода - равенство текущей суммы заданной плюс текущее местоположение - основание. Схематично:

proc findpath(currentway, currentplace, currentsum)
if currentsum >= checksum then
    if currentplace.level=0 and currentsum=checksum then
        output currentway
    end if
else
    for i=0 to 5
        call findpath(currentway+currentplace, currentplace.moveto(i), currentsum+currentplace.weight)
    next i
end if
end proc
1
  • Для удобства (и упрощения) работы алгоритма пирамидальную схему надо трансформировать в треугольную матрицу с "обрамляющим контуром" (т.е. вершина имеет индекс 2,2), а "несуществующим элементам" присвоить значение не менее заданной суммы. Тогда при выходе за границу сразу наступит превышение текущей суммы и останов рекурсии без вывода текущего пути.
    – Akina
    21 дек 2016 в 18:20

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.