11000. Пчела

В Африке живет специальный вид пчел. Каждый год самка производит на свет одого самца, а самец – самца и самку, после чего родители погибают. Ученые изобрели магическую самку пчелу, которая плодится как обыкновенная самка, но при этом является бессмертной. Необходимо вычислить число самцов и общее количество пчел в семействе, если изначально была лишь одна магическая самка пчела.

Вход. Каждая строка содержит целое N (N ³ 0).Последний тест содержит N = -1 и не обрабатывается.

Выход. Для каждого значения N вывести число самцов и общее количество пчел в семействе через N лет. Выводимые числа не более 2³².

Пример входа

1

3

-1

Пример выхода

1 2

4 7

РЕШЕНИЕ

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

Анализ алгоритма

Обозначим n - ое число Фибоначчи через f(n). Тогда через n лет число самцов в пчелином семействе будет равно f(n) – 1, а общее число пчел f(n + 1) – 1. Через n = 0 лет семейство состоит из единственной пчелы самки, то есть имеется 0 самцов и 1 пчела. Положим f(0) = 1, f(1) = 2. Далее по индукции докажем справедливость приведенного утверждения. После n + 1 года число самцов равно суммарному числу самок и самцов после n - го года, то есть f(n + 1) – 1. Число самок после n + 1 года равно числу самцов после n - го года плюс одна бессмертная самка, то есть f(n) – 1 + 1 = f(n). Таким образом общее число пчел после n + 1 года равно f(n + 1) – 1 + f(n) = f(n + 2) – 1.

Реализация алгоритма

Искомые числа Фибоначчи не превосходят 2³². Вычислим их первые 50 значений и занесем в массив f типа long long.

long long f[50];

Заполним массив f числами Фибоначчи.

f[0] = 1; f[1] = 2;

for(i = 2; i < 50; i++) f[i] = f[i-1] + f[i-2];

Для каждого входного n выведем результат.

while(scanf("%d",&n),n >= 0)

printf("%lld %lld\n",f[n] - 1,f[n+1] - 1);