2014-02-02
365
Рекурсивный алгоритм должен быть описан так, чтобы составляющий его рекурсивный вызов был описан в терминах более простого случая, и так, чтобы цепь рекурсивных вызовов привела к рекурсивному вызову с таким вариантом данных, при котором нет рекурсивного вызова.
Пример 2.
nod(a,b)=a, при b=0
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);
}
Пример 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);
}
Рассмотрим различные структуры рекурсивных алгоритмов:
1.Тип P(…)
{S; //Действие S выполняется до рекурсивного вызова,
If (усл) P(…); //т.е. на рекурсивном спуске.
}
2. Тип P(…)
{ //Действие S выполняется после рекурсивного вызова,
If (усл) P(…);
S; // т.е. на рекурсивном возврате.
}
3.. Тип P(…)
{S1; //S1 выполняется на рекурсивном спуске
If (усл) P(…);
S2; //S2 выполняется на рекурсивном возврате.
}
?Полезна ли рекурсия:
рекурсию можно рекомендовать,
= если данные имеют структуру, описываемую рекурсивно;
= сам алгоритм явл. по сути рекурсивным.
|
|
|
Если этого нет, то всё зависит от того,
= стремимся ли мы к эффективной программе;
= стремимся ли мы к удобству для пользователя.
Рекурсивные функции простые, наглядные и компактно записываются. Эти качества вытекают из того, рек. Функция указывает, что делать, а не рекурсивная больше ориентирует внимание на то, как делать.
С точки зрения пользователя:
= рек. Алгоритм ближе к математическому описанию, обеспечивает более простое понимание алгоритма.
= нерек. Алгоритм требует от пользователя навыков в программировании.
С точки зрения эффективности: рек. Алгоритм проигрывает,
= т.к. требует больше места и времени
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
если i<=j: {ai ó aj ; i=i+1; j=j-1; }
4шаг: если i<=j,перейти к шагу 3
Разделение на S1 и S2 выполнено
5шаг: к S1 применяется тот же метод (рекурсивно)
к S2 применяется тот же метод (рекурсивно)
//sorthoar.cpp
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
// Пример для лекции
int const ni=100;
ifstream fin;
ofstream fout;
void readm(ifstream & fin,int& k,int a[]);
void writem(ofstream &fout, int k,int a[]);
void sortH(int a[],int l, int r);
int main ()
{ int k;
int a[ni];
fout.open("rez.txt");
if(fout.fail()){cout<<"?open rez.txt";return 2;}
fin.open("dan.txt");
if(fin.fail()){cout<<"?open dan.txt";return 2;}
readm(fin,k,a);
writem(fout,k,a);
sortH(a,0,k-1);
writem(fout,k,a);
fout.close();fin.close();
return 0;
}
void readm(ifstream & fin,int & k,int a[])
{k=0;
// чтение массива
while (fin>>a[k])k++;
}
void writem(ofstream &fout,int k,int a[])
{for(int i=0;i<k;i++)
{fout<<setw(5)<<a[i];
if((i+1)%10==0)fout<<endl;
}
fout<<endl;
}
//сортировка Хоара
void sortH (int a[], int l, int r)
{ int i=l,j=r;
int x=a[(l+r)/2]; //Х – некоторый средний элемент
do //цикл разделения
{while (a[i]<x) i++;
while (a[j]>x) j--;
if (i<=j)
{int w=a[i];a[i]=a[j];a[j]=w;
i++; j --;
}
}while (i<=j);
if (l<j) sortH(a, l, j);
if (i<r)sortH(a, i, r);
}
| Dan.txt 23 54 12 45 78 24 36 71 21 35 11 22 44 55 67 | Rez.txt 23 54 12 45 78 24 36 71 21 35 11 22 44 55 67 11 12 21 22 23 24 35 36 44 45 54 55 67 71 78 |
Каждое разделение требует, очевидно, порядка п операций. Количество шагов деления (глубина рекурсии) составляет примерно log2 n, если массив делится на почти равные части. Т.О. порядок метода O(n* log2 n).
Однако возможен худший случай входных данных, когда алгоритм будет выпонняться с порядком O(n2), это происходит, если каждый раз в качестве среднего элемента выбирается минимальный или
 | |
i j
i j i j
4 3 1 6 8 9 7
j i
Ханойские башни
//hanoy.cpp
#include <fstream>
#include <iostream>
using namespace std;
ofstream fout;
int i;
void Hanoy(int n, int sour, int dest)
{if (n>0)
{int middle=6-sour-dest;
Hanoy(n-1,sour,middle);
i++;
fout<<i<<". disk "<<n<<" "<<sour<<"-->"<<dest<<endl;
Hanoy(n-1,middle,dest);
}
}
int main ()
{
int n;
fout.open("rez.txt");
if (fout.fail())
{cout<<"error open file rez.txt "<<endl; return 1;}
cout<<"--> n ";
cin>>n;
fout<<"n="<<n<<endl;
i=0;
Hanoy(n,1,3);
fout.close();
return 0;
}
