Калейдоскоп из комбинаторных алгоритмов

Автоматическое построение лабиринтов

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

Здесь не представляется возможным описать все мыслимые лабиринты, да это и не требуется. Мы займемся простыми лабиринтами, построенными на прямоугольнике $$m\times n$$, где $$m,n$$ — положительные целые числа. Внутри и на границах прямоугольника поставлены стенки по ребрам покрывающей его единичной квадратной сетки. Чтобы построить из прямоугольника лабиринт, выбьем одну единичную стенку на одной из сторон прямоугольника (получится вход в лабиринт); выбьем одну единичную стенку на противоположной стороне (получится выход) и еще удалим какое-то число строго внутренних стенок. Говорят, что лабиринт имеет решение, если между входом и выходом внутри лабиринта есть путь в виде ломаной, не имеющей общих точек со стенками. Решение единственно, если любые два таких пути проходят через одни и те же внутренние ячейки сетки. На рис. 17.1 приведен пример лабиринта $$5\times 5$$.

Один из возможных подходов к решению таков. Выбираем вход; затем, начав от него, добавляем по одной ячейке к главному пути-решению, пока он не достигнет выходной стороны. После этого удаляем некоторые внутренние стенки так, чтобы все клетки оказались соединенными с главным путем. Чтобы главный путь не получился прямым коридором, следует при его построении предусмотреть случайные повороты. Программа должна также следить за тем, чтобы при построении главного пути или при открытии боковых ячеек не нарушалась единственность решения. Наблюдательный читатель заметит, что определение единственности решения не годится в случае, когда путь заходит в боковой тупик и затем возвращается.

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

Программа 1. Лабиринт.

{Программно задаются вход и выход. Нажимая на клавишу "Enter",
перебираем  всевозможные пути от входа до выхода в лабиринте.
Выход из программы по клавише "Esc".
Алгоритм реализован на языке программирования Turbo-Pascal}

program Maze;
uses
  Graph, Crt;

var
  m,n: Integer;
  Matrix: array [1..100,1..100] of Boolean;
  Start,Finish: Integer;

procedure PrepareGraph;
var
  Driver,Mode: Integer;
begin
  Driver:=VGA;
  Mode:=VGAHi;
  InitGraph(Driver,Mode,'c:\borland\tp\bgi');
end;

procedure DisplayMaze(x1,y1,x2,y2: Integer);
var
  i,j: Integer;
  dx,dy: Real;
begin
  SetFillStyle(1,8);
  SetColor(15);
  dx:=(x2-x1)/m;
  dy:=(y2-y1)/n;
  for i:=1 to n do
    for j:=1 to m do
      if not Matrix[i,j] then
        Rectangle(Round(x1+(i-1)*dx),Round(y1+(j-1)*dy),
        Round(x1+i*dx),Round(y1+j*dy));
end;

function CreatesPath(i,j: Integer): Boolean;
var
  Result: Boolean;
  Count: Integer;
  ii,jj: Integer;
begin
  Count:=0;
  if (i>1) and Matrix[i-1,j] then Inc(Count);
  if (i<m) and Matrix[i+1,j] then Inc(Count);
  if (j>1) and Matrix[i,j-1] then Inc(Count);
  if (j<m) and Matrix[i,j+1] then Inc(Count);
  if Count>1 then Result:=true else Result:=false;
  CreatesPath:=Result;
end;

function DeadEnd(i,j: Integer): Boolean;
var
  Result: Boolean;
  Count: Integer;
begin
  Count:=0;
  if (i=2) or CreatesPath(i-1,j) then Inc(Count);
  if (i=m-1) or CreatesPath(i+1,j) then Inc(Count);
  if (j=2) or CreatesPath(i,j-1) then Inc(Count);
  if (j=n-1) or CreatesPath(i,j+1) then Inc(Count);
  if Count=4 then Result:=true else Result:=false;
  DeadEnd:=Result;
end;

