Рекурсивные процедуры

Ссылки и многомерные массивы

Для решения одних и тех же задач можно использовать многомерные массивы и массивы указателей. Для простоты сравнения возьмем двумерный массив и одномерный массив указателей. Пусть имеем следующие определения:

short a[10][10];

short *b[10];

и пусть оба массива используются аналогичным образом, т.е. a[5][5] и b[5][5] допустимые обращения к одному и тому же целому значению. Тогда под массив a будет выделена память размером в 100 целых значений (200 байтов), а под массив b – размером в 10 указателей типа short. Если каждая ссылка массива b указывает на массив из 10 целых, то потребная память для решения составит: 100 целых + 10 указателей на short. Кроме того, необходимо будет динамически выделять память под массив. Однако, не требуется вычислять адрес элемента двумерного массива, а можно обратиться прямо по ссылке.

Второе преимущество: каждый элемент массива ссылок может указывать на на массив, количество элементов которого может быть произвольным, т.е. с его помощью можно реализовать так называемые непрямоугольные массивы, содержащие разное число элементов в младших измерениях. Обычно это используют при работе с массивами строк (string). См. пример "Инициализация массива ссылок".

Пример. Вывод сообщений в окна.

#include <conio.h>

#define Screen BLACK

void message(short nom, // Номер сообщения

short reg){ // Режим: 1-вывод сообщения, 0-очистить окно

static struct mes{ // Описание сообщения

short beg_x, // Начальная позиция окна по x

beg_y, // Начальная позиция окна по y

end_x, // Конечная позиция окна по x

end_y, // Конечная позиция окна по y

regim; // Режим вывода текста: 'r' – с разрядкой, 'p' - плотный

char *text; // Текст сообщения

} def[ ]={ // Инициализация списка сообщений

28, 2, 54, 4, 'r', "ВВОД ДАННЫХ",

19, 12, 61, 14, 'p', "Имя файла входных данных",

.

.

.

19, 12, 61, 14, 'r', "ВВОД ДАННЫХ ЗАКОНЧЕН"

};

struct mes *p; // Указатель на элемент списка

p = &def[nom-1];

if (reg){ // Вывод сообщения в окно

init_window(p->beg_x, p->beg_y, p->end_x, p->end_y,

BLACK, LIGHTGRAY, 1);

out_text(2, 2, 200, p->regim, p->text);

} else { /* Очистка окна */

clear_window(p->beg_x, p->beg_y, p->end_x, p->end_y, Screen);

}

} /* End message */

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

Пример. Вычислить n!=n*(n-1)!.

short factorial(short n){

short fact;

if (n == 0){ // Условие завершение рекурсии

return 1;

} else {

fact = n * factorial(n – 1);

}

return fact;

}

Рекурсия реализуется с помощью рассмотренной выше структуры данных – стека. При этом не предусматриваются никакие механизмы защиты памяти, вследствие чего при неправильном программировании терминальной ветви рекурсивного алгоритма (см. пример выше) автоматически выделяемая память под каждый рекурсивный вызов (программный стек) будет переполняться и вызывать прерывание программы во время выполнения (run time error) с сообщением stack overflow (переполнение стека).

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

Пример. "Ханойская башня".

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

Требуется: переместить башню с одной площадки на другую с соблюдением следующих условий:

- за 1 раз переносится 1 диск;

- нельзя ставить диск большего диаметра на диск меньшего диаметра;

- можно использовать только одну резервную площадку.

Рисунок ниже иллюстрирует процесс решения для n=2 и n=3.

n=2 n=3

Площ. 1 Площ. 2 Площ. 3 Площ. 1 Площ. 2 Площ. 3

В соответствии с рисунком рекурсивное решение для n=3 записывается так:

hanoi(1, 3, 2)

hanoi(1, 2, 3) = 1à 2

hanoi(3, 2, 2)

Для произвольного n и произвольных номеров площадок от 1 до 3 получим:

hanoi(a, 6-a-b, n-1)

hanoi(a, b, n) = a à b

hanoi(6-a-b, b, n-1)

Здесь:

- a - № начальной площадки,

- b - № конечной площадки,

- n – число дисков в башне.

В общем случае для решения задачи требуется 2ⁿ -1 операций переноса дис-

ков. Решение представляется в выводе на экран последовательности номеров начальной и конечной площадок. Для n=4 решение имеет вид:

1 à 3 1 à 2 3 à 2 1 à 3 2 à 1 2 à 3 1 à 3 1 à 2 3 à 2 3 à 1 2 à 1 3 à 2

1 à 3 1 à 2 3 à 2

Дата добавления: 2014-12-27