Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 43 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

. Практикум по курсу «Алгоритмизация и программирование». Часть 2
scanf("%d",&n);
if(n<=0)
printf("Введите положительное число.\n");
else break;
}
int k=Fibonachi(n);// вызов функции
printf("F[%d]=%d\n",n,k);
}
// определение функции вычисления n-го числа Фибоначчи
int Fibonachi(int n)
{
// числа Фибоначчи вычисляются только для n > 0
if(n <= 0) return -1;
// условие выхода из рекурсии
if(n==2 || n==1)
return 1;
else
// рекурсивный вызов функции
return Fibonachi(n-2)+Fibonachi(n-1);
}
Это пример задачи, в которой рекурсивный алгоритм очевиден, но его ис-
пользование приводит к большим вычислительным расходам и излишним за-
тратам памяти. В теле функции Fibonachi несколько раз осуществляется
рекурсивный вызов. Каждый вызов требует выделения памяти. Например, для
вычисления F
10
необходимо вызвать функцию Fibonachi для вычисления
F
9
и F
8
. В свою очередь, для вычисления F
9
снова понадобится вызвать функ-
цию Fibonachi для вычисления F
8
и т.д. согласно приведенной ниже схеме:
F
10
=
F
9
+ F
8
F
9
=
F
8
+ F
7
F
8
=
F
7
+ F
6
F
8
=
F
7
+ F
6
F
7
=
F
6
+ F
5
F
7
=
F
6
+ F
5
F
6
=
F
5
+ F
4
. . . .
Из схемы видно, что для некоторых аргументов приходится осуществлять
повторные вызовы функции Fibonachi, т. е. происходят лишние вычисле-
ния.
Задача 3. Задача о Ханойской башне.
Согласно легенде в одном из буддийских монастырей монахи уже тысячу
43
              .       Практикум по курсу «Алгоритмизация и программирование». Часть 2
                  scanf("%d",&n);
                  if(n<=0)
                       printf("Введите положительное число.\n");
                  else break;
          }

          int k=Fibonachi(n);// вызов функции
          printf("F[%d]=%d\n",n,k);
   }


   // определение функции вычисления n-го числа Фибоначчи
   int Fibonachi(int n)
   {
         // числа Фибоначчи вычисляются только для n > 0
         if(n <= 0) return -1;

          // условие выхода из рекурсии
          if(n==2 || n==1)
               return 1;
          else
               // рекурсивный вызов функции
               return Fibonachi(n-2)+Fibonachi(n-1);
   }

    Это пример задачи, в которой рекурсивный алгоритм очевиден, но его ис-
пользование приводит к большим вычислительным расходам и излишним за-
тратам памяти. В теле функции Fibonachi несколько раз осуществляется
рекурсивный вызов. Каждый вызов требует выделения памяти. Например, для
вычисления F10 необходимо вызвать функцию Fibonachi для вычисления
F9 и F8. В свою очередь, для вычисления F9 снова понадобится вызвать функ-
цию Fibonachi для вычисления F8 и т.д. согласно приведенной ниже схеме:

                                   F10 = F9 + F8
                  F9 = F8 + F7                         F8 = F7 + F6
        F8 = F7 + F6       F7 = F6 + F5       F7 = F6 + F5       F6 = F5 + F4
                                     . .    . .

     Из схемы видно, что для некоторых аргументов приходится осуществлять
повторные вызовы функции Fibonachi, т. е. происходят лишние вычисле-
ния.
     Задача 3. Задача о Ханойской башне.
     Согласно легенде в одном из буддийских монастырей монахи уже тысячу
                                           43

Страницы