Пути по клеткам

  • 4 мин чтения
  • Послушать — 3 мин
  • 10 карточек

Математика, 5 класс · Г. В. Дорофеев, Л. Г. Петерсон

Робот идёт по клетчатому полю только вправо и вверх и собирает монеты. Как найти наибольшую добычу, не перебирая все пути?

Идея: считать по клеткам, а не по путям. В каждую клетку можно прийти только слева или снизу. Значит, лучшая добыча на пути к клетке равна её числу плюс большее из значений для соседа слева и соседа снизу.

Способ:

  1. В стартовую клетку впиши её число.
  2. Заполняй поле по рядам снизу вверх, слева направо: для каждой клетки — её число плюс максимум из клетки слева и клетки снизу (у края — тот сосед, который есть).
  3. Число в финишной клетке — ответ.

Так же можно посчитать количество путей: в каждую клетку ведёт столько путей, сколько в соседа слева и в соседа снизу вместе.

Чтобы найти сам лучший путь, пройди от финиша назад, каждый раз переходя к тому соседу, у которого значение больше.

Наглядно

1 / 10

Робот и монеты

Робот идёт по полю только вправо и вверх и собирает монеты. Как найти наибольшую добычу?

Поле 3 на 3 клетки с монетами. Нижний ряд: 2, 5, 7; средний: 6, 2, 9; верхний: 7, 1, 4. Старт — левая нижняя клетка (зелёная), финиш — правая верхняя (красная); стрелки: ходить можно вправо и вверх
Поле 3 на 3 клетки с монетами. Нижний ряд: 2, 5, 7; средний: 6, 2, 9; верхний: 7, 1, 4. Старт — левая нижняя клетка (зелёная), финиш — правая верхняя (красная); стрелки: ходить можно вправо и вверх

Правило

2 / 10

Считаем по клеткам

Считай по клеткам, а не по путям. В каждую клетку можно прийти только слева или снизу.

Лучшая добыча на пути к клетке — её число плюс большее из значений для соседа слева и соседа снизу.

Правило

3 / 10

Способ

  1. В стартовую клетку впиши её число.
  2. Заполняй поле по рядам снизу вверх, слева направо: число клетки плюс большее из значений соседа слева и соседа снизу (у края — тот сосед, который есть).
  3. Число в финишной клетке — ответ.

Разбор

4 / 10

Заполняем поле

Поле с рисунка: нижний ряд 2, 5, 7, средний 6, 2, 9, верхний 7, 1, 4.

  1. Нижний ряд

    2; 2 + 5 = 7; 7 + 7 = 14

  2. Средний ряд

    2 + 6 = 8; 2 + 8 = 10, ведь 8 > 7; 9 + 14 = 23, ведь 14 > 10

  3. Верхний ряд

    8 + 7 = 15; 1 + 15 = 16; 4 + 23 = 27

  4. Ответ

    27 монет

Проверь себя

5 / 10

Что вписать?

Число клетки плюс большее из двух соседей.

В клетке 5 монет. У соседа слева записано 12, у соседа снизу — 9. Что вписать?

171426
Ответ и объяснение

5 + 12 = 17: выгоднее прийти слева.

Наглядно

6 / 10

Лучший путь

Сам путь ищут от финиша назад: каждый раз к тому соседу, у которого значение больше.

То же поле с лучшими результатами. Нижний ряд: 2, 7, 14; средний: 8, 10, 23; верхний: 15, 16, 27. Закрашен лучший путь: по нижнему ряду вправо, потом вверх — 2, 7, 14, 23, 27
То же поле с лучшими результатами. Нижний ряд: 2, 7, 14; средний: 8, 10, 23; верхний: 15, 16, 27. Закрашен лучший путь: по нижнему ряду вправо, потом вверх — 2, 7, 14, 23, 27

Частая ошибка

7 / 10

Жадный шаг

Ошибка: на каждом шаге идти к большему числу рядом.

Из 2 — вверх к 6 (а не к 5), потом 7, 1, 4: всего 20 монет.

А лучший путь даёт 27. Считай по клеткам, а не «на глаз».

Правило

8 / 10

Сколько путей

Так же считают количество путей: в клетку ведёт столько путей, сколько в соседа слева и в соседа снизу вместе.

Поле 3 на 4 с числом путей в каждую клетку: нижний ряд 1, 1, 1, 1; средний 1, 2, 3, 4; верхний 1, 3, 6, 10. В правую верхнюю клетку ведут 10 путей
Поле 3 на 4 с числом путей в каждую клетку: нижний ряд 1, 1, 1, 1; средний 1, 2, 3, 4; верхний 1, 3, 6, 10. В правую верхнюю клетку ведут 10 путей

Проверь себя

9 / 10

Монеты или пути?

Пути — сумма соседей, монеты — больший сосед.

Считаем пути. В соседа слева ведут 3 пути, в соседа снизу — 6. Сколько путей в клетку?

6918
Ответ и объяснение

3 + 6 = 9: каждый путь приходит либо слева, либо снизу.

Главное

10 / 10

Главное

  • Считай по клеткам, а не по путям.
  • Монеты: число клетки плюс большее из значений соседей слева и снизу.
  • Заполняй снизу вверх, слева направо; ответ — в финише.
  • Число путей — сумма соседей; лучший путь — от финиша назад.

Проверь себя: тест по теме

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

  • Задания из этого учебника
  • Ответ проверяется сразу
  • Без регистрации
Начать тест