Покрыть шахматное поле ходами коня.

		3		2
	4				1
			k
	5				8
		6		7

 

a) Одно решение

void TryNextMove()

{

       while (нет решения && есть ходы)

       {

                   выбрать ход;

                   if (ход возможен)

                   {

запомнить ход;

                          if (доска заполнена)

                                          есть решение;

                          else

                     {

                                 TryNextMove();

                                     if (нет решения)  забыть ход;

                              }

                   }

       }

}

int q=0;

void TryNextMove(int n, int x, int y)

{

       int u, v, m=0;

           

       while (q==0 && m<8)

       {

                   u=x+a[m]; //2, 1, -1, -2, -2, -1, 1, 2

                   v=y+b[m]; //-1, -2, -2, -1, 1, 2, 2, 1

                   m++;

                   if ((u>-1)&&(u<8)&&(v>-1)&&(v<8)&&(h[u][v]==0))

                   {

                              h[u][v]=n;

                              if (n==64)

                                          q=1;

                              else

                              {

                                          TryNextMove(n+1,u,v);

                                          if (q==0)

                                                      h[u][v]=0;

                              }

                   }

       }

}

b) Все решения

void TryNextMove()

{

       while (есть ходы)

       {

                   выбрать ход;

                   if (ход возможен)

                   {

запомнить ход;

                          if (доска заполнена)

                                          выдать решение;

                          else

                     {

                                 TryNextMove();

                                      забыть ход;

                              }

                   }

       }

}

2.5.3 Задача о коммивояжере

void коммивояжер(int k, вершина v)

{

for (w соседих с v)

{

       if {L+C[v,w]<Lmin}

       {

             if (w==начальный узел и k==n)

             {

                   Lmin=L+C[v,w];

                   Smin <- S;

             }

             else

             {

                   if (T[w]==0)

                   {

                        S[k]=w;

                        T[w]=1;

                        L=L+C[v,w];

                        коммивояжер(k+1, w);

                        T[w]=0;

                        L=L-C[v,w];

                   }

             }

       }

}

}

Использование симметрии

Раскраска карты

   procedure перебор_с_возвратом(m: integer);   var i: integer;  begin if m > n  then   <найдено решение>  else   for i:= 1  to k  do begin      цвет[m]:= i;     if <цвета стран 1,...,m-1 соседних с m -ой не i>  then       перебор_с_возвратом(m+1);     end;   end ; 1,2,3,3 = 3,2,1,1  procedure перебор_с_возвратом(m: integer);  var i: integer;  begin if m > n  then    <найдено решение>  else begin     for i:= 1  to кол_красок  do begin        цвет[m]:= i;       if <цвета стран 1,...,m-1 соседних с m -ой не i>  then            перебор_с_возвратом(m+1);    end;     if кол_красок < k  then begin        кол_красок:= кол_красок+1;       цвет[m]:= кол_красок;       перебор_с_возвратом(m+1);       кол_красок:= кол_красок-1;    end;  end;  end;

Распространение ограничений

 

Рис. 2.4

 procedure распространение_ограничений(m: integer);   var i: integer;  if m > n  then     <найдено решение>  else     for i:= 1  to n  do          if пространство[m,i] = 0  then begin              ферзь[m]:= i;             сократить_пространство_перебора(m,i);             распространение_ограничений(m+1);             восстановить_пространство_перебора(m,i);         end;  end;

Изменение порядка перебора

 

 

Рис. 2.5

 

Метод ветвей и границ

Укладка рюкзака. Из заданных n предметов выбрать такие, чтобы их суммарная стоимость была не менее чем S, а суммарный объём не превосходил V.

Неизвастна длина результата.

 procedure перебор_с_возвратом(m: integer);   var i: integer;  begin if m > n  then     <найдено решение>   else begin    x[m]:= 0;   потерянная_стоимость:= потерянная_стоимость+стоимость[m];   if полная_стоимость - потерянная_стоимость => S  then        перебор_с_возвратом(m+1);   потерянная_стоимость:= потерянная_стоимость-стоимость[m];   x[m]:= 1;   сумм_объём:= сумм_объём+объём[m];   if сумм_объём <= V  then        перебор_с_возвратом(m+1);   сумм_объём:= сумм_объём-объём[m];  end;  end;

Деревья

Определения

 

Бинарные деревья

Представление деревьев в памяти

1. Хранение двух указателей

struct tree{

char ch;

tree * left;

tree * right;

};

1. Паралельные массивы
2. Хранение в одном массиве

LEFT(i) return 2 i RIGHT(i) return 2 i + 1

Обходы

1. Обходы в прямом, внутреннем и обратном порядке

void PrintTree(tree *t)

{

if (t!=NULL)

{

             printf("%c",t->ch);

             PrintTree(t->left);

             PrintTree(t->right);

}

}

void PrintTree(tree *t)

{

if (t!=NULL)

{

             PrintTree(t->left);

             printf("%c",t->ch);

             PrintTree(t->right);

}

}

void PrintTree(tree *t)

{

if (t!=NULL)

{

             PrintTree(t->left);

             PrintTree(t->right);

             printf("%c",t->ch);

}

}

1. Раскрытие рекурсии

tree *st[10];

int s=0;

void PrintTree(tree *t)

{

s++; st[s]=t;

while (s)

{

             t=st[s]; s--;

             while (t!=NULL)

             {

                        printf("%c",t->ch);

                        s++; st[s]=t->right;

                        t=t->left;

             }

}

}

 

struct stackT{

int type;

tree *t;

};

stackT stk[20];

int s=0;

 

void PrintTree(tree *t)

{

int type;

 

s++; stk[s].type=1; stk[s].t=t;

while (s)

{

             t=stk[s].t; type=stk[s].type; s--;

             if (t!=NULL)

             {

                        if (type==0)

                                    printf("%c",t->ch);

                        else

                        {

                                    s++; stk[s].type=1; stk[s].t=t->right;

                                    s++; stk[s].type=0; stk[s].t=t;

                                    s++; stk[s].type=1; stk[s].t=t->left;

                        }

             }

}

}

1. Обход в ширину

 

void PrintTree(tree *t)

{

S<-t;

while (S не пусто)

{

             t<-S;

             if (t!=NULL)

             {

                        printf("%c",t->ch);

                        S<- t->right;

                        S<- t->left;

             }

}

}

 

void PrintTree(tree *t)

{

Q<-t;

while (Q не пусто)

{

             t<-Q;

             if (t!=NULL)

             {

                        printf("%c",t->ch);

                        Q<- t->left;

                        Q<- t->right;

             }

}

}