Задание 3 Параграф 1.6 ГДЗ Босова 9 класс Углубленный уровень (Информатика)
Рассмотрим вариант решения задания из учебника
Босова, Аквилянов 9 класс, Просвещение:
В материалах международного конкурса по информатике «Бобёр» есть такая задача, предложенная разработчиками из Нидерландов. Бобёр Билли любит жёлуди. Он хочет поплыть по течению и собрать все жёлуди на островах, мимо которых будет проплывать. Какое максимальное количество желудей он сможет собрать?
Для каждого острова выбираем максимальное количество желудей, которое можно собрать, доплыв до него.
В таблице следующие строки:
n – номер острова
k – количество желудей на острове
max – максимальное количество желудей, которые можно собрать, доплыв до этого острова.
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
k 2 0 5 8 1 0 0 5 2 2 2 3 0 4 3 0
max 2 2 7 10 8 7 10 15 10 9 12 18 15 14 12 18
Путь: 1 - > 2 - > 4 - > 8 - > 12 - > 16 (2 + 0 + 8 + 5 + 3 + 0 = 18)
Другое решение через построение дерева. Всего получается 16 возможных маршрутов. Наилучший маршрут обозначен цветом. На дугах обозначено передающееся количество желудей.
Ответ: 18
