Question

В одной из вершин треугольника сидит лягушка. Она прыгает по вершинам треугольника, перемещаясь каждый раз в одну из соседних вершин. Сколькими способами лягушка может попасть в начальную вершину за 9 прыжков?

Answer 1

# Код на ruby 2.2.3p173
count = 0
for i in 0..2**9-1
    s = ("000000000"+i.to_s(2))[-9..-1]
    vertix = 0
    s.chars.each {|c|
        vertix = (vertix + (c == "1" ? 1 : -1)) % 3 ;
        # p [c, vertix]
    }
    if vertix == 0
        p s
        count += 1
    end
end
p count

Вывод
170

Answer 2

Для решения этой задачи мы можем использовать метод динамического программирования. Предположим, что у нас есть треугольник с вершинами A, B и C, и лягушка начинает в вершине A.

Давайте обозначим количество способов, которыми лягушка может попасть в каждую вершину после i-го прыжка, как F(i, A), F(i, B) и F(i, C).

Теперь мы можем рассмотреть все возможные способы, которыми лягушка может попасть в каждую вершину после i-го прыжка. Например, чтобы попасть в вершину A после i-го прыжка, лягушка может либо сделать прыжок из вершины B в A, либо из вершины C в A. Таким образом, F(i, A) = F(i-1, B) + F(i-1, C).

Аналогично, мы можем найти F(i, B) и F(i, C) через предыдущие значения и таким образом рекурсивно находим количество способов попасть в каждую вершину после каждого прыжка.

Затем мы можем найти количество способов попасть в начальную вершину после 9 прыжков, что будет равно F(9, A) + F(9, B) + F(9, C).

Таким образом, используя метод динамического программирования, мы можем найти количество способов, которыми лягушка может попасть в начальную вершину за 9 прыжков.