function CreateMaze: Boolean;
var
  i,j: Integer;
  di,dj: Integer;
  Result: Boolean;
begin
  Randomize;
  for i:=1 to n do
    for j:=1 to m do Matrix[i,j]:=false;
  Start:=Random(m-2)+2;
  i:=Start;
  j:=2;
  Matrix[Start,1]:=true;
  repeat
    Matrix[i,j]:=true;
    di:=0;
    dj:=0;
    while (di=0) and (dj=0) do begin
      di:=1-Random(3);
      if (i+di=1) or (i+di=m) then di:=0;
      if di=0 then dj:=1-Random(3);
      if j+dj=1 then dj:=0;
      if CreatesPath(i+di,j+dj) then begin
        di:=0;
        dj:=0;
      end;
    end;
    i:=i+di;
    j:=j+dj;
  until DeadEnd(i,j) or (j=n);
  Finish:=i;
  Matrix[Finish,n]:=true;
  if j<n then Result:=false else Result:=true;
  CreateMaze:=Result;
end;

begin
  m:=6;
  n:=6;

PrepareGraph;
  repeat
    ClearDevice;
    repeat until CreateMaze;
    DisplayMaze(120,40,520,440);
    repeat until KeyPressed;
  until ReadKey=#27;
  CloseGraph;
end.

Программа 2. Лабиринт.

{Лабиринт реализуется автоматически, без участия пользователя.
Алгоритм реализован на языке программирования  Turbo-Pascal }
uses graph,crt;
var
mpos,npos,m,n,delx,x,y,t,gd,gm,i,k:integer;

begin
randomize;
writeln('Input labyrint size (x and y)');
readln(m,n);
writeln('Input entranceexit coordinates (mpos<m and npos<m)');
readln(mpos,npos);
initgraph(gd,gm,'c:\borland\tp\bgi');
for i:=1 to m do
begin
for k:=1 to n do
begin
rectangle(90+10*i,90+10*k,90+10*i+10,90+10*k+10);
end;
end;
setfillstyle(1,0);
setcolor(0);
line(100+(mpos-1)*10+1,100,100+(mpos-1)*10+9,100);
line(100+(npos-1)*10+1,100+n*10,100+(npos-1)*10+9,100+n*10);
y:=n;
x:=npos;
readln;

while y>1 do
begin
delx:=random(m)-x+1;
if y=2 then delx:=mpos-x;
i:=91+x*10;
 if i<90+(x+delx)*10 then
 begin
  while i<>90+(x+delx)*10 do
   begin
    i:=i+1;
    line(i,91+y*10,i,99+y*10);
   end;
 end;

if i>91+(x+delx)*10 then
 begin
  while i<>91+(x+delx)*10 do
   begin
    i:=i-1;
    line(i,91+y*10,i,99+y*10);
   end;
 end;

x:=x+delx;
line(91+10*x,90+y*10,99+10*x,90+y*10);

y:=y-1;

end;

readln;
end.

Бинарное дерево

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

Программа 3. Поиск максимального элемента.

{ Алгоритм реализован на языке программирования Turbo-Pascal}
uses crt;
type sp=^tree;
tree=record
     val:integer;
     l:sp;
     r:sp;
     end;
var
 t:sp;
 nh, max,h,i:integer;
procedure find(t:sp; h,nh:integer);
  begin
    if t=nil then exit;
    if h=nh then
      begin
         if t^.val> max then max:=t^.val;
      end
    else
      begin
        find(t^.l,h+1,nh);
        find(t^.r,h+1,nh);
      end;
end;
procedure zadtree(var t:sp; h,nh:integer);
  begin
    if h=5 then
     begin
       new(t);
       t^.l:=nil;
       t^.r:=nil;
       t^.val:=random(100);
     end
   else
    begin
      new(t);
      zadtree(t^.l, h+1,nh);
      zadtree(t^.r, h+1,nh);
      t^.val:=random(100);
   end;
