Задача, немного интересно :)

12
doctorpc
На сайте с 12.07.2009
Offline
112
#11

Возможно это решение уже описано в топике, но я не заметил или не понял объяснений.

Я бы сделал так:

для примера использую рисунок из 5 поста

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

Например для числа 1 из второго уровня этот массив будет выглядеть как array(21, 5), для 10 - array(11, 12), дальше подсчитываем самый верхний уровень - число 4 = array(4+21, 4+12). Здесь 21 и 12 - максимальные числа из массивов второго уровня.

Таким образом мы получили максимально возможный вариант = 25. Теперь просто нужно переписать элементы, которые в нем участвуют. Начинаем с самого верха и продвигаемся только на элемент с индексом , содержащим максимальное значение.

Путь получается такой: вершина ->0 индекс->0 индекс

Как-то так. Реализация конечно же за Вами.

IL
На сайте с 20.04.2007
Offline
418
#12
bay_ebook:
Но по факту у него слабое место - много итераций, вот и думаю как уменьшить, как вывернуться

а "много" - это сколько? Как минимум, во все вершины нужно по 1 разу "заглянуть" см. обход графа в ширину.

bay_ebook:
Не должно быть никаких ограничений на высоту пирамиды.

Если в память поместится.. (2^h-1)

... :) Облачные серверы от RegRu - промокод 3F85-3D10-806D-7224 ( http://levik.info/regru )
L
На сайте с 07.12.2007
Offline
351
#13
bay_ebook:
Вы получаете массив чисел в качестве входного параметра, который выглядит как пирамида

Зачем предварительно организовывать хранение данных в деревьях/таблицах, чтобы потом по ним ещё раз искать оптимальный?

Сразу обработать входной массив в поисках оптимального маршрута - не получится?

Есть пример входного массива?

bay_ebook
На сайте с 28.05.2010
Offline
111
#14
Ladycharm:
Зачем предварительно организовывать хранение данных в деревьях/таблицах, чтобы потом по ним ещё раз искать оптимальный?
Сразу обработать входной массив в поисках оптимального маршрута - не получится?

Есть пример входного массива?

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

Написал рекурсию на обход все веток пирамиды с запоминанием максимальной суммы и ID самой нижней ветки (дна) и потом функцию поиска верхнего уровня. Посмотрю чего скажут "великие головы" которые такие задачи придумали :)

Нужен прогер на php+mysql+понимание чужего кода? (/ru/forum/540660) Вам сюда PHP-шаман (http://php-shaman.pw/)
Милованов Ю.С
На сайте с 24.01.2008
Offline
197
#15

Не знаю че скажут эти великие головы, но с вопросами в СУЗе от подобных голов тоже встречался. Боюсь подумать, какие там головы в ВУЗах:D

Подпись))
12

Авторизуйтесь или зарегистрируйтесь, чтобы оставить комментарий