Void main()

{ setlocale(LC_CTYPE, "Russian");

Int rings;

cout<<"Число колец: ";

cin>>rings;

Init(rings);

Hanoi(rings, 1, 2, 3);

cout<<"Перенос колец завершен.\n";

cout<<"Число перемещений - "<<nm;

}

Рекурсия широко применяется при решении игровых и поисковых задач.

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

http://cppstudio.com/post/418/

Некоторые рекурсивные программы

Пример 1. Написать рекурсивную функцию для поиска максимального элемента в одномерном массиве:

int max (int *a, int i)

{ if (i==1) return a[1]; else if a[i]>max(a,i-1) return a[i]; else return max(a,i-1); }

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

Void convert (int z)

{ if (z>1) convert(z/8); cout<<(z % 8); }

Пример 3. Составить функцию подсчета количества x(m) разбиений натурального числа m (вводится с клавиатуры), то есть его представлений в виде суммы натуральных чисел.

P(m,n) разбиений натурального числа m со слагаемыми, не превосходящими n.

x(m)=P(m,m) - дать пояснения свойства:

P(m,1)=1 m=1+1+…+1 P(1,n)=1

P(m,n)=P(m,m) при n>m P(m,m)=P(m,m-1)+1 P(m,n)=P(m,n-1)+P(m-n,n) (n<m).

int deco (int m, int n) { if (m==1) return 1; if (n==1) return 1; if (n>m) return deco(m,m); else if (m==n) return 1+deco(m,m-1);

else return(deco(m, n-1)+deco(m-n,n)); }

Типы данных, определяемые пользователем

Это

– структуры (structure),

– объединения (union),

– перечисления (enumeration),

– битовые поля (bit fields),

– создание нового имени (псевдонима) с помощью оператора typedef для уже существующего типа.

Структуры

Структура – это составной объект (пользовательский тип данных), совокупность логически связанных данных различного типа, объединенных под одним идентификатором.

Данные называются полями.

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

Структуры полезны, когда надо объединить несколько переменных с разными типами под одним именем или сгруппировать некоторые данные, например, записи из базы данных или контакты из книги адресов и т.п.

В отличие от массива, который является однородным объектом, структура может быть неоднородной.

Элементы структуры не обязательно сохраняются в последовательных байтах памяти.

Тип структуры определяется записью вида:

struct 

{

список определений

} идентификатор;

Память при этом не выделяется.

В структуре обязательно должен быть указан хотя бы один компонент.

struct { double x, y;

} s1, s2, sm[9];

Переменные s1, s2 определяются как структуры, каждая из которых состоит из двух компонент: х и у. Переменная sm определяется как массив из девяти структур.

struct

{ int year;

char month, day;

} d1, d2;

Каждая из двух переменных d1, d2 состоит из трех компонентов year, moth, day.

Если объявление структуры не содержит имени, то переменные структурного типа могут быть объявлены только в описании структуры

Другой способ ассоциирования имени с типом структуры основан на использовании имени структуры:

struct имя_структуры

{ список описаний; };

где имя_структуры явл. идентификатором.

В привед. ниже примере идентификатор student описывается как имя структуры:

struct Student

{ char *name;

int id, age;

char pol;

} ;

Имя Student используется для последующего объявления структур:

struct Student st1, st2;

Student А[10]; //массив структур

Если есть имя, то слово struct  можно опускать.

Указатель на структуру:

Student *pstud;

Структура может быть рекурсивной:

struct Node

{ int data;

Node *next;

} st;

Структуры не могут быть прямо рекурсивными, т.е. структура Node не может содержать компоненту, являющуюся структурой Node, но любая структура может иметь компоненту, являющуюся указателем на свой тип, как и сделано в приведенном примере.

Таким образом, структуры имеют следующие свойства:

• поля структуры могут иметь разный тип;

• полями структуры могут быть функции (С++);

• структура может быть аргументом и результатом функции:

struct man *create()

{ ...

};