Однако все усложняется, когда нужно определить все возможные перестановки набора каких либо конкретных символов или цифр. Такой перебор называется ограниченным. В этом случае программный счетчик не поможет, так как он генерирует комбинации с повтором значений, и их нужно исключать из рассмотрения. Решение такой задачи упрощается при использовании древовидной рекурсии.
Пример 13. Написать программу, которая выводит все возможные комбинации цифр 1, 2, 3 без их повторения.
1,2,3 Þ 123,132, 213, 231, 312, 321.
Схема формирования перестановок представлена на рисунке 11.
Рисунок 11 – Схема формирования перестановок
Схема алгоритма рекурсивной подпрограммы приведена на рисунке 12.
Рисунок 12 – Схема алгоритма перестановок цифр 123
Текст программы:
#include "stdafx.h"
#include <stdio.h>
void perest(int n,int m,const int r[],int pole[])
{
int r1[3],k,i,j;
if (n==m)
{
for(i=0;i<m;i++)
printf("%2d",pole[i]);
printf("\n");
}
Else
for(i=0;i<m-n;i++)
{
pole[n]=r[i];
k=0;
for(j=0;j<m-n;j++)
if (j!=i)
{
|
|
r1[k]=r[j];
k++;
}
perest(n+1,m,r1,pole);
}
}
//Основная программа
int main(int argc, char* argv[])
{
int a[3]={1,2,3 }, pole[3];
perest(0,3,a,pole);
return 0; }
Применение ограниченного перебора может помочь уменьшить вычислительную сложность и задачи о ферзях. Попробуем сократить количество рассматриваемых вариантов за счет как можно более раннего отбрасывания неперспективных комбинаций. На рисунке 13 представлена часть дерева промежуточных и завершенных вариантов.
Рисунок - 13 Дерево вариантов расстановок
Красным отмечены комбинации, уже содержащие комбинации при которых ферзи "бьют" друг друга. Генерацию таких вариантов можно не продолжать, существенно уменьшая общее количество просматриваемых вариантов. В принципе возможна и не рекурсивная реализация данного подхода, но рассмотрим более интересный вариант с использованием рекурсии.
Для реализации программы используем две подпрограммы (см. рисунок 14). Функция new_r используется для проверки уже сгенерированной комбинации (уровень n соответствует попытке установить n-го ферзя). Процедура ferz рекурсивна. На каждом уровне она может породить до m рекурсивных вызовов (в соответствии c деревом генерации вариантов). Однако общее количество рассматриваемых вариантов резко уменьшается, что можно наглядно видеть по таблице 1.
Рисунок 14 – Схемы алгоритмов программы задачи о ферзях
Текст программы:
#include "stdafx.h"
#include <stdio.h>
#include <math.h>
// Функция проверки корректности варианта
int new_r(int n,int pole[])
{ int r=1;
for(int j=0;j<n;j++)
if((pole[j]==pole[n])|| (abs(pole[j]- pole[n])==abs(n-j)))
r=0;
return r;
}
// Функция расстановки ферзей
|
|
void ferz(int n,int m,int pole[])
{ int i;
if (n==m){
for(i=0;i<m;i++)
printf("%2d",pole[i]+1);
printf("\n"); }
else
for(i=0;i<m;i++)
{pole[n]=i;
if(new_r(n,pole)==1) ferz(n+1,m,pole);
}
}
// Основная программа
int main(int argc, char* argv[])
{
int pole[10],m;
puts("Input N");
scanf("%d",&m);
ferz(0,m,pole);
return 0;
}
Таблица 1 – Зависимость рассматриваемых вариантов от размера доски
Размер доски | Всего вариантов | Рассмотрено вариантов | Количество решений |
4*4 | 256 | 17 | 2 |
5*5 | 3125 | 54 | 10 |
6*6 | 46656 | 153 | 4 |
7*7 | 823543 | 552 | 40 |
8*8 | 16777216 | 2057 | 92 |