Однопроходные_Рекурс_Итер_ алгоритмы

Однопроходные алгоритмы

Рассмотрим класс задач, в которых входом является последовательность некоторых объектов, потенциально сколь угодно большого размера. В этот класс задач, попадают, например, следующие задачи:

•вычисление максимума (минимума) набора чисел;

•вычисление среднего арифметического набора чисел;

•упорядочивание по возрастанию чисел из данного набора;

•вычисление наибольшего общего делителя набора целых чисел;

•вычисление выпуклой оболочки набора точек на плоскости;

•вычисление медианы чисел (медиана набора чисел — это число, которое окажется в середине последовательности, если данный набор чисел упорядочить по возрастанию).

При конструировании алгоритмов для таких задач возникает естественный вопрос о том, как растёт среднее и максимальное время работы алгоритма от размера последовательности объектов, а также как растёт память, требуемая алгоритму. Для первых двух задач есть простые алгоритмы 1 и 2.

Программа 1: Однопроходный алгоритм вычисления максимума чисел

#include <stdio.h> int main () {

int i, n, a, max=0;

printf ("Введите количество чисел: ");//cout<<"Введите количество чисел: "; scanf ("%d", &n); // или в С++ cin>>n; ( используйте scanf_s в MS Studio) printf ("Введите %d чисел: ", n); //cout<<"Введите"<<n<< "чисел "; scanf ("%d", &max);

for(i = 1; i < n ; i++) { scanf ("%d", &a); if(a > max) max = a;

}

printf ("%d\n", max); // cout<<max; return 0;

}

Программа 2: Однопроходный алгоритм вычисления среднеарифметического чисел.

#include <stdio.h> int main () {

int i, n;

double a, sum = 0, mean =0; scanf ("%n", &n);

printf ("%15.10lf\n", mean); return 0;

}

ОПРЕДЕЛЕНИЕ 1. Алгоритм называется однопроходным, если каждый элемент входной последовательности считывается алгоритмом один раз и размер требуемой алгоритму памяти чётко зафиксирован, то есть не растёт с ростом размера последовательности.

Видно, что представленные алгоритмы 1 и 2 являются однопроходными. Для первого алгоритма требуется память только под переменную тax — текущее значение максимума. Bo-втором алгоритме память требуется под три переменные п (количество считанных чисел), sum (сумма считанных чисел), mean (текущее значение среднего-арифметического считанных чисел).

Обратимся к перечисленным вначале задачам. Не все из них, могут быть решены однопроходным алгоритмом. В частности, однопроходным алгоритмом не могут быть решены задачи упорядочивания (сортировки) чисел по возрастанию, вычисления выпуклой оболочки точек на плоскости и задача вычисления медианы.

Алгоритмы вычисления аn

На примере задачи вычисления f(a,n) = ап рассмотрим два принципиально различных метода конструирования алгоритмов

— итерации и рекурсия.

Первый алгоритм (Программа 3) состоит из одного арифметического цикла, тело которого выполняется п раз. В теле этого цикла переменная r, изначально равная 1, каждую итерацию домножается на а.

Программа 3: Возведение в степень (итерационный алгоритм

1)

printf ("%lf\n", power (x, n));

}}

Число итераций цикла равно п, в теле цикла выполняется элементарное действие, и поэтому время работы этого алгоритма растет пропорционально п.

Второй простой способ вычисления ап — это способ, основанный на рекурсии. Рассмотрим рекуррентное соотношение

f(а,0) = 1, f(a,n) = a · f ( a , n - 1 ) .

Оно задает функцию f(a, п) = ап. На основе этого соотношения можно написать рекурсивный алгоритм 4.

Программа 4: Возведение в степень (рекурсивный алгоритм

Рекурсивный вызов — это элементарная операция. Если считать, что операция умножения также элементарна, то время работы рекурсивного алгоритма пропорционально п.

Существуют ли более оптимальные алгоритмы, чем два представленных? Да, существуют. В частности, если п является степенью двойки, то ап можо получить последовательно возводя в квадрат зачение переменной r, изначально равной а:

aÆ a2 Æ a4Æ a8Æ a16 Æ a32Æ

Вчастности, по этой цепочке всего за 10 шагов можно получить а1024. Эту идею можно воплотить в более оптимальный рекурсивный алгоритм 5, 6 для произвольного значения п (не только для степеней двойки). Алгоритм основан на рекурентном соотношении

Программа 5: Возведение в степень (рекурсивный алгоритм способ 2)

Программа 6: Возведение в степень (итерационный алгоритм способ 2)

double power(double a, long n) { double b = a;

double r = 1; while(n != 0) {

if(n % 2 == 1) r *= b; b *= b;

n/= 2;

}

return r;}

Алгоритмы вычисления чисел Фибоначчи

Последовательность Фибоначчи 1, 1, 2, 3, 5, 8, 13, ..., определяемая следующими соотношениями

F0 =1, F1 =1, F1 = Fn-1 + Fn-2

При n > 1 числа Фибоначчи определяются рекурсивно, то есть через другие числа Фибоначчи, а при п = 1 и п = 0 они по определению равны 1.

Программа 7: Числа Фибоначчи (рекурсивный алгоритм)

#include<stdio.h> int fib(int n) {

if(n <= 1) return 1;

return fib(n-l)+fib(n-2); // 4} int mainO {

int n;

scanf ("%d", &n); printf ("%d \n", fib(n)); return 0;}

