2015-10-22
492
Float angle, int n)
{
float k = 0.7, x1, y1;
x1 = x + L*cos(angle); // координаты второго конца
y1 = y - L*sin(angle);
Line (x, y, x1, y1); // рисуем ствол
if (n <= 1) return; // все нарисовали, выход
Pifagor(x1, y1, k*L, angle+M_PI_4, n-1); // рекурсивные
Pifagor(x1, y1, k*L, angle-M_PI_4, n-1); // вызовы
}
Основная программа выглядит примерно так же, как и в предыдущем примере.
Перебор вариантов
Одна из главных практически важных областей, где применение рекурсии значительно
упрощает решение – задачи на перебор вариантов.
Сочетания
Необходимо получить все возможные сочетания чисел от 1 до K, которые имеют длину N
(в последовательности могут быть одинаковые элементы). Для решения задачи выделим в памяти массив A[N]. Представим себе, что все его первые q элементов (с номерами от 0 до q-1) уже определены, и надо найти все сочетания, при которых эти элементы не меняются.
Сначала ставим на место элемент с номером q. По условию на этом месте может стоять
любое число от 1 до K, поэтому сначала ставим 1 и находим все варианты, при которых q+1
элементов уже поставлены (здесь будет рекурсивный вызов), затем ставим на это место 2 и т.д.
Если q=N, то все элементы уже поставлены на место, и надо печатать массив –одна из нужных
комбинаций готова. Ниже приведена рекурсивная процедура, которая использует массив A[N]
и печатает все комбинации на экране.
void Combinations (int A[], int N, int K, int q)
{
if (q == N) // одна комбинация получена
PrintData (A, N);
Else
for (int i = 1; i <= K; i ++) {
A[q] = i;
Combinations(A, N, K, q+1); // рекурсивныйвызов
}
}
Для вывода массива на экран используется такая процедура:
void PrintData (int Data[], int N)
{
for (int i = 0; i < N; i++)
printf("%2d ", Data[i]);
printf("\n");
}
В основной программе надо вызвать процедуру с параметром q = 0, поскольку ни один элемент
еще не установлен:
#include <stdio.h>
// здесь надо разместить процедуры
Main()
{
int A[5], N = 5, K = 10;
Combinations (A, N, K, 0);
}
Перестановки
Существует еще одна весьма непростая задача, которая хорошо решается с помощью ре-
курсии. Представьте, что к вам пришли N гостей. Сколько существует различных способов рассадить их за столом?Сформулируем условие задачи математически. В массиве A[N] записаны целые числа.Надо найти все возможные перестановки этих чисел (в перестановку должны входить все элементы массива по 1 разу)Как и в предыдущем примере, предположим, что q элементов массива (с номерами от 0 до q-1) уже стоят на своих местах. Тогда в позиции q может стоять любой из неиспользованных элементов – их надо перебрать в цикле и вызвать рекурсивно эту же процедуру, увеличив на 1 количество установленных элементов. Чтобы не потерять никакой элемент, в цикле для
всех i от q до N-1 будем переставлять элементы A[i] и A[q], генерировать все возможные
комбинации, а затем менять их местами, восстанавливая исходный порядок.
Для обмена местами двух элементов массива будем использовать вспомогательную пере-
менную temp.
void Permutations (int A[], int N, int q)
{
int temp;
if (q == N) // перестановка получена
