Неділя
06.10.2024
23:14


ФОРМА ВХОДУ

Вітаю Вас Гість | RSS
Солонянська шкільна лабораторія
нових інформаційних технологій

Відділ освіти Солонянської РДА
Головна Задача06 Реєстрація Вхід


Україна - єдина країна

Меню


Информатика и ИКТ в современной школе

Как создать свой сайт

Всё для создания сайта на ucoz


Буратіно в замку.

Стародавній замок має форму квадрата й містить N x N кімнат. У кожній кімнаті розставлені скриньки із золотими монетами. Буратіно знаходиться у верхній лівій кімнаті й мріє, зібравши якомога більше монет, дістатись до правої нижньої кімнати. З кожної кімнати він може перейти до сусідньої знизу або сусідньої праворуч. Ви також хочете запам’ятати маршрут, який пройде Буратіно.

Ідея розв’язання. Задача є класичною задачею динамічного програмування. Розглянути всі можливі маршрути майже нереально. Тому подамо замок у вигляді двовимірного масиву, у кожну клітинку якого запишемо кількість монет у відповідній кімнаті. За умовою загальна кількість монет повинна бути максимальною, а це значить, що вона повинна бути максимальною як на усьому маршруті, так і на кожній ділянці. Тому заведемо ще один двовимірний масив, у якому будемо записувати максимальні значення при виборі із двох можливих кімнат.

Малюнок, який ілюструє роботу програми для випадку N=5


input.txtoutput.txtburatino.pas


Місцевий час



Корисні посилання
Солонянська СЗШ №1
Солонянський РНМК
відділ освіти
**********
Освітній портал
ДОІППО
Єдиний освітній центр



Copyright MyCorp © 2024Безкоштовний хостинг uCoz