Озадачили

Вчерашние старшеклассники, а сейчас уже студенты, иногда озадачивают меня такими хитрыми задачами: "Человек стоит на первой ступени лестницы. Его действия: подняться на одну ступень вверх, либо подняться на две ступени. Сколькими способами человек это может сделать? Сколькими способами он может подняться вверх. Максимум 100 ступеней".

Привожу листинг переписки (ICQ).

Lena (23:45:37): Формулу подобрать не могу
Lena (23:47:29): Вот мои расчеты: при 3 ст. количество способов =2
Lena (23:47:41): При 4 - 3
Lena (23:47:49): При 5-5
Lena (23:48:32): При 6-8, при 7-13, при 8-21, при 9-34, при 10-55
Lena (23:48:45): И при 11-89
Lena (23:51:40): Что скажете?
 Fakel (23:52:02): это просто
 Fakel (23:52:10): 3+5=8
 Fakel (23:52:25): 5+8=13
 Fakel (23:52:36): 8+13=21
 Fakel (23:52:48): 13+21=34
 Fakel (23:52:50): тд
 Fakel (23:53:01): )))))))
Lena (23:53:02): И что?
Lena (23:53:25): Прогу каким макаром писать?))))
 Fakel (23:53:27): 34+55=89
 Fakel (23:53:36): сумму
Lena (23:53:36): Да знаю,знаю
Lena (23:53:42): Я так и считала
 Fakel (23:54:18): Xn=(Xn-1)+(Xn-2)
 Fakel (23:55:44): надо 2 переменные
 Fakel (00:00:42): x1:=1;
 Fakel (00:00:45): x2:=2;
Lena (00:01:05): Я кажется догадываюсь
 Fakel (00:01:06): for i=3 to 100 do begin
 Fakel (00:01:15): x:=x1+x2;
 Fakel (00:01:21): x2:=x;
 Fakel (00:01:27): x1:=x-x1;
 Fakel (00:01:29): end;
 Fakel (00:01:48): там тока разберись c for i:=?? to 100 do
 Fakel (00:03:03): write ( x );
Lena (00:04:35): Ух ты
Lena (00:04:41): Спасибо большое!

 

Теги: 

Для 4 ступенек:

1111, 112, 121, 211

те надо найти все комбинации 1 и 2 чтобы в сумме давали количество ступенек, в данном случае 4:

1+1+1+1=4
1+1+2=4
1+2+1=4
2+1+1=4

остается написать программу

--------
Ильфат Рифатович Исмагилов

Забыли еще один вариант для 4-х ступенек

22

2+2 = 4

Мой блог тут http://oivt.ru/blog/3
А где ваш? Нету? Заведи свой персональный блог на ОИВТ.ру !

Хорошо вы так сами с собой поговорили :)

Два браузера. вот и не посмотрел с кого запостил ;) Отредакт ировал )))

--------
Ильфат Рифатович Исмагилов

А получаются самые обычные числа Фибоначчи, о которых говорится во всех учебниках по математике и олимпиадному программированию ;)

Сама задача - частный случай "Зайчика":
http://acmp.ru/?main=task&id_task=11