Раздел «Образование».FIVTLecturesTerm1Lecture4:
<<Лекции ФИВТ, 1-й семестр

Лекция 4. Рекурсия и итерации.

Дерево рекурсивных вызовов. Стек вызовов.

Числа Фибоначчи. Итеративный и рекурсивный алгоритм.

Время работы рекурсивного и итеративного алгоритмов.

#include <stdio.h>
int fib(int n) {
   if ( n == 0 || n == 1 ) return 1;
   return fib(n-1) + fib(n-2);
}

#include <stdio.h>
int fib(int n) {
   int i, a = 0, b = 1; c;
   for ( i = 1; i < n; i++ ) {
      c = a + b;
      a = b;
      b = c;
   }
   return b;
}

в результате сложения единиц.

Задача возведения в степень: рекурсивный и итеративный алгоритмы.

2 алгоритма вычисления f(n)=a^n: итеративный и рекурсивный. Оценка времени их работы.

#include <stdio.h>
double power(int n) {
   if ( n == 0 ) return 1;
   return a * power(a, n - 1);
}

#include <stdio.h>
double power(double a, int n) {
   int i;
   double x = 1;
   for ( i = 1; i < n; i++) {
      x *= a;
   }
   return x;
}

Оба алгоритма работают динейное по n время.

#include <stdio.h>
double power(int n) {
   if ( n == 0 ) return 1;
   if ( n % 2 == 1) 
      return power(a*a, n/2); 
   else
      return a * power(a, n - 1);
}
- эта рекурсия работает время O(log n). Оценка выводится, если нарисовать цепочку рекурсивных вызовов, представляя n в двоичной системе счисления.

Проверочная работа

  1. Рассмотрим следующее рекурсивное определение f(n)=a^n: f(0) = 1; f(n) = f(n/2)^2, если n чётное; f(n) = a * f(n-1) если n нечётное. Нарисуйте дерево рекурсивных вызовов для f(100). Оцените время работы алгоритма. Напишите рекурсивную функцию, которая вычисляет f(n) согласно заданному определению.
  2. Что такое сложность вычислительной задачи?
  3. Чему равна сложность задачи сортировки n чисел?
  4. Оцените время работы алгоритма сортировки методом пузырька, рассмотренного на предыдущей лекции (с возможным досрочным завершением если не произошло ни одной операции swap) - среднее, лучшее и худшее время.

Задание на семинар

result = 1;
b = a;
ПОКА n > 0
   ЕСЛИ n нечётно
      result = result * b
   КОНЕЦ
   b = b * b;
   n = n / 2 (деление нацело без остатка);
КОНЕЦ
ВЕРНУТЬ result
Для случая n = 100, a = 2 заполните таблицу значений переменных в конце каждой итерации цикла:

номер итерации n b result
1      
2      
3      
4      
...