Числа Фибоначчи

1. Человек может, поднимаясь по лестнице ступать на соседнюю ступеньку, переступать через одну, переступать через две ступеньки. Сколькими способами данный человек сможет подняться на лестницу, состоящую из N ступенек (2<N<30).

Пример ввода: 4

Пример вывода: 7

Сразу видно, что на одну ступеньку можно подняться одним способом. На две ступеньки двумя способами. На три ступеньки четырьмя.

На четвёртую ступень человек может прийти либо с первой, либо со второй, либо с третьей ступеней. А поскольку нам известно количество способов, которыми он может оказаться на них, то:

a[4]=a[1]+a[2]+a[3] (7 способов)

Таким образом, на ступеньку под номером i человек может ступить с i-1 ступеньки с i-2 или i-3 ступеней, т.е.

a[i]=a[i-1]+a[i-2]+a[i-3]

writeln(' Введите количество ступенек k ');

readln(k);

a[1]:=1; a[2]:=2; a[3]:=4;

for i:=4 to k do

a[i]:=a[i-1]+a[i-2]+a[i-3];

write(‘Количество способов = ’a[k]);

Задания для самостоятельного решения

1. Некоторое дерево растёт по следующему закону: ствол дерева пускает новую ветвь, на следующий год он "отдыхает" и только через год пускает еще одну ветвь - точно так же ведет себя каждая ветвь. Сколько ветвей будет на дереве через N лет?

2. Пара кроликов через месяц производит на свет другую пару, а потомство они дают со второго месяца после своего рождения. Итак, через месяц будет две пары, через два месяца - три пары, а через четыре месяца - пять, так как к паре, рожденной первой парой, добавятся первые дети от второй пары. ... Сколько пар кроликов будет через N месяцев.

3. Некоторый робот может, поднимаясь по лестнице ступать на соседнюю ступеньку, переступать через одну, через две и т.д. через K ступенек (2<=K<=10). Сколькими способами данный робот сможет подняться на лестницу, состоящую из N ступенек (2<N<20).

4. Пусть через один такт времени красная клетка превращается в зеленую, а та в свою очередь через один такт делиться на две - красную и зеленую. Вначале задано K красных клеток и R зелёных. Сколько всего клеток будет через N тактов времени. K, R, N – заданные натуральные числа.