Джесс Либерти - Освой самостоятельно С++ за 21 день.

for (int i = 0; i<5; i++)

{

cout << "i: " << i << endl;

}

i = 7; // теперь переменная i будет корректно восприниматься всеми компиляторами return 0;

}

На занятии 5 рассматривался пример построения ряда чисел Фибоначчи с использованием рекурсивного алгоритма. Напомним, что этот ряд начинается числами 1, 1, 2, 3, а все последующие его члены являются суммой двух предыдущих.

1,1,2,3,5,8,13,21,34...

Таким образом, n-й член ряда Фибоначчи вычисляется сложением (rt-l)-TO и (n-2)-го членов. Рассмотрим вариант решения этой задачи с помощью циклов (листинг 7.15).

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

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

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

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

4:

5: #include

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) и циклическим методами. Несомненно, рекурсивный вариант программы более компактный, однако многократный вызов функции, использующийся в любом рекурсивном алгоритме, заметно снижает его быстродействие. Поэтому использование цикла более приемлемо с точки зрения скорости выполнения. Кроме того, благодаря оптимизации арифметических операций в большинстве современных микропроцессоров превосходство не рекурсивных алгоритмов в скорости становится все более очевидным.