2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Проект Эйлера
Сообщение26.07.2014, 12:40 


02/03/10
73
Как можно решить эту задачу, кроме простого перебора?
http://euler.jakumo.org/problems/view/18.html
Найдите максимальную сумму пути с вершины треугольника до его основания.
Начиная в вершине треугольника (пример ниже) и перемещаясь на смежные числа ниже, максимальная сумма до основания составляет 23.

3
7 4
2 4 6
8 5 9 3
Найдите максимальную сумму пути от вершины до основания следующего треугольника:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Примечание: Так как в данном треугольнике всего 16384 маршрута от вершины до основания, эту задачу можно решить проверяя каждый из маршрутов.

 Профиль  
                  
 
 Re: Проект Эйлера
Сообщение26.07.2014, 12:48 
Заслуженный участник
Аватара пользователя


09/02/14

1377
Динамическое программирование.

 Профиль  
                  
 
 Re: Проект Эйлера
Сообщение27.07.2014, 23:13 


30/06/14
47
Ну зачем же перебирать все маршруты? Некоторое подобие волнового алгоритма. Идем снизу верх.
Начинаем с предпоследней строчки, для каждого элемента сохраняем его сумму с максимальным нижним смежным и запоминаем направление. Ну и так до самого верха.

Кол-во иттераций при этом будет пропорционально кол-ву элементов, а не кол-ву маршрутов.

-- 27.07.2014, 22:20 --

wcl.AleX в сообщении #890401 писал(а):
Найдите максимальную сумму пути от вершины до основания следующего треугольника:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

Примечание: Так как в данном треугольнике всего 16384 маршрута от вершины до основания, эту задачу можно решить проверяя каждый из маршрутов.


Если нам нужна только сумма, то еще проще.
Берем предпоследнюю строку.
Например там стоит 63, а смежные числа с последней строки 04 и 62. Что больше? 62
Потому меняем 63 на 63+62
Далее следующий элемент 66, смежные нижней строки 62 и 98
значит заменяем 66 на 66+98 и так далее, когда дойдем до самого верха - там будет искомая сумма

 Профиль  
                  
 
 Re: Проект Эйлера
Сообщение28.07.2014, 08:03 


01/12/11

1047
Оба направления счёта: вниз или вверх, равноценны.

 Профиль  
                  
 
 Re: Проект Эйлера
Сообщение28.07.2014, 10:49 


01/12/11

1047
wcl.AleX в сообщении #890401 писал(а):
Как можно решить эту задачу, кроме простого перебора?
http://euler.jakumo.org/problems/view/18.html
Найдите максимальную сумму пути с вершины треугольника до его основания.
Начиная в вершине треугольника (пример ниже) и перемещаясь на смежные числа ниже, максимальная сумма до основания составляет 23.

3
7 4
2 4 6
8 5 9 3

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

 Профиль  
                  
 
 Re: Проект Эйлера
Сообщение28.07.2014, 16:14 


30/06/14
47
Skeptic в сообщении #890812 писал(а):
Оба направления счёта: вниз или вверх, равноценны.


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

Если представить треугольник в виде массива A, где верхний элемент A[1,1], нижний левый A[k,1], нижний правый A[k,k], то весь расчет на Delphi, будет выглядеть так:

Код:
for i:=k-1 downto 1 do for j:=1 to i do A[i,j]:=A[i,j]+max(A[i+1,j],A[i+1,J+1];


После чего из A[1,1] берем результат...

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

 Профиль  
                  
 
 Re: Проект Эйлера
Сообщение18.09.2014, 18:00 
Заслуженный участник


27/04/09
28128
Skeptic в сообщении #890846 писал(а):
На сайте по ссылке другая задача: каждое число в строке имеет только два смежных в следущей.
Та же, просто тут код съехал.

-- Чт сен 18, 2014 21:10:17 --

В OEIS, если не ошибаюсь, такие треугольники только так и пишутся в комментариях, и все всё понимают — это распространённая форма записи.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group