Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2021-03-17 | 114 |
5.00
из
|
Заказать работу |
|
|
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;Деревья
Определения
Бинарные деревья
Представление деревьев в памяти
struct tree{
char ch;
tree * left;
tree * right;
};
Обходы
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);
}
}
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;
|
}
}
}
}
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;
}
}
}
|
|
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!