Question

Заяц прыгает в одном направлении по разделенной на клетки полосе 1 * 12. За один прыжок он может сместиться либо на одну, либо на две клетки. Сколькими способами заяц может добраться с 1-й клетки на 12-ю? ДАЮ 20 БАЛЛОВ!!!

Answer 1

Пошаговое объяснение:

Считаем для каждого варианта варианты:

12 прыжков по 1 клеточке - 1 вариант

10 по 1 клеточке + 1 прыжок на 2 клеточки - 11 вариантов

8 по 1 клеточке и 2 по 2 клетки - С(2,10) = 45 вариантов

6 по 1 клеточке и 3 по 2 клеточки - С(3, 9) = 84 варианта

4 по 1 клетке и 4 по 2 клеточки - С(4, 8) = 70 вариантов

2 по 1 клетке и 5 по 2 клетки - С(5, 7) = С(2, 7) = 28 вариантов

6 прыжков по 2 клеточки - 1 вариант.

Всего вариантов 1 + 11 + 45 + 84 + 70 + 28 + 1 = 240 вариантов

Answer 2

Спасибо за предоставленные 20 баллов! Давайте рассмотрим данную задачу.

Чтобы решить эту задачу, мы можем воспользоваться методом динамического программирования. Пусть dp[i] будет количество способов добраться до клетки i (где i принимает значения от 1 до 12). Так как заяц может прыгнуть либо на одну, либо на две клетки вперёд, то количество способов добраться до клетки i будет равно сумме способов добраться до клетки i-1 и i-2.

Формально:

cssCopy code
dp[i] = dp[i-1] + dp[i-2]

Начальные значения dp[1] и dp[2] равны 1, так как изначально заяц уже находится на 1-й клетке и может добраться до 2-й клетки либо сделав один прыжок, либо два.

Теперь мы можем начать вычислять значения dp[i] для i от 3 до 12:

cssCopy code
dp[1] = 1
dp[2] = 1
dp[3] = dp[2] + dp[1] = 2
dp[4] = dp[3] + dp[2] = 3
dp[5] = dp[4] + dp[3] = 5
...
dp[12] = dp[11] + dp[10] = 144

Итак, количество способов добраться от 1-й клетки до 12-й клетки составляет 144.

Если у вас есть ещё вопросы или задачи, не стесняйтесь спрашивать!