Освой самостоятельно С++ за 21 день.
Шрифт:
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 <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.
Анализ:
В строке 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) и циклическим методами. Несомненно, рекурсивный вариант программы более компактный, однако многократный вызов функции, использующийся в любом рекурсивном алгоритме, заметно снижает его быстродействие. Поэтому использование цикла более приемлемо с точки зрения скорости выполнения. Кроме того, благодаря оптимизации арифметических операций в большинстве современных микропроцессоров превосходство не рекурсивных алгоритмов в скорости становится все более очевидным.
Испытывая программу, не вводите слишком большие номера членов ряда Фибоначчи. Значения членов ряда возрастают довольно быстро и ввод большого порядкового номера может привести к переполнению регистра памяти.
Оператор switch
На занятии 4 вы познакомились с операторами if и if/else. Однако в некоторых ситуациях применение оператора if может привести к возникновению конструкций с большим числом вложений, значительно усложняющих как написание, так и восприятие программы. Для решения этой проблемы в языке C++ предусмотрен оператор switch. Основным его отличием от оператора if является то, что он позволяет проверять сразу несколько условий, в результате чего ветвление программы организуется более эффективно. Синтаксис оператора switch следующий:
switch (выражение)
{
case ПервоеЗначение: оператор;
break;
case ВтороеЗначение: оператор;
break;
....
case Значение_N: оператор:
break;
default: оператор;
}
В скобках за оператором switch может использоваться любое выражение, корректное с точки зрения синтаксиса языка. Вместо идентификатора оператор допускается использование любого оператора или выражения, а также последовательности операторов или выражений, результатом выполнения которых является целочисленное значение (или значение, которое может быть однозначно приведено к целочисленному типу). Поэтому использование логических операций или выражений сравнения здесь не допускается.