Контрольные задания > 112. Маша пришла в лес за грибами. У неё есть план леса в виде графа (рис. 66). Вершины гра- — это тропинки. Чтобы не заблудиться, идти по тропинке фа - это полянки в лесу, рёбра — это тропинки. Чтобы не заблудиться, идти по тропинке можно только в указанном направлении. На некоторых полянках растут грибы, их количество указано внутри вершин. Какое наибольшее количество грибов она может со- брать? Указание. Решайте задачу, постепенно удаляясь от входа в лес и вычисляя наибольшее количество грибов, которое можно собрать, дойдя до каждой лесной полянки. Тогда в са- мом конце вы получите ответ для последней полянки, которая находится на выходе.
Вопрос:

112. Маша пришла в лес за грибами. У неё есть план леса в виде графа (рис. 66). Вершины гра- — это тропинки. Чтобы не заблудиться, идти по тропинке фа - это полянки в лесу, рёбра — это тропинки. Чтобы не заблудиться, идти по тропинке можно только в указанном направлении. На некоторых полянках растут грибы, их количество указано внутри вершин. Какое наибольшее количество грибов она может со- брать? Указание. Решайте задачу, постепенно удаляясь от входа в лес и вычисляя наибольшее количество грибов, которое можно собрать, дойдя до каждой лесной полянки. Тогда в са- мом конце вы получите ответ для последней полянки, которая находится на выходе.

Смотреть решения всех заданий с листа

Ответ:

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

Смотри, тут всё просто: нужно сложить все варианты сбора грибов по тропинкам, а потом выбрать наибольшее число.

Начинаем:

  1. Считаем количество грибов, которое можно собрать, двигаясь от входа к выходу:

    • 2 + 8 + 6 + 1 = 17

    • 2 + 8 + 5 + 4 + 2 = 21

    • 2 + 1 + 3 + 1 = 7

    • 2 + 1 + 2 + 2 = 7

    • 2 + 5 + 4 + 2 = 13

    • 2 + 5 + 3 + 1 = 11

  2. Выбираем наибольшее количество грибов: 21.

Ответ: 21

ГДЗ по фото 📸