Листинг 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) и циклическим методами. Несомненно, рекурсивный вариант программы более компактный, однако многократный вызов функции, использующийся в любом рекурсивном алгоритме, заметно снижает его быстродействие. Поэтому использование цикла более приемлемо с точки зрения скорости выполнения. Кроме того, благодаря оптимизации арифметических операций в большинстве современных микропроцессоров превосходство не рекурсивных алгоритмов в скорости становится все более очевидным.
Испытывая программу, не вводите слишком большие номера членов ряда Фибоначчи. Значения членов ряда возрастают довольно быстро и ввод большого порядкового номера может привести к переполнению регистра памяти.
|
|
|
Оператор switch
На занятии 4 вы познакомились с операторами if и if/else. Однако в некоторых ситуациях применение оператора if может привести к возникновению конструкций с большим числом вложений, значительно усложняющих как написание, так и восприятие программы. Для решения этой проблемы в языке C++ предусмотрен оператор switch. Основным его отличием от оператора if является то, что он позволяет проверять сразу несколько условий, в результате чего ветвление программы организуется более эффективно. Синтаксис оператора switch следующий:
switch (выражение)
{
case ПервоеЗначение: оператор;
break;
case ВтороеЗначение: оператор;
break;
....
case Значение_N: оператор:
break;
default: оператор;
}
В скобках за оператором switch может использоваться любое выражение, корректное с точки зрения синтаксиса языка. Вместо идентификатора оператор допускается использование любого оператора или выражения, а также последовательности операторов или выражений, результатом выполнения которых является целочисленное значение (или значение, которое может быть однозначно приведено к целочисленному типу). Поэтому использование логических операций или выражений сравнения здесь не допускается.
|
|
|
Оператор switch
Синтаксис использования оператора switch следующий:
switch (выражение)
{
case ПервоеЗначение: оператор;
break;
case ВтороеЗначение: оператор;
break;
....
case Значение_N: оператор:
break;
default: оператор;
}
Оператор switch позволяет осуществлять ветвление программы по результатам выражения, возвращающего несколько возможных значений. Значение, возвращенное выражением, заданным в скобках оператора switch, сравнивается со значениями, указанными за операторами case, и в случае совпадения значений выполняется выражение в строке соответствующего оператора case. Будут выполняться все строки программы после выбранного оператора до тех пор, пока не закончится тело блока оператора switch, или не повстречается оператор break.
Если ни одно из значений операторов case не совпадет с возвращенным значением, то выполняются строки программы, стоящие после оператора default, в случае же отсутствия этого оператора в теле блока switch. управление будет передано следующей за этим блоком строке программы.
Пример 1:
switch (choice)
{
case 0:
cout << "Zero!" << endl;
break;
case 1:
cout << "One!" << endl;
break;
case 2:
cout << "Two!" << endl;
break;
default:
cout << "Default!" << endl;
break;
}
Пример 2:
switch (choice)
{
case 0:
case 1:
case 2:
cout << "Less than 3!" << endl;
break;
case 3:
cout << "Equals 3!" << endl;
break;
default:
cout << "Greater that 3!" << endl;
}
При отсутствии оператора break после оператора или выражения, следующего за case, будет выполняться выражение очередного блока case. В большинстве случаев такая ситуация возникает, когда оператор break пропущен по ошибке. Поэтому, если break опускается умышленно, рекомендуем вставлять в соответствующую строку комментарий. Пример использования оператора switch приведен в листинге 7.16.
Дата добавления: 2019-02-12; просмотров: 253; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!