Коник. Черепашка

Острів зламаних іграшок from lesson mail on Vimeo.


Задача 1. Коник-стрибунець, переміщуючись кроками або стрибками по стовпчиках, збирає або втрачає монети на кожному зі стовпчиків (відповідні числа у файлі konyk.txt). Знайти максимальну суму, яку він може зібрати.

коник

Стратегія полягає у тому, щоб отримувати максимальну суму на кожному стовпці, обираючи одну із двох стратегій: стрибати на цей стовпець чи переходити.

Для набору з прикладу ([1, -2, 4, -2, -3, -5, -1, 5, 3, -4]) виграшною стратегією є 1, 3, 5, 7, 8, 9, а загальна сума, яку можна отримати =5.

Покроковий алгоритм:

  1. Записуємо останній елемент стека у тимчасову змінну (піддаємо сумніву останній хід)
  2. Розглядаємо дві суми – останнього та передостаннього елемента з поточним стовпчиком
  3. Повертаємо у стек тимчасову змінну
  4. Записуємо у стек кращу з двох сум пункту 2


Задача 2. Черепашка. Дано файл, у якому записані монети, які може зібрати на своєму шляху черепашка, котра вміє рухатись лише праворуч та вниз. Знайти оптимальний маршрут черепашки, яка має дістатись у правий нижній кут поля.

черепаха

Принцип розв'язання залишається схожим. Створимо двовимірний список, у якому будемо фіксувати суми, накопичені під час проходження черепашкою поля. В окремий список заносимо відомості про те, з якого напрямку опинились у поточній клітинці.

Для поданого прикладу за позначеним маршрутом черепашка може отримати 96 монет, рухаючись вниз, вниз, вниз, вправо, вправо, вниз, вправо, вправо.

Завдання: вивести шлях не з кінця, а з початку


Задача 3. Порахувати, скільки способів потрапити з точки А в точку Б (якщо це взагалі можливо)

Яка тривалість маршруту черепашки?

Це стале число чи змінна?

Скільки можливих маршрутів у черепашки?

Остання зміна: середа 26 грудня 2018 11:12