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

12
bay_ebook
На сайте с 28.05.2010
Offline
111
1053

Вы получаете массив чисел в качестве входного параметра, который выглядит как пирамида - каждый номер строки связана с двумя другими числами в ряду ниже его.

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

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

Цифры могут повторяться, и не должны быть отсортированы.

Пример маршрута: 1 - 16 - 56 - 1434

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

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

Это реферальная система?

Я для себя использую вариант на Мускуле с таблицей из 3 полей(`id`, `refer_id`, `referal_id`, `level`)

Пусть она и избыточна(если у юзера есть реферал 5 уровня, то он не ищется перебором рефералов 1,2,3,4 уровней, а пишется в БД).

Даже если записей будет 10 миллионов, то индексы сделают свое дело(в таблице только данные типа int)

Подпись))
bay_ebook
На сайте с 28.05.2010
Offline
111
#2

Нет, к сожалению не рефералка. По факту мне нужно найти сумму чисел, цепочку, чья сумма значений будет максимальной.

Милованов Ю.С
На сайте с 24.01.2008
Offline
197
#3

Это вообще что такое? Чем больше инфы - тем лучше, сам знаешь;)

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

Потом просто находим max(`summa_ot_samogo_starshego_roditel9`) и уже вычисляем саму цепочку чисел из другой таблицы(id, num) если надо.

Оптимизайка
На сайте с 11.03.2012
Offline
396
#4

При построении этого двоичного дерева храните не только значение отдельного листа, но и сразу вычисляйте сумму значения предка и текущего листа. Тогда конечные листы ("дно пирамиды") будут содержать максимально возможные значения. Для определения цепочки - просто выполнить обратный обход дерева. Т.е. самый выгодный маршрут будет 4-1-20, а не 4-10-2, как может показаться при обходе с корня:

⭐ BotGuard (https://botguard.net) ⭐ — защита вашего сайта от вредоносных ботов, воровства контента, клонирования, спама и хакерских атак!
bay_ebook
На сайте с 28.05.2010
Offline
111
#5

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

Вариант с расчетом и хранением суммы от родителя - да, рассматриваю. Но по факту у него слабое место - много итераций, вот и думаю как уменьшить, как вывернуться :)

Милованов Ю.С
На сайте с 24.01.2008
Offline
197
#6

Если бы было к примеру, что на 1 уровне десятки, на 2 сотки, на 3 тысячи и т.д. То есть знать, что в родителе число всегда меньше(или наоборот больше), чем в потомке, тогда да, тупая рекурсивная функция для массива(ищем ключ, который больше/меньше всех своих соседей(они такого же уровня), форычим значение(если массив) этого ключа).

А если числа во всех ячейках рандомные(любая ячейка от 0 до +~), то скорей всего без полного перебора всех комбинаций не обойтись.

ЗЫ. там че в условии задачи написано: "программа должна работать на тетрисе":D

Оптимизайка
На сайте с 11.03.2012
Offline
396
#7

В каком месте много итераций? Вам нужно построить дерево на основе существущих данных, с дополнительными признаками у листа (сумма, "есть дочки") взять максимальное значение со "дна пирамиды" ("нет дочки"), продвинуться к корню дерева и перевернуть полученную цепочку. Задача в-общем, тривиальная.

Милованов Ю.С
На сайте с 24.01.2008
Offline
197
#8

От полного перебора никак не уйдешь!!!

Ты же заранее не знаешь, где и какие числ. Они же ведь везде рандомные и в 10 потомке может быть число в 100500 раз больше чем в родителе. Поэтому необходимо построить древо.

Если уж без БД, то ситуация очень похожа на рекурсивную функцию для обхода директории(если директория - заходим в нее и опять вызываем функцию, а если файл, то отображаем его название). Тут все также: если значение ячейки == массив - делаем то что надо(суммируем и т.д.), а если число, то значит конец и надо продолжать, пока не будет конец конца:D

Оптимизайка
На сайте с 11.03.2012
Offline
396
#9

Если есть память, то можно дополнительно использовать массив указателей на листья без "дочек", "дно пирамиды". В этом случае полный обход дерева и рекурсии не нужны.

Милованов Ю.С
На сайте с 24.01.2008
Offline
197
#10

Оптимизайка, а для указателей Вы будете использовать линейный(есть еще условый и циклический) алгоритм? Доступ к ячейки к указателям массива не есть перебор этого самого массива?

Перебор по-любому нужен, хоть с указателями, хоть без! Потому что Вы не можете знать где какое число, и Вам по-любому нужно все просчитать.

ПокАжите решение без рекурсии и без обхода(не получая доступ к ячейкам) массива - либо вырву тот волос(он уже заждался, когда же я проиграю пари), либо отсеку ту(не совсем ту, та была отсечена, не дождавшись когда я проспорю) белую часть ногтя;D

12

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