3. Вася шагает по шпалам. Каждый раз он может пойти либо на следующую шпалу, либо переступить через одну шпалу. Сколькими различными способами он сможет дойти с 1-ой шпалы до 4? А с 1-ой до 7?

Краткое пояснение:

Пошаговое решение:

Обозначим количество способов добраться до шпалы n как W(n).

Часть 1: С 1-ой шпалы до 4-ой.

• W(1) = 1 (начинаем с первой шпалы, есть 1 способ оказаться на ней).
• W(2): Можно попасть на 2-ю шпалу только с 1-ой. W(2) = W(1) = 1 способ.
• W(3): Можно попасть на 3-ю шпалу с 1-ой (переступив через 2-ю) или со 2-ой (переступив через 1-ю). W(3) = W(1) + W(2) = 1 + 1 = 2 способа.
• W(4): Можно попасть на 4-ю шпалу с 2-ой (переступив через 3-ю) или с 3-ей (переступив через 2-ю). W(4) = W(2) + W(3) = 1 + 2 = 3 способа.

Часть 2: С 1-ой шпалы до 7-ой.

Продолжаем по тому же принципу:

• W(5) = W(3) + W(4) = 2 + 3 = 5 способов.
• W(6) = W(4) + W(5) = 3 + 5 = 8 способов.
• W(7) = W(5) + W(6) = 5 + 8 = 13 способов.

Это последовательность Фибоначчи, где каждое число является суммой двух предыдущих (начиная с W(3)).

Ответ: С 1-ой шпалы до 4-ой — 3 способа. С 1-ой до 7-ой — 13 способов.