Розділ IV. АЛГОРИТМИ
return (*find_pos)->m_iDist;
}
find_pos++;
}
return 0;
}
//пошук у глибину
void CFind::isFlight(char *from, char *to)
{
int d, dist;
char anywhere[20];
//подивитися, чи є місто пунктом прибуття if(d=match(from, to)) {
push(from, to, d); return;
}
//перевірити інший рейс if(dist=find(from, anywhere)) {
push(from, to, dist); isFlight(anywhere, to);
}
else {
//пошук із поверненням pop(from, to, &dist); isFlight(from, to);
}
}
/*Підпрограми звернення до стеку*/
void CFind::push(char *from, char *to, int dist)
{
CStack *st=new CStack(from, to, dist); bt_stack.push_back(st);
}
void CFind::pop(char *from, char *to, int *dist)
{
vector<CStack*>::iterator tos=bt_stack.end()-1; if(!bt_stack.empty()) {
strcpy(from, (*tos)->m_sFrom); strcpy(to, (*tos)->m_sTo); *dist=(*tos)->m_iDist; bt_stack.pop_back();
}
else cout<<"EMPTY Стек порожній."<<endl;
}
Основна програма:
int main()
{
char from[20], to[20]; CFind *fnd=new CFind(); fnd->setup();
cout<<"From Пункт відправлення:"; cin>>from;
cout<<"To Пункт прибуття:"; cin>>to;
fnd->isFlight(from, to); fnd->route(to);
return 0;
}
Зверніть увагу, що main() просить ввести пункти відправлення та прибуття. Це означає, що програму можна використовувати для ви- значення маршрутів між будь-якими двома містами.
Якщо обрано Київ і Сімферополь, то розв'язком буде: Київ – Черні- гів – Одеса – Сімферополь (див. рис. 4.7). Відстань – 1258 км.
Пошуком у глибину знайдено один із розв'язків. Він не оптималь- ний (оптимальний у даному випадку – Київ – Вінниця – Сімферополь із відстанню 1067 км), але поганим його теж назвати не можна ■
У цьому випадку було з першої спроби знайдено маршрут без пове- рнення – це перевага методу. Недоліком є те, що для відшукання оп- тимального розв'язку при пошуку в глибину доводиться пройти май- же всі вершини.
Тепер звернемося до алгоритму пошуку в ширину для знаходження маршруту.
Приклад 4.37. Пошук у ширину.
Щоб програма виконувала пошук у ширину, необхідно змінити ли- ше підпрограму isFlight():
Лістинг.
/*Визначити, чи є маршрут із міста from до міста to, пошук у ширину*/
void void CFind::isFlight(char *from, char *to)
{
int d, dist;
char anywhere[20];
while(dist=find(from, anywhere)) { //модифікація: пошук у ширину
Розділ IV. АЛГОРИТМИ
if(d=match(anywhere, to)) { push(from, to, dist); push(anywhere, to, d); return;
}
}
//перевірити довільний рейс if(dist=find(from, anywhere)) {
push(from, to, dist); isFlight(anywhere, to);
}
else {
pop(from, to, &dist); isFlight(from, to);
}
}
Якщо обрано Київ і Сімферополь, то розв'язком буде: Київ – Вінни- ця – Сімферополь. Відстань – 1067 км.
Пошуком у ширину знайдено оптимальний розв'язок, але завдяки не методу, а способу організації даних. У цілому всі зауваження щодо швидкості роботи алгоритму пошуку в глибину діють і тут ■
Застосуємо для пошуку маршруту алгоритм Дейкстри. Щоб знайти найкоротший шлях, перепишемо метод find().
Приклад 4.38. Алгоритм Дейкстри. Лістинг.
int CFind::find(char *from, char *anywhere)
{
int dist=32000;//більше довжини найдовшого рейсу
vector<CFl*>::iterator find_pos=flight.begin(); vector<CFl*>::iterator pos=flight.begin();
while(find_pos<flight.end()) { if(!strcmp((*find_pos)->m_sFrom, from) &&
!(*find_pos)->m_cSkip) { if((*find_pos)->m_iDist<dist) { pos=find_pos; dist=(*find_pos)->m_iDist;
}
}
find_pos++;
}
if(pos<flight.end()) { strcpy(anywhere, (*pos)->m_sTo);
(*pos)->m_cSkip=1; return (*pos)->m_iDist;
}
return 0;
}
За допомогою цієї версії find() для маршруту Київ – Сімферополь отримуємо розв'язок: Київ – Вінниця – Сімферополь. Відстань – 1067 км. У даному випадку цей метод пошуку дозволяє знайти най- коротший маршрут ■
4.6.7. ЖАДІБНІ АЛГОРИТМИ
Жадібний алгоритм – це алгоритм, який на кожному окремому кроці обирає локально-оптимальний варіант.
Жадібним є алгоритм Дейкстри для пошуку найкоротшого шляху, оскільки він завжди обирає вершину, найближчу до вихідної, серед тих, найкоротший шлях до яких ще невідомий.
Слід зазначити, що не кожен жадібний алгоритм дозволяє отрима- ти оптимальний результат у цілому, проте для багатьох задач такі ал- горитми дійсно дають оптимальний розв'язок. Наприклад, алгоритм Дейкстри за умови відсутності ребер із від'ємною вагою дає оптима- льний розв'язок, але якщо припустити наявність таких ребер, то цей алгоритм у деяких випадках не дозволить знайти найкоротший шлях.
Застосуємо алгоритм Дейкстри для пошуку найкоротшого шляху
звершини 1 через вершину 2 до наступного графа, що містить ребро
звід'ємною вагою:
1
2
3
3
2 -2
Початкова ініціалізація:
0
1
2
3
3 ∞
Розділ IV. АЛГОРИТМИ
Крок 1. Мінімальну мітку має вершина 1. Її сусідами є вершини 2 та 3. Позначимо довжини шляхів у ці вершини через першу. Довжи- на шляху у вершину 2 становить 2, у вершину 3 – 3. Це менше поточ- них міток вершин 2, 3, тому призначимо їм нові мітки. Усі сусіди ве- ршини 1 перевірені – позначимо її як переглянуту:
0
1
2
3
3 3
Ми знайшли шлях із вершини 1 у 2. Згідно з алгоритмом Дейкстри пошук припиняється. Однак, оскільки існує шлях із вершини 3 у 2 дов- жиною –2, то оптимальним є незнайдений шлях 1–3–2 довжиною 1.
Якщо задача така, що єдиним способом знаходження оптимального розв'язку є повний перебір, то застосування жадібного алгоритму чи іншого евристичного методу для знаходження хорошого розв'язку може виявитися єдиною реальною можливістю досягнення результату.
У комбінаториці є розділ, пов'язаний із жадібними алгоритмами – теорія матроїдів. За допомогою цієї теорії можна розв'язувати задачі про застосовність конкретних жадібних алгоритмів.
*Література для CР: перебірні задачі – [8, 65, 95, 100, 125]; те-
орія матроїдів – [8, 65]; бектрекінг – [8, 65].
Контрольні запитання та вправи
1.Що таке комбінаторний вибух?
2.Що таке список суміжних вершин?
3.Як виглядає зображення графа у вигляді матриці суміжності?
4.Що таке пошук у глибину?
5.Що таке пошук у ширину?
6.Що таке алгоритм Дейкстри?
7.Дати визначення жадібного алгоритму.
8.Зобразити за допомогою списку суміжних вершин граф:
1
5
9. Зобразити за допомогою матриці суміжності граф із вправи 8.
10.Продемонструвати роботу алгоритму пошуку в глибину на заданому графі із вправи 8.
11.Продемонструвати роботу алгоритму пошуку в ширину на заданому графі із вправи 8.
12.Зобразити за допомогою списку суміжних вершин зважений граф:
|
3 |
1 |
2 |
|
|
1 |
|
|
|
|
|
3 |
2 |
3 |
4 |
2 |
|
|
|
|
|
|
|
|
|
4 |
|
|
|
1 |
|
5 |
|
|
|
5 |
|
|
13. Зобразити за допомогою матриці суміжності зважений граф із вправи 12.
14.Продемонструвати роботу алгоритму Дейкстри на заданому графі із вправи 12.
15.Чи для всіх можливих перестановок рядків розкладу рейсів компанії XYZ результат роботи запропонованих програм за- лишиться незмінним? Чому?
16.Елімінувати рекурсію в методі isFlight() для пошуку:
а) у глибину (прикл. 4.36); б) у ширину (прикл. 4.37). Для подання дерева пошуку в глибину (ширину) використати стек (чергу) на базі масиву [100, 125].
17.Відредагувати запропоновані програми пошуку маршруту різними методами так, щоб рейси, пункт відправлення й прибуття вводилися з клавіатури.
18.Лабіринт може бути заданий матрицею суміжності, в якій
для кожної пари кімнат указано, чи з'єднані вони коридо- ром. Дано матрицю суміжності лабіринту з n кімнат і но-
мери двох кімнат. Знайти шлях, що сполучає дані кімнати.
19.Перевірити зв'язність графа.
20.З'ясувати, чи є граф циклічним.
21.Побудувати транзитивно-рефлексивне замикання графа.
22.Побудувати матрицю відстаней між вершинами графа.
23.Для даного скінченного автомата реалізувати алгоритм по- шуку: а) множини недосяжних станів; б) тупикових станів;
в) * множин еквівалентних станів; г) відповіді на запитання, чи допускає скінченний автомат задане слово. Автомат за- дається з: 1) клавіатури; 2) файла.
24. Для даного скінченного недетермінованого автомата реалі- зувати алгоритм його детермінізації.
ВІДПОВІДІ ТА ВКАЗІВКИ
РОЗДІЛ 1
|
|
|
|
|
|
|
|
|
1.1. |
8. а) 8; б) 14. |
21. ( y( z( x(P 1(x) (P2(y)& (¬P1(z))))))). |
23. Нехай |
n |m |
означає |
подільність |
n |
на |
m |
без |
залишку. |
а) x y z(x |z & y|z d(x |d & y|d z ≥ d)). 26. Перейти від формул
ПЧП до пропозиційних форм шляхом заміни предикатних підтермів на пропозиційні змінні й використати формули із вправи 20 і закони булевої алгебри (див. вправу 24, підрозд. 1.2).
|
1.2. |
|
6. а) |
|
|
B ; б) C ; в) A ∩ B ∩ X . 22. Скористатися математичною |
A |
індукцією по n . |
|
|
|
10. |
|
Урахувати співвідношення max(x,y) = (x + y+|x − y|)/2. |
1.3. |
|
Знайти залежність між функціями sign(x) та |x |. 11. Написати спочатку допоміжні предикати: 1) Білa(x,y) , який є істинним, якщо клітинка (x,y) біла (якщо горизонталь парна, то білими в ній є
клітинки непарних стовпчиків, якщо непарна – то навпаки); 2) Гор. Вер. (x,y,u,v) , який є істинним, якщо клітинки(x,y) та (u,v)
розташовані на одній горизонталі або вертикалі; 3) Діагональ (x,y,u,v), який є істинним, якщо клітинки (x,y) та (u,v)
розташовані на одній діагоналі. 12–13. Застосувати композицію ітерації. 14. б) Застосувати метод від супротивного. 27. Застосувати алгоритм Евкліда через віднімання. 31. У цьому прикладі функція керування не залежить від стану. а) δ(0) = x2 ← a a, δ(1) = x4 ← x2 x2,
δ(2) = x8 ← x4 x4, δ(3) = x10 ← x8 x2. 32. Див. [42].
1.4. 39. Застосувати індукцію за кількістю станів автоматата. 40. а)
Найменші розв'язки є регулярними відносно коефіцієнтів a та b. Скористатися теоремою 1.1 про нерухому точку. (Див. [52]). 45. Застосувати метод від супротивного. Припустити, що існує скінченний автомат, який допускає цю мову, і отримати протиріччя. 58. Застосувати метод від супротивного.
ПРОГРАМУВАННЯ |
|
|
|
|
|
РОЗДІЛ 2 |
|
|
|
|
|
|
|
|
|
27. Варіант Ейлера для обходу конем: |
|
2.1. |
20 |
|
45 |
26 |
39 |
18 |
43 |
24 |
33 |
|
27 |
|
38 |
19 |
44 |
25 |
32 |
17 |
42 |
|
|
|
46 |
|
21 |
36 |
29 |
40 |
23 |
34 |
31 |
|
|
|
37 |
|
28 |
47 |
22 |
35 |
30 |
41 |
16 |
|
|
|
48 |
|
9 |
62 |
3 |
54 |
15 |
60 |
5 |
|
|
|
63 |
|
2 |
55 |
8 |
61 |
4 |
53 |
14 |
|
|
|
10 |
|
49 |
64 |
57 |
12 |
51 |
6 |
59 |
|
|
|
1 |
|
56 |
11 |
50 |
7 |
58 |
13 |
52 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
28. |
а) |
1. |
Kh5+ |
T:h5 |
2. |
Tg6+ |
Кр:g6 |
3.Te6×; |
б) 1. Tc6! Кр b7 2. Kd6+ Кр b8 3.Tc8×; |
в) 1. e8C! Кр:f6 2. g8T Кр e6 3. |
Tg6×; г) 1. Сf6! gf 2. 2. Кр f8 f5 3.Kf7×. |
|
|
|
|
|
|
16. |
15=(1111) 2 , |
|
255=(11111111) 2 , |
256=(100000000) 2 , |
2.3. |
|
32767=(111111111111111) 2 . |
|
17. |
(1111)10 =15, |
(1111)16 =F, |
(11111111)10 =255, |
(1111110)16 =FE. |
18. |
(FF2) 2 =111111110010, |
(ABCD) 2 =1010101111001101, (FF2)10 =4082. |
19. |
а) 11100111; б) |
10011010. 20. a) 36; б) 47989. 21. а) 0.11111111111. 43, 45.
Алгоритм аналогічний алгоритму швидкого піднесення до степеня
(див. прикл. 2.31).
2.5. 15. а) Див. побудову послідовності всіх десяткових цифр
натурального числа у прикл. 2.31. 17. б) p1 = |
2 , pi = 2 + pi −1 , фільтр: |
i < n . 20. а) |
Покласти ai = (−1)i(i +1)/2 /2 і знайти |
частку |
ai /ai −1 ; |
б) |
побудувати |
графік функції a(k) = [ k ],k N |
і |
звернути |
увагу |
на |
точки, в яких відбуваються стрибки значення функції; в) те саме, що й у б), тільки для функції c(k); г)-д) див. прикл. 2.29. 17. Див. прикл.
2.31. Узяти до уваги, що алгебра (R,+) є півгрупою.
|
|
|
|
|
|
|
|
ВІДПОВІДІ ТА ВКАЗІВКИ |
|
|
13. 1) |
(Б) |
ε L2 (І) для |
u L2 : aub L2 ; |
2) (Б) ε D2n (І) для |
2.6. |
u,v D2n , |
i = |
|
: aiubi D2n , uv D2n . |
16. |
а) (Б) ne(ε,ε)= 0 , |
1,n |
ne(ε,v)=1,v Σ+ |
(І) для a,b Σ: |
ne(pre(a,u), |
pre(b,v) = (a ≠ b →1|ne(u,v)); |
д) розв'язок дає система індуктивних функцій prefix(u,n), tail(u,n) та
|
tail3(u,i,n) |
таких, |
|
що |
delsym(u,k )= prefix(u,k −1)otail(u,k +1), |
|
tail(u,n) = tail3(u,1,n) |
(БФС) |
prefix(u,0) = prefix(ε,n) = ε , |
tail3(ε,i,n) = ε |
(ІФС) |
prefix(au,n) = a(prefix(u,n −1)), tail3(au,i,n) =(i ≤n →tail3(u,i +1,n)|u). |
17. а) (Б) |
count (0)= 0 |
(І) для |
n > 0 count (n )= count (n /10)+1; в)-г) |
див. прикл. 2.43. 19. (Б) |
f ( ) = 0, f (a( , )) =1, (І) для кореня |
a |
та |
піддерев |
d1,d2 , |
з |
яких |
принаймні |
одне |
непорожнє: |
|
f (a(d1,d2 )) = f (d1) + f (d2 ). 20. (Б) |
f ( ) = 0, |
(І) для кореня a |
та піддерев |
|
d1,d2 : f (a(d1,d2 )) = max{ f (d1), f (d2 )} +1. |
|
|
|
|
|
РОЗДІЛ 3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
4. a) |
<string |
|
>,<FFF>,<Null>; |
б) |
<”FDEL?>, |
<Null>; |
з) |
3.1. |
|
|
<x>,<==>,<(>, <a>, |
|
<++>, |
<+>,<b>,<*>,<2>,<)>. 6. |
1) |
< |
>,<*>,<*>,<*>,< >,</>,<*>. |
|
|
|
|
|
|
|
30.а) пари чисел 1,6; 2,19 та 3,492.
3.2.20. 1) 2057; 3) 8; 7) 13. 26. 1) так. 31. б) a%10 – залишок від
|
|
10. |
32. а) |
(a == b)& &(a == c )& &(c == b). 36. |
а) |
ділення a на |
swap(x,z), swap(y,z), |
деswap(u,v) обмінює значеннями змінні u |
та |
v . За умовою |
змінні |
x,y,z |
мають отримати значення відповідно |
змінних z,x,y . 41. а) Скористатися функціями із вправи 40; є) слону на полі xy доступні всі поля, що розташовані на двох діагоналях
(чотирьох променях), які проходять через поле. Перший промінь – уверх і праворуч із полями xy,(x +1)(y +1),(x + 2)(y + 2),... , другий –
уверх і ліворуч із полями xy,(x −1)(y +1), (x − 2)(y + 2),... , третій – униз і
ліворуч із |
полями |
xy,(x −1)(y −1),(x − 2)(y − 2),... , |
четвертий – |
униз і |
праворуч із полями |
xy,(x +1)(y −1),(x + 2)(y − 2),..., |
де |
x + i(x −i) |
– |
i -та |
вертикаль |
за (перед) вертикаллю x . У функції |
врахувати, |
що |
координати полів не можуть виходити за межі діапазону a..h ×1..8 .
|
3.3. |
16. а) Буде надруковано: |
while count і у стовпчик: 1 |
2 3 |
|
4 |
5 6 7 |
8 9 |
10. |
18. Рекурентні послідовності |
для |
n!:a0 = i0 =1,ik |
= ik −1 +1,ai |
= ai −1 ×ik ,n ! = an . 22. Урахувати, що |
при |
знаходженні чергового дільника d числа n до суми можна додати ще один дільник – n /d . При цьому на подільність достатньо перевірити
лише числа до [ n ] . Чому? 23–24. Особливості машинної арифметики
див. у підрозд. 2.3.3. 25. Для знаходження рекурентної залежності між членами ряду поділити k -й його член на попередній k −1-й.
31.Див. прикл. 2.28 про числа Фібоначчі.
3.4.16. За означенням вектор a = (a1,...,an ) є рекурентною
послідовністю без конструкторів. Опорною послідовністю для
першого місцезнаходження c є модифікований лічильник i1 =1 , |
ik = (ik −1 |
≤ n & &ai |
≠ c ) → (ik −1 |
= n → −1|ik −1 |
+1)|(ai |
= c → ik −1|−1))), |
|
k −1 |
|
|
k −1 |
|
k >1, а фільтром – умова (ik ≤ n & &ai ≠ c ) . 18. За означенням вектор |
|
|
|
|
|
|
|
k |
|
|
|
|
|
|
|
= (a1,...,an ) |
є |
рекурентною |
послідовністю |
без |
конструкторів. |
a |
Візьмемо |
bi |
= max{a1,...,ai } , |
i = |
|
, |
як |
опорну |
послідовність |
1,n |
(bn = max{a1,...,an } ). Вона рекурентна: b1 = a1 , |
bi = (ai |
> bi −1 → ai |bi −1). |
Фільтром |
є |
умова i ≤n , |
лічильник |
i |
|
ініціалізується |
з 1. |
22. У багаточлені |
P(x) = an xn +... +a1x +a0 |
|
винести |
x за |
дужки: |
P(x) = (...((an x +an −1 )x... +a1 )x +a0 . У схемі Горнера обчислення значення P(x) розпочинається з найбільш внутрішніх дужок. 23. Знайдені
прості числа зберігаються в масиві |
p(n) |
у порядку зростання, |
p(0) = 2, p(1) = 3 . Наступні кандидати x |
на просте число – непарні: 5, |
7, …. Урахувати, що для перевірки числа x |
на простоту достатньо |
перевірити, чи ділиться воно на одне з простих чисел p(i), i = 0,1,...
|
|
|
|
|
|
таких, що |
p(i)2 < x . Для подальшого вдосконалення алгоритму див. |
[19, 33]. |
|
24. |
Ініціалізувати цілий масив |
p(n) за формулою |
p(i) = i,i = |
|
. |
Вилучення кратних чисел з |
масиву означає їхнє |
0,n |
обнулення. Наступний цикл вилучає всі парні числа, які більші 2: for (k=2;k<=n;k++) p[2*k]=0;, потім вилучаються всі числа, кратні 3 і більші ніж 3 і т. д., відшукується перше p[i] ≠ 0 і викреслюються всі
числа 2i, 3i,... тощо для всіх p[i] ≤ [ n ]. 25. а) Двійкових цифр у числі k = 2100 – 101. Реалізувати в циклі множення 100 разів довгого
