LecturesCMC/AL/Prac/Homework_FibPair

Рекурсивный алгоритм вычисления последовательной пары xчисел Фибоначчи

$$ F(2k) = F(k)(2F(k+1) - F(k)) $$ (если нужно чётное по номеру число Фибоначчи)
$$ F(2k+1) = F(k)^2 + F(k+1)^2 $$ (если нужно нечётное по номеру число)

Написать рекурсивную функцию fib(int n, int *f, int *f1), которая записывает в f и f1, соответственно, n-е и n+1-е числа Фибоначчи (нумерация начинается с 0: 0, 1, 1, 2, 3, 5, 8, 13, …).

Пример тестирующей программы:
```
   1 #include <stdio.h>
   2 int main(void) {
   3         int f, f1;
   4         int n;
   5         while (scanf("%d", &n)>0) {
   6                 fib(n, &f, &f1);
   7                 printf("%d: %d\n", n, f);
   8         }
   9         return 0;
  10 }
```

0 1 6 7 8 10 30

Подсказка: вариант решения. Вычислим F(n/2) и F(n/2+1). Для соседних чётного и нечётного n результаты будут одни и те же… При этом для чётного n мы можем вычислим пару F(n) и F(n+1), но для нечётного это будет F(n-1) и F(n). Ну и ладно. Это ж числа Фибоначчи! Правильную пару легко довычислить, ибо F(n+1) = F(n-1) + F(n)

CategoryHomework

LecturesCMC/AL/Prac/Homework_FibPair (последним исправлял пользователь hbd 2026-11-15 22:00:02)