end;
procedure writetree(t:sp; h,nh:integer);
begin
  if t=nil then exit;
  if h=nh then
    begin
        write(t^.val,' ');
    end
  else
    begin
       writetree(t^.l,h+1,nh);
       writetree(t^.r,h+1,nh);
    end;
end;
begin
  clrscr;
  randomize;
  t:=nil;
  zadtree(t,1,nh);
  for i:=1 to 5 do
   begin
     writetree(t,1,i);
     writeln;
   end;
  max:=0;
  write('vvedite uroven ');
  readln(nh);
  find(t,1,nh);
  write('max= ',max);
readln;
end.

Задача о восьми ферзях

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

Анализ задачи. Пусть $$A$$ - множество искомых расстановок (конфигураций). Рассмотрим следующий подход к решению задачи. Будем искать множество конфигураций $$B$$ со следующими свойствами:

С помощью процедуры из пункта 3 будем генерировать по очереди все элементы из $$B$$ ; для элементов из $$B$$ проверяем (см. пункт 2) принадлежит ли он $$A$$: в результате в силу 1 свойства будут порождены все элементы $$A$$.

Заметим теперь, что ферзи, которые не бьют друг друга, должны располагаться на разных горизонталях. Поэтому можно упорядочить ферзи и всегда ставить $$k$$ -го ферзя на $$k$$ -ю горизонталь. Тогда в качестве $$B$$ можно взять множество конфигураций, в которых на каждой из первых $$N$$ горизонталей стоит ровно по одному ферзю, причем никакие два ферзя не бьют друг друга.

Программа 4. Расстановка восьми ферзей на шахматной доске.

{ Программа выдает все комбинации ферзей, которые не бьют друг друга.
Алгоритм реализован на языке программирования Turbo-Pascal }
program ferz;
uses crt;
const desksize=8;
type sizeint=1..desksize;
     unuses=set of sizeint;
     combinates=array[shortint] of sizeint;
var num:byte;
    combinate:combinates;
    unuse:unuses;

function attack(combinate:combinates):boolean;
var i,j:byte;
    rightdiag,leftdiag:combinates;
begin
 attack:=false;
 for i:=1 to desksize do
 begin
  leftdiag[i]:=i+combinate[i];
  rightdiag[i]:=i-combinate[i];
 end;
 for j:=1 to desksize do
  for i:=1 to desksize do
  begin
   if (i<>j) and ((leftdiag[i]=leftdiag[j])or(rightdiag[i]=rightdiag[j]))
then
   begin
    attack:=true;
    exit;
   end;
  end;
end;

procedure output(combinate:combinates);
var i,j:byte;
begin

