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

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.

Листинг 7.16. Использование оператора switch

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

2: // Использование оператора switch

3:

4: #include <iostream.h>

5:

6: int main()

7: {

8:    unsigned short int number;

9:    cout << "Enter а number between 1 and 5: ";

10:   cin >> number;

11:   switch (number)

12:   {

13:     case 0: cout << "Too small, sorry!";

14:             break;  

15:     case 5: cout << "Good job!\n"; // fall through

16:     case 4: cout << "Nice Pick!\n"; // fall through

17:     case 3: cout << "Excellent!\n"; // fall through

18:     case 2: cout << "Masterful!\n"; // fall through

19:     case 1: cout << "Incredible!\n"; 

20:             break;  

21:     default: cout << "Too large!\n"; 

22:             break;  

23:   }    

24:   cout << "\n\n";  

25:   return 0;

26: }

Результат:

Enter a number between 1 and 5: 3

Excellent!

Masterful!

Incredible!

Enter a number between 1 and 5: 8

Too large!

Анализ: Сначала программа предлагает ввести число. Затем введенное число обрабатывается оператором switch. Если вводится 0, то это соответствует значению оператора case из строки 13 и на экран выводится сообщение Too small, sorry!, после чего оператор break завершает выполнение конструкции switch. Если вводится число 5, управление передается в строку 15 и выводится соответствующее сообщение. Затем выполняется строка 16, в которой также выводится сообщение, и так до строки 20. В этой строке оператор break завершает выполнение блока с оператором switch.