Давайте посчитаем, сколько операций сложения (строка 4) будет осуществлено при вычислении числа Фибоначчи F50.

При вычислении F0 и F1 строка 4 не выполняется и число операций сложения равно 0. При вычислении F2 осуществляется одно сложение. При вычислении F3 осуществляется два сложения. Обозначим число операций сложения при вычислении Fn как Gn. Тогда G0 = G1 = 0, G2 = I, G3 = 2, .... Несложно увидеть, что выполняется следующее рекуррентное соотношение:

Gn = Gn-1 + Gn-2 + 1.

Последовательно вычисляя первые 50 чисел, получим G50 = 20365011073. Эта последовательность растёт достаточно быстро, в частности, G100 º 5.7 • 1020. Можно показать, что Gn растёт примерно как ап, где а = (◊5+l)/2º 1.61803.

Время, необходимое описанному рекурсивному алгоритму, примерно пропорционально вычисляемому числу Фибоначчи. Это следует из того, что число Фибоначчи Fn в рекурсивном алгоритме получается в результате сложения Fn единиц. Необходимое число операций сложения Gn ровно на 1 меньше самого числа Fn.

Поэтому даже на мощном компьютере с помощью этого алгоритма нам не удастся вычислить больше, чем первые несколько десятков членов последовательности Фибоначчи. Вы, наверное, уже догадываетесь, в чём здесь проблема. В нашей программе очень много избыточных вызовов — в дереве рекурсивных вызовов много повторений. Например fib(n-2) будет вызвана два раза: сначала из fib (n), а потом из fib(n-1), и оба раза будут проводится одни и те же вычисления. Простой «человеческий» алгоритм вычисления чисел Фибоначчи работает существенно быстрее: нужно помнить последние два числа Фибоначчи, вычислять следующее число и повторять этот шаг нужное число раз.

Программа 8: Числа Фибоначчи (итерационный алгоритм)

Логика работы алгоритма 8 заключается в следующем: в переменных а и b хранятся последние вычисленные числа Фибоначчи. На каждой итерации вычисляется следующее число Фибоначчи (переменная с) и происходит обновление значений а и b.

Алгоритм 8 вычисления Fn выполнит п-2 итераций цикла for. Соответственно время работы этого алгоритма растёт линейно с п. Как мы видим, данный нерекурсивный алгоритм оказался существенно менее эффективным (дольше работающем при больших п) нежели рекурсивный алгоритм.

Но это не значит, что использовать рекурсию не надо. От экспоненциального роста времени вычисления рекурсивных алгоритмов легко избавится с помощью запоминания вычисленных значений. А именно, в памяти хранят вычисленные значений, а в начале функции помещается проверка на то, что требуемое значение уже вычислено и хранится в памяти. Если это так, то это значение возвращается как результат, а вычисления и рекурсивные вызовы осуществляются лишь в том случае, когда функция с такими аргументами ещё ни разу не вызывалась. Подробнее этот метод мы рассмотрим при изучении динамического программирования.

Анализ рекурсивного алгоритма вычисления чисел Фибоначчи Задание 1. Запустите программу 9. Найдите рекуррентную

формулу для количества вызовов функции fib (fib_calls). Измените программу так, чтобы она считала количество вызовов функции fib с аргументом 1 или 0.

Напишите программу, которая ищет отношение fib_calls(n+l)/fib_calls(n). Измените тип переменной count на double.

Программа 9. Анализ рекурсивного алгоритма вычисления чисел Фибоначчи

#include<stdio.h>

int count = 0; // глобальная переменная int fib(int n) { count++; if(n <= 1) return 1;

return fib(n-l)+fib(n-2); } int main( ) {

int n; // локальная переменная функции main for(n = 0 ; n < 20; n++) {

count = 0;

printf("F(%2d) = %8d ", n, fib(n));

printf ("fib_calls(%2d) = %8d\n", n, count);

}return 0; }

Задача 1. Изучите программы 1 и 2. Напишите программу, которая находит минимальное, максимальное, среднее арифметическое и среднее квадратичное введённых действительных чисел (используйте тип double) и располагает эти четыре числа в порядке возрастания.

Задача 2. Напишите программу, реализующую однопроходный алгоритм вычисления 4-х самых больших различных чисел из данного набора чисел.

Задача 3. Любое число можно представить в виде суммы неповторяющихся чисел Фибоначчи. Более того, можно сделать так, что в этой сумме отсутствуют пары соседних чисел Фибоначчи. Задача: представить введённое число п в виде такой суммы. Пример входа/выхода:

Вход: 25

Выход: 21+3+1

Задача 4. Различаются ли результат и скорость работы следующих двух функций?

double fl(unsigned int n) { if(n==0) return 0; if(n==l) return 0.1;

return 1.9*fl(n - 1) - 0.95*fl(n - 2); } double f2(unsigned int n) {

if(n==0) return 0; if(n==l) return 0.1;

return 0.95*f2(n - 1) + 0.95*(f2(n - 1) - f2(n - 2)); }

Реализуйте идею «рекурсии с запоминанием», а имено, объявите глобальные массивы «double fdata[1000]» и «int is_calculated[1000]»

и инициализируйте массив is_calculated. нулями. Запоминайте вычисленные значения функции в глобальном массиве fdata. Определение фунции f может выглядеть так:

is_calculated[n] = 1; return result; } }

Сравните время вычисления f (50) и fl(50). Объясните результат сравнения.