2014-02-02
407
Рекурсивный алгоритм должен быть описан так, чтобы составляющий его рекурсивный вызов был описан в терминах более простого случая, и так, чтобы цепь рекурсивных вызовов привела к рекурсивному вызову с таким вариантом данных, при котором нет рекурсивного вызова.
Пример 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);
}
Рассмотрим различные структуры рекурсивных алгоритмов:
1.Тип P(…)
{S; //Действие S выполняется до рекурсивного вызова,
If (усл) P (…); //т.е. на рекурсивном спуске.
}
2. Тип P(…)
{ //Действие S выполняется после рекурсивного вызова,
If (усл) P(…);
S; // т.е. на рекурсивном возврате.
}
3.. Тип P(…)
{S1; //S1 выполняется на рекурсивном спуске
If (усл) P(…);
S2; //S2 выполняется на рекурсивном возврате.
}
?Полезна ли рекурсия:
рекурсию можно рекомендовать,
= если данные имеют структуру, описываемую рекурсивно;
= сам алгоритм явл. по сути рекурсивным.
Если этого нет, то всё зависит от того,
= стремимся ли мы к эффективной программе;
= стремимся ли мы к удобству для пользователя.
|
|
|
Рекурсивные функции простые, наглядные и компактно записываются. Эти качества вытекают из того, рек. Функция указывает, что делать, а не рекурсивная больше ориентирует внимание на то, как делать.
С точки зрения пользователя:
= рек. Алгоритм ближе к математическому описанию, обеспечивает более простое понимание алгоритма.
= нерек. Алгоритм требует от пользователя навыков в программировании.
С точки зрения эффективности: рек. Алгоритм проигрывает,
= т.к. требует больше места и времени
= отладка рекурсивной функции затруднительна.
Пример 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)
Метод решения задач “Разделяй и властвуй”
Идея: задачу разделяют на части, находят решение для каждой подзадачи и из этих решений составляют решение всей задачи. Рекурсивное описание часто приводит к эффективному решению задачи.
Пример 4.
Алгоритм «Быстрая сортировка Хоара» разработан в 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шаг: do // Цикл разделения
{ Пока ai < x: i=i+1
Пока aj > x: j=j-1
если i<=j: {ai ó aj ; i=i+1; j=j-1; }
если i<=j,перейти к шагу 3
} Разделение на S1 и S2 выполнено
4 шаг: к 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 |
Каждое разделение требует, очевидно, порядка n операций. Количество шагов деления (глубина рекурсии) составляет приблизительно log 2 n, если массив делится на почти равные части. Таким образом, общее быстродействие: O(n log2 n), что и имеет место на практике.
Однако возможен случай таких входных данных, на которых алгоритм будет работать за O(n2) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге... Вообще говоря, малореальная ситуация.
Метод неустойчив. Поведение довольно естественно, если учесть, что при частичной упорядоченности повышаются шансы разделения массива на более равные части.
 | |
i j
i j i j
4 3 1 6 8 9 7
j i
Ханойские башни
sour middle dest
Сведем задачу с n дисками к задаче с n – 1 дисками (фактически, применим метод математической индукции по числу дисков). Пусть нам требуется переложить пирамиду из дисков со штыря с номером 1 (sour) на штырь с номером 3 (dest), используя штырь 2(work) в качестве вспомогательного. Для этого необходимо сначала переложить пирамиду из n – 1 диска со штыря 1 на штырь 2, используя штырь 3 в качестве вспомогательного. Затем переместить оставшийся диск со штыря 1 на штырь 3 и, наконец, переложить пирамиду из n – 1 диска со штыря 2 на штырь 3 используя штырь 1 в качестве вспомогательного.
//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;
}