for i:=1 to desksize do
  for j:=1 to desksize do
  begin
   gotoxy(i,j);
   if(combinate[i]=j) then write(#2) else write(' ');
  end;
 readln;
end;

procedure create(num:byte; unuse:unuses; combinate:combinates);
var i:byte;
begin
 if num<=desksize then
  for i:=1 to desksize do
  begin
   if i in unuse then
   begin
    combinate[num]:=i;
    create(num+1,unuse-[i],combinate);
   end;
  end
 else if not attack(combinate) then output(combinate);

end;

begin
 textmode(c40);

clrscr;
 unuse:=[1..desksize];
 create(1,unuse,combinate);
end.

Сортировки

В лекциях 14 и 15 мы рассматривали более подробно различные способы сортировки. Здесь мы напоминаем некоторые из них и приводим пример программ.

Сортировка упорядочивает совокупность объектов в соответствии с заданным отношением порядка. Ключ сортировки - поле или группа полей элемента сортировки, которые используются при сравнении во время сортировки. Сортирующая последовательность - схема упорядочивания. Например, можно взять последовательность символов алфавита, задающую способ упорядочения строк этого алфавита.

Способ сортировки: сортировка по возрастанию, сортировки по убыванию. Методы сортировки:

Сортировка по возрастанию - это сортировка, при которой записи упорядочиваются по возрастанию значений ключевых полей.

Сортировка по убыванию - это сортировка, при которой записи упорядочиваются по убыванию значений ключевых полей.

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

Сортировка по ключу - это сортировка записей с упорядочением по значению указанного поля или группы полей.

Сортировка слиянием - это внешняя сортировка, при которой на первом этапе группы записей сортируются в оперативной памяти и записываются на несколько внешних носителей; на втором этапе упорядоченные группы сливаются с нескольких внешних носителей на один носитель данных. Носитель данных - материальный объект, предназначенный для хранения данных, или среда передачи данных.

Сортировка Батчера - это сортировка, внутренний алгоритм которой работает за время $$O(N\cdot\log (N))$$.

Программа 5. Сортировка массива по возрастанию методом пузырька.

//Данные, которые нужно отсортировать, берутся из файла "massiv.txt",
//результат записывается в массив int mas['K'] и выводится на экран
// Алгоритм реализован на Turbo C++.
#include <conio.h>
#include <stdio.h>
#define K 1000; //Размер массива

int mas['K'];
int n;
void puzirek()//функция сортирует массив по возрастанию методом пузырька
{
int i,j,t;
    for(i=0;i<n;i++)
        for(j=1;j<n-i;j++)
            if(mas[j]<mas[j-1])
            {
                t=mas[j];
                mas[j]=mas[j-1];
                mas[j-1]=t;
            }
}

int main()
{
    clrscr();
    FILE *filePointer=fopen("massiv.txt","r");
    int i=0;
    while (!feof(filePointer))
        {
            fscanf(filePointer,"%d",mas[i]);
            i++;
    }
  n=i;
    puzirek();
    for(i=0;i<n;i++)
        printf("%d ",mas[i]);
    //scanf("%d",n);
    getch();
    return 0;
}

Программа 6. Пузырьковая сортировка и сортировка методом прямого выбора.

{Сортировка. Алгоритм реализован на языке программирования Turbo-Pascal}
uses crt;
var
M, N : array[0..10] of integer;
i:integer;

procedure Input;
begin
for i := 0 to 10 do
begin
writeln('Число');
readln(M[i]); {Ввод массива}
end;
end;

Procedure Sort1; {Пузырьковый метод сортировки}
var
q,i,x:integer;
begin

for i:=10 downto 0 do
  begin
    for q:=0 to 10 do
      if M[q]<M[q+1] then
        begin
         x:=M[q];
         M[q]:=M[q+1];
         M[q+1]:=x
        end;
   end;
  end;

procedure Sort2;  {Метод прямого выбора}
var
i,j,k,x:integer;
begin
for i:=0 to 9  do
 begin
   k:=i;
   x:=M[i];
   for j:=i+1 to 10 do
   if M[j] >x then begin k:=j; x:=M[k];
   end;
   M[k]:= M[i];
   M[i]:=x;
   end;
   end;

{---------------------------------------------}
  begin
  clrscr;
  input; {Ввод исходного массива}
  writeln('Исходный массив');
  for  i:=0 to 10 do write(M[i],'  '); {Вывод исходного массива}
  writeln;
Sort1;{Сортировка массива методом пузырька}
writeln ('Сортированный массив');
    for  i:=0 to 10 do write(M[i],'  '); {Вывод отсортированного массива}
  input; {Ввод исходного массива}
  writeln('Исходный массив');
  for  i:=0 to 10 do write(M[i],'  '); {Вывод исходного массива}
  writeln;

sort2;
    writeln ('Сортированный массив методом прямого выбора');
  for  i:=0 to 10 do write(M[i],'  '); {Вывод отсортированного массива}
 readln;
  end.

Программа 7. Сестры.

//Две строки матрицы назовем сестрами, если совпадают
//множества чисел, встречающихся в этих строках. Программа
//определяет всех сестер матрицы, если они есть,
//и выводит номера строк. Алгоритм реализован на Turbo C++.
//#include <graphics.h>
#include <stdlib.h>
//#include <string.h>
#include <stdio.h>
#include <conio.h>
//#include <math.h>
#include <dos.h>
#include <values.h>
#include <iostream.h>

const n=4,//кол-во строк
      m=4; //столбцов

int m1[n][m];
//исходный массив
struct mas{int i,i1;};
//i-индекс сравниваемой строки с i1 строкой
mas a[n*2];
//массив типа mas, где будут лежать сестры, пример) a[1].i и a[1].i1 -
сестры

void main()
{clrscr();
int i,j;
 randomize();
 for( i=0;i<n;i++)
 for( j=0;j<m;j++)
 m1[i][j]=random(2);
//случайным образом в массив заносим цифры

for(i=0;i<n;i++)
 {printf("\n %d) ",i);
  for(int j=0;j<m;j++)
  printf(" %d",m1[i][j]);
//распечатываем этот массив
 }
 int min,
 p;
//индекс минимального элемента после s-го элемента i-ой строки
//сортировка строк массива по возрастанию
 for(i=0;i<n;i++)//i-сортировка i-ой строки
 {
   for(int s=0;s<m-1;s++)
 {min=m1[i][s+1];
 for(int j=s;j<m;j++)
  if(m1[i][j]<=min){min=m1[i][j];p=j;}
//запоминаем минимальный элемент в ряде после s-го элемента
 if(m1[i][s]>=min)
    {m1[i][p]=m1[i][s];m1[i][s]=min;}
//меняем местами s-й и p-й элемент,если s-й>p-го(минимального)
 }

}

printf("\n");
  for(i=0;i<n;i++)
 {printf("\n %d) ",i);
  for(int j=0;j<m;j++)
  printf(" %d",m1[i][j]);
//выводим отсортированный массив
 }
int s=0 //сколько элементов в i-й строке совпадают с 
  эл-ми i1 строки, k=0;    
//сколько строк совпали
int i1;
for(i=0;i<n-1;i++)                  //верхняя строка i
for( i1=i+1;i1<n;i1++)                  //нижняя строка i1
{s=0;
 for(int j=0;j<m;j++)
    //сравнение идет по j-му столбцу
//        !          !
 if(m1[i][j]==m1[i1][j])s++;         //если соответствующие элементы в
//i-й и i1-й строки совпадают, то кол-во совпавших увеличивается на 1
 if(s==m){a[k].i=i;a[k].i1=i1;k++;}
    //если все элементы i-й и i1-й строки совпали, то они сестры
}

printf("\nСестры :");
for(i=0;i<k;i++)
printf("\n %d и %d",a[i].i,a[i].i1);
    //распечатываем a[i].i-ю и a[i].i1-ю сестру
getch();
}

Программа 8. Поиск узоров из простых чисел.

//Построить матрицу А(15 Х 15)таким образом:  А(8,8)=1, затем
//по спирали против часовой стрелки,
//увеличивая значение очередного элемента на единицу
//и выделяя все простые числа красным цветом, заполнить матрицу
//Алгоритм реализован на Turbo C++.

#include <stdio.h>
#include <conio.h>

void main(void)
{
 clrscr();
 int mas[15][15];
 int n=1,x=6,y=6,k=1;
 int i,j;
 while(1){
  mas[x][y]=k++;
  switch(n){
  case 1: x++;break;
  case 2: y--;break;
  case 3: x--;break;
  case 4: y++;break;
  }
  if(x==15) break;

if(x==y  x<6) n=4;
  else if(x+y==12  x<6) n=1;
  else if(x+y==12  x>6) n=3;
  else if(x==y+1  x>6) n=2;

}

for(i=0;i<15;i++)
 {
    for(j=0;j<15;j++)
    {
      textcolor(12);
      if(mas[j][i]>2)
       for(k=2;k<mas[j][i];k++)
          if(mas[j][i]%k==0) textcolor(15);
      cprintf("%3d ",mas[j][i]);
    }
    printf("\n");
 }

getch();
}