"Ханойские" башни.

/*
Легенда гласит, что где-то в Ханое находится храм, в котором размещена следующая конструкция:
на основании укреплены 3 алмазных стержня, на один из которых при сотворении мира Брахма
нанизал 64 золотых диска с отверстием посередине, причем внизу оказался самый большой диск,
на нем – чуть меньший и так далее, пока на верхушке пирамиды не оказался самый маленький диск.
Жрецы храма обязаны перекладывать диски по следующим правилам:

1. За один ход можно перенести только один диск.

2. Нельзя класть больший диск на меньший.

Руководствуясь этими нехитрыми правилами, жрецы должны перенести исходную пирамиду с 1-го стержня на 3-й.
Как только они справятся с этим заданием, наступит конец света.

Мы предлагаем Вам решить данную задачу с помощью рекурсии.
*/

//Решение взято с vk.com.

void hanoi_towers(int quantity, int from, int to, int buf_peg)
//quantity-число колец, from-начальное положение колец(1-3),to-конечное положение колец(1-3)
{

//buf_peg - промежуточный колышек(1-3)
if (quantity != 0)
{

hanoi_towers(quantity-1, from, buf_peg, to);

cout << from << " -> " << to << "\n";
hanoi_towers(quantity-1, buf_peg, to, from);

}

}

void main()
{

setlocale(LC_ALL, "Russian");
int start_peg, destination_peg, buffer_peg, plate_quantity;
cout << "\nНомер первого столбика:";
cin >> start_peg;
cout << "\nНомер конечного столбика:";
cin >> destination_peg;
cout << "\nНомер промежуточного столбика:";
cin >> buffer_peg;
cout << "\nКоличество дисков:";
cin >> plate_quantity;
cout<<"\n";

hanoi_towers(plate_quantity, start_peg, destination_peg, buffer_peg);

}

Написать функцию, которая находит максимальное значение в массиве, используя рекурсию

int max(int A[], int size)
{

if(size==1) return A[0];
else
{

int tmp=max(A,size-1);
return tmp>A[size-2]?tmp:A[size-2];

}

}

void init(int A[], int size)
{

srand(time(NULL));
for (int i = 0; i < size; i++)

A[i] = rand() % 20+1;

}

void out(int A[], int size)
{

cout << "\n";
for (int i = 0; i < size; i++)

cout << A[i] << " ";

cout << "\n";

}

void main()
{

setlocale(LC_ALL, "Russian");
int digit;
const int size=15;
int A[size];

do
{

cout<<"Эта программа находит максимальное значение в массиве, используя рекурсию\n";
init(A,size);
out(A,size);
cout<<"\nМаксимальное значение - "<<max(A,size)<<"\n";
cout<<"Если хотите продолжить, нажмите 1:";
cin>>digit;

}while(digit==1);

}

Пример на рекурсию

long int Fact(long int N)
{

// если произведена попытка вычислить факториал нуля
// или единицы - вернуть 1,
// именно здесь произведется выход из рекурсии
if (N == 1 || N == 0) return 1;
// любое другое число вызывает функцию заново с формулой N-1
else return N * Fact(N-1);

}

void main()
{

long number=5;
//первый вызов рекурсивной функции
long result=Fact(number);
cout<<"Result "<<number<<"! is - "<<result<<"\n";

}

Двоичный поиск

int BinarySearch (int A[], int Lb, int Ub, int Key)
{

int M;
while(1)
{

M = (Lb + Ub)/2;
if (Key < A[M])

Ub = M - 1;

else
if (Key > A[M])

Lb = M + 1;

else

return M;

if (Lb > Ub)

return -1;

}

}

void main()
{

srand(time(NULL));
const long SIZE=10;
int ar[SIZE];
int key,ind;

// до сортировки
for(int i=0;i<SIZE;i++)
{

ar[i]=rand()%100;
cout<<ar[i]<<"\t";

}
cout<<"\n\n";
cout<<"Enter any digit:";
cin>>key;
ind=BinarySearch(ar,0,SIZE,key);
cout<<"Index - "<<ind<<"\t";
cout<<"\n\n";

}

Быстрая сортировка

template <typename T>
void quickSortR(T a[], int B, int E)
{

long i = B, j = E;
T temp, p;
p = a[(B+E)/2];
do
{

while ( a[i] < p ) i++;
while ( a[j] > p ) j--;
if (i <= j)
{

temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;

}

}while ( i<=j );
if(B<j)quickSortR(a, B, j);
if(i<E)quickSortR(a, i, E);

}

void main()
{

srand(time(NULL));
const long SIZE=10;
int ar[SIZE];
// до сортировки
for(int i=0;i<SIZE;i++){

ar[i]=rand()%100;
cout<<ar[i]<<"\t";

}
cout<<"\n\n";
quickSortR(ar,0,SIZE-1);
// после сортировки
for(int i=0;i<SIZE;i++){

cout<<ar[i]<<"\t";

}
cout<<"\n\n";

}

Написать функцию, которая рекурсивно вычисляет сумму чисел в заданном диапазоне.

int summ(int a, int b)
{

return (a==b)?b:a + summ(a+1,b);

}

void main()
{

setlocale(LC_ALL, "Russian");
int begin, end;
do
{

cout<<"Эта программа считает сумму чисел в заданном диапазоне\n";
cout<<"\nВведите начало диапазона:";
cin>>begin;
cout<<"\nВведите конец диапазона:";
cin>>end;
cout<<"Сумма от "<<begin<<" до "<<end<<" равна "<<summ(begin,end)<<"\n";
cout<<"Если хотите продолжить, нажмите 1:";
cin>>begin;

}while(begin==1);

}