Листинг 7.15. Нахождение n-го члена ряда Фибоначчи с помощью цикла

1: // Листинг 7.15.

2: // Нахождение n-ro члена ряда Фибоначчи

3: // с помощью цикла

4:

5: #include < iostream.h>

6:

7:

8: int fib(int position);

9:

10: int main()

11: {

12: int answer, position;

13: cout < < " Which position? ";

14: cin > > position;

15: cout < < " \n";

16:

17: answer = fib(position);

18: cout < < answer < < " is the ";

19: cout < < position < < " Fibonacci number.\n";

20: return 0;

21: }

22:

23: int fib(int n)

24: {

25: int minusTwo=1, minusOne=1, answer=2;

26:

27: if (n < 3)

28: return 1;

29:

30: for (n -= 3; n; n--)

31: {

32: minusTwo = minusOne;

33: minusOne = answer;

34: answer = minusOne + minusTwo;

35: }

36:

37: return answer;

38: }

Результат:

Which position? 4

3 is the 4th Fibonacci number.

Which position? 5

5 is the 5th Fibonacci number.

Which position? 20

6765 is the 20th Fibonacci number.

Which position? 100

3314859971 is the 100th

Fibonacci number.

Анализ: Программа, представленная в листинге 7.15, позволяет найти значение любого члена ряда Фибоначчи. Использование рекурсии заменено циклом, организованным с помощью конструкции for. Кроме того, применение цикла уменьшает объем используемой памяти и время выполнения программы.

В строке 13 пользователю предлагается ввести порядковый номер искомого члена ряда Фибоначчи. Для нахождения этого значения используется функция fib(), в качестве параметра которой передается введенный порядковый номер. Если он меньше трех, функция возвращает значение 1. Для вычисления значений, порядковый номер которых превышает 2, используется приведенный ниже алгоритм.

1. Пpиcвaивaютcянaчaльныeзнaчeнияпepeмeнным: minusTwo=1, minus0ne=1, answer=2. Значение переменной, содержащей номер искомой позиции, уменьшается на 3, поскольку две первые позиции обрабатываются выше.

2. Для каждого значения n вычисляем значение очередного члена последовательности. Делается это следующим образом:

• переменной minusTwo присваивается значение переменной minusOne;

• переменной minusOne присваивается значение переменной answer;

• значения переменных minusOne и minusTwo суммируются и записываются в answer;

• значение n уменьшается на единицу.

3. Как только n достигнет нуля, возвращается значение переменной answer.

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

1, 1, 2,

Остается определить еще два члена ряда. Следующий член будет равен (2+1=3), а для вычисления искомого члена теперь нужно сложить значения только что полученного члена и предыдущего — числа 2 и 3, в результате чего получаем 5. В сущности, на каждом шаге мы смещаемся на один член вправо и уменьшаем количество искомых значений.

Особое внимание следует уделить выражению условия продолжения цикла for, записанному как n. Это одна из особенностей синтаксиса языка C++. По-другому это выражение можно представить в виде n'=0. Поскольку в C++ число 0 соответствует значению false, при достижении переменной n нуля условие продолжения цикла не будет выполняться. Исходя из сказанного, описание цикла может быть переписано в виде

for (n-=3; n! =0; n--)

Подобная запись значительно облегчит его восприятие. С другой стороны, первоначальный вариант программы иллюстрирует общепринятую для C++ форму записи условия, поэтому не стоит умышленно ее избегать.

Скомпилируйте и запустите полученную программу. Сравните время, затрачиваемое на вычисление 25-го числа рекурсивным (см. занятие 5) и циклическим методами. Несомненно, рекурсивный вариант программы более компактный, однако многократный вызов функции, использующийся в любом рекурсивном алгоритме, заметно снижает его быстродействие. Поэтому использование цикла более приемлемо с точки зрения скорости выполнения. Кроме того, благодаря оптимизации арифметических операций в большинстве современных микропроцессоров превосходство не рекурсивных алгоритмов в скорости становится все более очевидным.

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