Читайте также:
|
a, при b=0
nod(a,b)= nod(b, a%b), при b!=0
Unsigned int nod (unsigned int a,unsigned int b)
{if (b==0)return a;
return nod(b, a%b);
}
Рассмотрим различные структуры рекурсивных алгоритмов:
1.Тип P(…)
{S; //Действие S выполняется до рекурсивного вызова,
If (усл) P(…); //т.е. на рекурсивном спуске.
}
2. Тип P(…)
{ //Действие S выполняется после рекурсивного вызова,
If (усл) P(…);
S; // т.е. на рекурсивном возврате.
}
3.. Тип P(…)
{S1; //S1 выполняется на рекурсивном спуске
If (усл) P(…);
S2; //S2 выполняется на рекурсивном возврате.
}
?Полезна ли рекурсия:
рекурсию можно рекомендовать,
= если данные имеют структуру, описываемую рекурсивно;
= сам алгоритм явл. по сути рекурсивным.
Если этого нет, то всё зависит от того,
= стремимся ли мы к эффективной программе;
= стремимся ли мы к удобству для пользователя.
Рекурсивные функции простые, наглядные и компактно записываються. Эти качества вытекают из того, рек. Функция указывает, что делать, а не рекурсивная больше ориентирует внимание на то, как делать.
С точки зрения пользователя:
= рек. Алгоритм ближе к математическому описанию, обеспечивает более простое понимание алгоритма.
= нерек. Алгоритм требует от пользователя навыков в программировании.
С точки зрения эффективности: рек. Алгоритм проигрывает,
= т.к. требует больше места и времени См. рек алгоритм fib().
= отладка рекурсивной функции затруднительна
Пример 3.Числа Фибоначчи f n =1, при n=1 || n=2; f n = f n-1 + f n-2, при n>2
Int fib(int n)
{if (n==1||n==2)return 1;
return fib(n-1)+ fib(n-2);
}
Fib(7)
Fib(6) fib(5)
Fib(5) Fib(4) Fib(4) Fib(3)
Fib(4) Fib(3) Fib(3) Fib(2) Fib(3) Fib(2) Fib(2) Fib(1)
Fib(3) Fib(2)
Fib(2) Fib(2) Fib(2) Fib(1)
Fib(1) Fib(1) Fib(1) Fib(2)
Метод решения задач “Разделяй и властвуй”
Идея: задачу разделяют на части, находят решение для каждой подзадачи и из этих решений составляют решение всей задачи. Рекурсивное описание часто приводит к эффективному решению задачи.
Алгоритм «Быстрая сортировка Хоара» разработан в 1962г. профессором Оксфордского университета Хоаром.
Идея основана на принципе обмена: для достижения б’ольшей эффективности обмениваются элементы, стоящие на больших расстояниях.
Основная идея Хоара:
Совокупность {a0, a1, a2,.... an-1 } разделяется на две совокупности S1 и S2: в S1 все элементы не больше некоторого среднего значения, а в S2 – не меньше этого среднего значения, затем к каждой из этих частей применяется тот же метод.
Схема алгоритма
1шаг:L=0; r=n-1;
I=L; j=r;
2шаг: выбор среднего элемента
x=am; где m=(L+r)/2;
3шаг: Цикл разделения
Пока ai < x: i=i+1
Пока aj > x: j=j-1
ai ó aj ; i=i+1; j=j-1;
4шаг: если i<=j,перейти к шагу 3
Разделение на S1 и S2 выполнено
5шаг: к S1 применяется тот же метод (рекурсивно)
к S2 применяется тот же метод (рекурсивно)
I j
I j i j
4 3 1 6 8 9 7
j i
//sorthoar.cpp
#include <iostream>
#include <fstream>
#include <iomanip>
Дата добавления: 2014-12-20; просмотров: 93 | Поможем написать вашу работу | Нарушение авторских прав |