Laby

  • 14 февр. 2012 г.
  • 5081 Слова
Лабораторная работа №1. Рекурсивные функции

Цель работы: изучить способы реализации алгоритмов с использованием рекурсии.
1.1. Краткие теоретические сведения
Рекурсия – это способ организации вычислительного процесса, при котором функция в ходе выполнения входящих в нее операторов обращается сама к себе. Классическим примером является вычисление факториала n! (n>0)
double Faktorial_R(int n) {
if (n < 2) return 1; // Условие окончания рекурсии
else
return n* Faktorial_R (n–1); // Рекурсивное обращение к функции
}
При выполнении правильно организованной рекурсивной функции осуществляется последовательный переход от текущего уровня организации алгоритма к нижнему уровню, в котором будет получено решение задачи (в приведенном примере при n < 2), не требующеедальнейшего обращения к функции (не рекурсивное).
При описании алгоритмов используем следующие стандартные фигуры блок-схем:

1.2. Пример выполнения задания
Написать программу вычисления факториала положительного числа n, содержащую функции пользователя с рекурсией и без рекурсии.
1.2.1. Реализация задания в оконном приложении
Вид формы и полученные результаты представлены на рис. 1.1. Компонента Edit1используется для ввода n, а компоненты Edit2 и Edit3 – для вывода результатов.
Листинг программы может иметь следующий вид:
Блок-схема функции-обработчика Button1Click представлена на рис. 1.2.
. . .
double Faktorial(int);
double Faktorial_R(int);
//--------------------- Кнопка START ---------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{int n = StrToInt(Edit1->Text);
switch(RadioGroup1->ItemIndex) {
case 0:
Edit2->Text = FloatToStrF(Faktorial_R(n), ffFixed, 8, 1);
break;
case 1:
Edit3->Text = FloatToStrF(Faktorial(n), ffFixed, 8, 1);
break;
}
}
//------------------ Функция без рекурсии---------------------------------------
double Faktorial(int n) {
double f = 1;
for (int i = 1; i n;
cout kod;
switch(kod) {
case 0:
cout x. Затем массив просматривается справа – налево, пока не будет обнаружен элемент a[j].key < x. Элементы a[i] и a[j] меняются местами. Процесс просмотра и обмена продолжается до тех пор, пока i не станет больше j.В результате массив оказывается разбитым на левую часть a[L], 0  L  j с ключами меньше (или равными) x и правую a[R], iR info = in; // Формируем информационную часть
t -> next = p; // Формируем адресную часть
return t;
}
Обращение к этой функции для добавления нового элемента «а» в стек, вершиной которого является указатель begin: begin = InStack(begin, a);

Алгоритмпросмотра стека (без извлечения его элементов, т.е. без сдвига вершины)
1. Устанавливаем текущий указатель на начало списка: t = begin;
2. Начинаем цикл, работающий до тех пор, пока указатель t не равен NULL (признак окончания списка).
3. Выводим информационную часть текущего элемента t -> info на экран.
4. Текущий указатель переставляем на следующий элемент, адрес которого находится в полеnext текущего элемента: t = t -> next;
5. Конец цикла.
Функция, реализующая рассмотренный алгоритм:
void View(Stack *p) {
Stack *t = p;
while( t != NULL) {
// Вывод на экран информационной части, например, cout info Next;
}
}
Обращение к этой функции: View(begin);
Блок-схема функции View представлена на рис. 3.1.

Рис. 3.1

Функция получения информации из вершины стека cизвлечением:
Stack* OutStack(Stack* p, int *out) {
Stack *t = p; // Устанавливаем указатель t на вершину p
*out = p -> info;
p = p -> next; // Переставляем вершину p на следующий
delete t; // Удаляем бывшую вершину t
return p; // Возвращаем новую вершину p
}
Обращение к этой функции: begin = OutStack(begin, &a); информацией является переданное по адресу...
tracking img