Алгоритми пошуку з поверненнями

Лінійний пошук

Об'єкт знайдений якщо

Об'єкт не знайдений якщо

З двох висловлень випливає

while(i<N && a[i]!=x) i++;

if(i==N) немає об'єкта.

Єдина можливість прискорити пошук об'єкта – спростити умову (предикат). Така можливість існує, якщо є апріорна впевненість, що елемент існує.

// N задається за межами масиву, тобто оголосити a[N+1]

тоді

a[N]=x; i=0;

while(a[i]!=x) i++;

предикат для цього випадку

Пошук розподілу навпіл (двійковий пошук).

Вважаємо, що дані упорядковані.

L___________m______________R

L=0; R=N-1; i=0; m=0;

while(L<=R && a[i] !=x)

{m=(L+R)/2;

if(a[m]==x) i=m, break;

else if(a[m]<x) L=m+1;

else R=m-1;

}

Умова останова

Спростивши, одержимо

На ефективність впливає вибір m. Однак краще коли береться ½ масиву, що забезпечує максимальне число порівнянь рівне log. Тоді як лінійний пошук забезпечує N/2 порівнянь.

Ефективність можна поліпшити, помінявши місцями, оператори перевірки

while( a[m] !=x && L<=R )

тому що умова L<=R не обчислюється якщо a[m] !=x прагне до 0.

З метою поліпшення, можна прийти до питання, а чи потрібна перевірка a[m] !=x .

Що якщо представити рішення у виді

і помістити перевірку за виходом із циклу.

L=0; R=N-1; m=0;

while(L<=R)

{ m=(L+R)/2;

if(a[m]==x) i=m, break;

else if(a[m]<x) L=m+1;

else R=m-1;

}

if(a[R]!=x) немає елемента;

Необхідно довести, що умова L>=R досяжна (тобто обидві секції пошуку «накриють» масив цілком).

Для доказу необхідно показати, що R-L убуває:

- спочатку L<R

- а потім, або L зростає (m+1), або R зменшується.

Інтерполяційний пошук.

Якщо відомо, що К знаходиться між К₁ і К_р, то номер чергового елемента для порівняння визначається формулою:

М = 1 + (р – 1) * (К – К₁) / (К_р – К₁).

находиться між та наступна процедура аналогічна процедурі, використовуваної в бінарному пошуку.

Прямий пошук рядка

Задано char S[N] і p[M], де 0<M<=N. Пошук рядка полягає у виявленні першого входження P у S.

Будемо вважати результатом індекс i , що вказує на перше (входження) збіг P у S. Уведемо предикат:

Звідси, якщо шукати розбіжність між образом і рядком, можна записати

Тоді програмна реалізація прийме вид

i=-1;

do

{ i++; j=0;//Q(i)

while(j<M&&S[i+j]=P[j])

{j++;}

} while(j!=M|| i=!(N-M));

j=M – умова «знайдена»

!(N-M)- збіг у рядку не виявлене

Алгоритм ефективний тільки у випадку якщо збіг буде досягнуто після декількох порівнянь у внутрішньому циклі. Інакше, щоб знайти збіг наприкінці рядка буде потрібно N*N порівнянь.

Пошук у рядку (алгоритм Кнута, Моріса, Пратта)

i=0; j=0;

while(j<M && i<N)

{while(j>=0&& s[i] !=P[j])

{j=d;}

i++; j=j+d; //

}

1.3.Варіанти індивідуальних завдань лабораторної роботи №1

1. Пошук елемента серед уведених цілих чисел методом половинного розподілу.

2. Пошук елемента серед генерованих через RND чисел методом половинного розподілу.

3. Пошук під рядка в рядку. Організувати через масиви.

4. Пошук заданого елемента серед с генерованих через RND чисел методом половинного розподілу. Для створення масиву скористатися покажчиками.

5. Пошук символу в рядку.

6. Реалізувати метод інтерполяційного пошуку.

7. Порівняти «швидкість» пошуку методам половинного розподілу й інтерполяційного пошуку.

8. Пошук рядка в рядку. Організувати через покажчики.

9. Написати функцію що дозволяє знаходити символ у рядку.

10. У заданій послідовності поміняти місцями перший від’ємний елемент, що зустрівся, з першим додатним елементом, що зустрівся за ним.

11. Визначити, скільки разів в сформованому вами рядку зустрічається сполучення символів “a” і “b”. Символи “a” і “b” задаються в інтерактивному режимі.

12. Визначити, скільки разів в сформованому вами рядку повторюються обрані символи, з яких складається алфавіт.

13. Визначити, скільки разів у вашому рядку зустрічається кожний із символів і яке сполучення з цих символів найбільше часто зустрічається.

14. Визначити, скільки однотипних сполучень символів міститься в списку прізвищ студентів сформованих у попереднім завданні.

15. Скласти програму визначення слів, що містять цифрові символи.

16. Виділити частину рядка, розташованого між двома буквами. Букви виводяться по запиті.

17. У довільно узятій пропозиції віддрукувати слова, у яких збігаються більш двох букв.

18. Віддрукувати слово тексту з максимальною кількістю голосних букв.

19. Вивести на печатку рядок символів, розташованих між дужками.

20. Визначити кількість слів, що складають дану пропозицію.

21. Дано довільний рядок, що містить 10 слів. Потрібно надрукувати цю послідовність слів, але в зворотному порядку.

22. Дано довільний рядок, що містить 10 слів. Потрібно надрукувати слова, перед якими в послідовності знаходиться тільки менші (за алфавітом) слова, а за ними тільки великі.

23. Дано довільний рядок, що містить 10 слів. Потрібно надрукувати всі слова, що у послідовності зустрічаються по одному разі.

24. Дано довільний рядок, що містить 10 слів. Потрібно надрукувати всі слова за абеткою.

25. Дано довільний рядок, що містить 10 слів. Потрібно надрукувати всі різні слова, указавши для кожного з них число його входжень у послідовність.

26. У довільно сформованому рядку, що містить 60 латинських букв, потрібно усі входження Lat замінити на Tal.

27. У довільно сформованому рядку, що містить 60 латинських букв, потрібно видалити перше входження AD , якщо таке є, а діру, що утвориться, заповнити наступними буквами, а наприкінці додати пробіли.

28. Скласти функцію, що дозволяє визначити позицію самого правого входження заданого символу у вихідний рядок. Якщо рядок не містить символу, результатом роботи процедури повинна бути –1.

29. Задано дві послідовності цілих чисел a₁,…,a_n,b₁,…,b_mі число k. Якщо в послідовності а₁,…,а_n немає жодного члена зі значенням k, тоді перший один по одному член цієї послідовності, не менший всіх інших членів, замінити на значення k. По такому ж правилу перетворити b₁,…,b_m стосовно до значення 10.

30. Скласти функцію перестановки кожної пари елементів масиву (перший і другий, третій і четвертий і т.д.). Застосувати її для векторів MX[10],MY[8], MZ[6].

1.4. Контрольні питання.

1. Які основні відмінності Ви бачите в методах лінійного пошуку й пошуку розподілу навпіл?

2. Що лежить в основі оптимізації методупошуку розподілу навпіл?

3. Коли ефективний алгоритм методу пошуку прямого рядка?

4. Визначите основні вимоги до алгоритму прямого пошуку в рядку.

2 РІШЕННЯ ЗАДАЧ З ВИКОРИСТАННЯМ РЕКУРСІЇ

2.1 Ціль роботи

Освоєння методів рішення задач з використанням рекурсії.

2.2 Підготовка до роботи

При підготовці до роботи варто вивчити методи [1, с.75-90; 2,с.89-96; конспект лекцій].

Рекурсією називається спосіб завдання функції, при якому значення обумовленої функції для довільних значень аргументів виражається відомим образом через значення обумовленої функції для менших значень аргументів.

Функції обчислювань - це такі функції значення, яких можна установити за допомогою деякого алгоритму. Функція називається рекурсивною, якщо існує ефективна процедура для її обчислення.

Поняття ефективної процедури є інтуїтивним, і говорять, що існує процедура для виконання визначених обчислень, якщо ці обчислення виробляються за визначеними правилами (алгоритму).

Сукупність числових функцій, що збігає із сукупністю усіх обчислювальних функцій при самому широкому до тепер відомому розумінні алгоритму, звуться рекурсивними функціями.

Гедель описав клас усіх рекурсивних функцій як клас усіх числових функцій, визначних у деякій формальній системі.

Черч (виходячи з інших передумов) вивів той же клас числових функцій, що і Гедель, і сформулював гіпотезу, що клас рекурсивних функцій тотожний із класом усюди визначених обчислюємих функцій. Поняття обчислюваємою функції точно не визначається, тому теза Черча довести не можна.

Якщо деяким елементам Х поставлені у відповідність деякі елементи Y, то говорять, що задано часткову функцію з Х в Y. (Якщо область визначення Х в Y збігаються з безліччю Х, то функція називається усюди визначеної).

Кліні ввів поняття частково рекурсивної функції і висловив гіпотезу, - « усі частково рекурсивні функції обчисліюмі за допомогою алгоритмів, є частково рекурсивними».

(Далі целочислені і ціло значимі функції називаються арифметичними.)

У теорії рекурсивних функцій велике значення мають три операції:

операція суперпозиції функцій полягає в підстановці одних арифметичних функцій замість аргументів інших арифметичних функцій;

операція примітивної рекурсії дозволяє будувати n+1 місцеву арифметичну функцію (функцію від n+1 перемінних) по двох заданих функціях n-місцевої і n+2 місцевої функції;

операція найменшого чи кореня операція мінімізації, дозволяє визначити нову арифметичну функцію f(x₁,...,x_n) від n перемінних за допомогою раніше побудованої арифметичної функції g(x₁,...,x_n,y) від n+1 перемінних.

Арифметичні функції, що можуть бути побудовані з елементарних арифметичних функцій за допомогою операції суперпозиції, примітивної рекурсії і найменшого кореня, називаються частково рекурсивними функціями. Якщо такі функції виявляються усюди визначеними, то вони називаються загально рекурсивними функціями.

Поняття частково рекурсивної функції – одне з найважливіших понять теорії алгоритмів. Значення його полягає в наступному:

Кожна стандартно задана частково рекурсивна функція вичисліма шляхом визначеної процедури механічного характеру.

Які би класи точно обкреслених алгоритмів дотепер фактично ні будувалися, у всіх випадках незмінно виявлялося, що числові функції, вичислімі за допомогою алгоритмів цих класів, були частково рекурсивними.(Теза Черча)

З погляду програмування рекурсія це спосіб організації обчислювального процесу, при якому функція може звертатися чи прямо чи побічно сама до себе.

Значне число задач зважується з використанням алгоритмів заснованих на використанні рекурсивних функцій. Але варто знати, що не всі задачі, що можуть бути вирішені з використанням рекурсивних функцій, виграють у порівнянні з ітераційними алгоритмами. Навіть навпаки, якщо задача може мати рішення, засноване на використанні ітераційних алгоритмів те воно переважніше. Цей висновок заснований на аналізі втрат часу зв'язаних з викликом функцій

Прикладом задачі, де використання рекурсії виправдане, може служити рішення задачі про Ханойські вежі.

Ця задача формулюється в такий спосіб: мається три стрижні. На одному з них знаходяться диски, різних розмірів, зменьшиними до верха (піраміда). Потрібно перенести ці диски на інший стрижень, використовуючи тільки один, допоміжний стрижень. При цьому за один раз можна перенести тільки один диск, а більший по розміру диск не припустимо ставити на диск меншого розміру

Доказ рішення цієї задачі засновано на використанні індукційного методу, з якого безпосередньо випливає алгоритм, заснований на використанні рекурсивних функцій. Так, для випадку одного диска рішення, мабуть, він просто перекладається з вихідного стрижня на заданий. Для випадку з двох дисків спочатку верхній диск перекладається на допоміжний стрижень, а потім нижній диск із вихідного стрижня і верхній з допоміжного стрижня перекладаються на заданий. Аналогічно, для випадку N дисків, спочатку N-1 дисків при дотриманні правил перестановки переміщаються на допоміжний стрижень, а потім на заданий стрижень переноситься нижній диск (він знайшов своє місце). Далі, з огляду на, що останній диск, переміщений на заданий стрижень, ніяк не заважає, оскільки він більше вся інших, задача зважується аналогічно. Виключення полягає в тому, що N-1 диск, із що залишилися, переміщаються на допоміжний, котрий раніше був вихідним, використовуючи в якості проміжного заданий, а останній з залишившихся знову переміщається на заданий стрижень. Таким чином, після двох циклів перестановок, ми приходимо до вихідної ситуації використання стрижнів, але кількість дисків, який необхідно переставити менше на два диски і т.д.. Процес рекурсії зупиняється, коли залишається тільки один диск, що переміщається на заданий. Доведено, що для n дисків мінімальне число необхідних переміщень дорівнює .

Рекурсивна функція повинна завжди визначати умову закінчення, інакше рекурсія стане нескінченної.

#include<iostream.h>

int k;

void Hanoy1 (char a,char b,char c,int n );

void main()

{

cout<<”уведіть кількість дисків”<< “\n”;

cin>>k;

Hanoy1 ('A', 'C', 'B', k);//перенесено k дисків з A на C проміжний B

cin>>k;

}

void Hanoy1 (char a,char b,char c,int n )

{int v;

v=n;

if (n==1)

cout<<”перемістити “<< v<<” з “<< a<<” на “<<b<<”\n”;

else

{Hanoy1 (a, c, b, n - 1); //перенесено n - 1 дисків з A на C проміжний B

cout<<”перемістити “<<v<<” з “<< a<<” на “<< b<<”\n”;

Hanoy1 (c, b, a, n - 1); //перенесено n - 1 дисків з C на B проміжний A

} }

2.3. Варіанти завдань до лабораторної роботи №2.

1.Дано число і послідовність чисел . Побудувати й обґрунтувати алгоритм обчислення по формулах:

а)

b)

2. Дано дві послідовності і .Визначити третю послідовність, елементи якої обчислюються по формулі:

( )

3.Скласти алгоритм обчислення по формулі

( , )

4. Скласти алгоритм обчислення по формулі

( )

5. Скласти алгоритм обчислення по формулі

( )

6. Скласти алгоритм обчислення по формулі

( , )

7. Скласти алгоритм визначення однакових чисел у заданій послідовності чисел .

8. Скласти алгоритм визначення максимального (мінімального) елемента в заданій послідовності чисел .

9. Скласти алгоритм визначення кількості однакових чисел у заданій послідовності чисел .

10. Скласти алгоритм множення матриці на вектор.

11. Скласти алгоритм множення матриці на матрицю.

12. Скласти алгоритм, що реалізує операцію об'єднання двох заданих множин.

13. Скласти алгоритм, що реалізує операцію перетинання двох заданих множин.

14. Скласти алгоритм транспонування матриці.

15. Скласти алгоритм, що реалізує операцію різниці двох заданих множин.

16. Знайти найбільший загальний дільник q для заданої пари чисел, використовуючи алгоритм Эвкліда. Алгоритм Эвкліда. Нехай а і b одночасно не рівні 0 цілі числа. Нехай a>b. Тоді для цілих чисел a,b,c де c – залишок від цілочисельного розподілу a на b виконується рівність

НОД(a,b)=НОД(b,c)

17. Скласти алгоритм, рішення задачі розрахунку боргу клієнта банку, що взяв деяку суму під щомісячний відсоток від поточної суми боргу.

18. Скласти алгоритм, визначення суми цифр заданого числа.

19. Числа Фібоначчи (f_n) визначаються формулами

f₀=f₁=1; f_n=f_n-1+f_n-2, при f=2, 3... .

Знайти перше число Фібоначчи більше m (m>1).

20. Обчислити S-суму всіх чисел Фібоначчи, що не перевершують 500. Визначення чисел Фібоначчи дано в попереднім завданні.

21. Написати програму рекурсивного пошуку максимального елемента послідовності a₁,...,a_30.

22. Послідовність U₀, U₁, U₂,... визначається правилами U₀=0, U₁=1, U_i+2=U_i+1+U_i. Написати програму обчислення

S= U_i.

23. Надрукувати всі прості дільники заданого натурального числа.

24. Написати програму побудови послідовності a₁,...,a₃₀, утвореної за законом: a₁=2, a_i=a_[i/2]+a_i-1, (i=2,..., 30).

25. Написати програму рекурсивного підсумовування елементів послідовності a₁,...,a_30.

26. Написати програму інверсії елементів послідовності a₁,...,a₃₀ з використанням рекурсії

27. Визначити число, одержуване уписуванням у зворотному порядку цифр заданого натурального числа.

28. Використовуючи рекурсію знайти суму ряду 1 + 1/2 + 1/3 + … + 1/N с заданою точністю.

29. Дано додатні цілі числа k, l, m, обчислити де

якщо

якщо

якщо

(Це так названа функція Акермана).

30. Дано натуральне число n. З'ясувати, чи маються серед чисел n, n+1,..., 2n близнюки, тобто прості числа, різниця між якими дорівнює двом. (Визначити процедуру, що дозволяє розпізнавати прості числа).

2.4.Контрольні питання.

1. Які задачі має сенс вирішувати з використанням рекурсії?

2. Визначите основні вимоги до алгоритму рішення задачі з використанням рекурсивних функцій.

3. Які основні операції визначають рекурсивний підхід до рішення задач?

4. Які обмеження накладає рекурсивний підхід до рішення задач?

3 РІШЕННЯ ЗАДАЧ З ВИКОРИСТАННЯМ АЛГОРИТМІВ СОРТУВАННЯ

3.1 Ціль роботи

Вивчити й освоїти основні методи сортувань. Навчитися правильно, вибирати методи сортувань у залежності від розподілів значень сортируємих даних.

3.2 Підготовка до роботи

Необхідно ознайомитися з основними методами сортувань [1, с.150-164;2,с.110-114; конспект лекцій].

Сортування масивів (внутрішнє сортування) і сортування файлів (зовнішнє сортування).

Внутрішнє сортування - це таке сортування, при якій всі елементи сортируємої послідовності уміщаються в оперативній пам'яті машини.

Зовнішнє сортування - це сортування, при якій елементи сортируємої послідовності в оперативній пам'яті не містяться, і в сучасний момент часу якась частина з них обов'язково знаходиться на зовнішньому носії (наприклад, у файлі).

Задача сортування полягає в наступному: задана деяка послідовність числових даних . Потрібно переставити елементи послідовності таким чином, щоб одержати упорядковану за деяким законом послідовність , у якій для будь-якого 1<=i<=n елемента виконується задане деякої функції, що упорядковує, f відношення порядку , наприклад .

Значення функції, що упорядковує, часто називають ключем елемента.

Метод сортування називають стійким, якщо в процесі сортування відносне розташування елементів з рівними ключами не змінюється. Наприклад, для послідовності 4567776 сортування подвисне на 7 при if ( a[i] <= a[i-1] )

while(is)

{ is=0;

for (i=m+1; i<=n; i++)

if ( a[i] <= a[i-1] )

{ c=a[i];

a[i]=a[i-1];

a[i-1]=c;

is=1;

}

Стійкість найбільш важлива, коли мова йде про вже упорядкований, по деяких вторинних ключах, послідовностей.

Часто однією з умов сортування є вимога, щоб перестановки елементи, що приводять, у порядок виконувалися на тім же місці, тобто не вимагали створення буферного масиву того ж порядку, що і вихідний.

Мірою ефективності алгоритмів сортування звичайно служать: C- число необхідних порівнянь ключів; M- число пересилань (перестановок) елементів.

Звичайно алгоритм вважається гарним, якщо він вимагає порядку n*ln(n) (ускладнені методи) порівнянь і невдалим, якщо він вимагає n² порівнянь ключів (прямі методи). Тут n - число сортируємих елементів.

Ускладнені методи вимагають невеликого числа операцій, але ці операції самі по собі складні, і тому при досить малих n прямі методи виявляються швидше.

Методи сортування «на тім же місці» поділяються на три категорії:

1) сортування вставками чи включенням.

2) сортування вибором

3) сортування обміном.

При роботі зі списками дуже часто виникає необхідність перестановки елементів списку у визначеному порядку. Така задача називається сортуванням списку і для її рішення існують різні методи. Розглянемо деякі з них.

Пухирцеве сортування

При обмінному сортуванні упорядкований список виходить із систематичним обміном сусідніх елементів, що не відповідають необхідному порядку, поки такі пари існують.

Найбільш відомий метод систематичного обміну сусідніх елементів з неправильним порядком зветься " Пухирцеве сортування". У цьому методі здійснюється перегляд усього списку ліворуч на право і виробляється взаїмозаміна елементів при порушенні закону відповідності. Максимальні елементи як би спливають наприкінці списку, що визначило назву методу. Якщо на якомусь проході обмінів не було, виходить, сортування закінчене.

У наших прикладах будемо вважати, що сортується одномірний масив (або його частина від індексу m до індексу n) у порядку зростання елементів. Нижче приводиться приклад програми реалізуючої метод пухирцеве сортування.

/* сортування пухирцевим методом */

float * bubble(float * a, int m, int n)

{ char is=1;

int i;

float c;

while(is)

{ is=0;

for (i=m+1; i<=n; i++)

if ( a[i] < a[i-1] )

{ c=a[i];

a[i]=a[i-1];

a[i-1]=c;

is=1;

} } return(a); }

3.3. Варіанти індивідуальних завдань лабораторної роботи №3.

Розробити алгоритм і програму формування заданої послідовності, відповідно до вашого варіанта, і відсортувати її.

При формуванні послідовностей використовувати функції виду: і т.п.

3.4. Контрольні питання

1. У чому відмінність внутрішнього і зовнішнього сортування даних?

2. Які основні категорії методів сортування Ви знаєте?

3. Які способи оцінки алгоритмів Ви знаєте?

4. Які вимоги пред'являються до алгоритмів сортування?

5. Які методи сортування називаються стійкими?

4. РІШЕННЯ ЗАДАЧ З ВИКОРИСТАННЯМ ГРАФІВ. ЗНАХОДЖЕННЯ ХРОМАТИЧНОГО ЧИСЛА.

4.1 Ціль роботи

Одержати практичні навички аналізу графів, використовуючи методи функціонального і логічного програмування.

4.2.Підготовка до роботи

Студент повинен знати основні визначення теорії графів. У даній роботі вивчаються основні поняття теорії графів, на основі яких зважується задача визначення хроматичного числа графа.

Графом називають сукупність двох множин – множини (вершин графа) і безлічі (ребер графа) неупорядкованих пар різних елементів безлічі .

= . .

Часто користаються й іншим визначенням графа. Графом називають упорядковану трійку

.

Де безліч вершин графа, безлічі ребер графа, - инцидентор – тримісний предикат, що визначає якій парі вершин , відповідає ребро .

Це визначення еквівалентне попередньому.

Якщо ,

де , те можна задати у виді , тому що инцидентор визначений завданням множин і .

Нехай , - вершини, - з'єднуюче їхнє ребро. У цьому випадку вершина і ребро інцидентні, так само як і з також інцидентні.

Вершини , інцидентні ребра , якщо і називаються суміжними. Два ребра інцидентні одній вершині також називаються суміжними.

Безліч вершин інцидентних з вершиною , називається безліччю суміжності вершини і позначається .

, , .

Якщо з випливає, що , то такий граф називається неорієнтованим.

Якщо елементами графа служать упорядковані пари

:= ,

те такий граф називається орієнтованим. У цьому випадку елементи безлічі називаються вузлами, а елементи безлічі називаються дугами.

Якщо елементом безлічі може бути пари однакових елементів , то такий елемент безлічі називається петлею, а граф називається графом з чи петлями псевдографом.

Інформація про граф задається матрицею чи суміжності матрицею інцидентності.

Матриця , де і потужності множин і відповідно називають матрицею инцидентності графа в тому випадку коли

1, якщо вершина инцидентна ребру

0, якщо вершина не инцидентна ребру

Розфарбуванням неорієнтованого графа називається таке приписування квітів (натуральних чисел) його вершинам

, де ,

що ніякі дві суміжні вершини не одержують однаковий колір. Можлива найменша кількість квітів використовуваних при розфарбуванні називається хроматичним числом.

Як приклад вирішимо задачу розфарбування для графа, зображеного на мал.5.1.

4.3. Варіанти завдань до лабораторної роботи №4.

Визначить хроматичні числа для приведених графів відповідно до вашого завдання.

№	граф	№	граф	№	граф

4.4. Контрольні питання.

1.Дайте визначення графа.

2.Які відмінності між орієнтованим і неорієнтованим графом?

3.Дайте визначення кратності в теорії графів.

4.Який граф називається псевдографом?

5.У якому виді задається інформація про графа?

5.РІШЕННЯ ЗАДАЧ З ВИКОРИСТАННЯМ ГРАФІВ. ЗНАХОДЖЕННЯ НАЙКОРОТШОГО ШЛЯХУ.

5.1. Мета роботи

Одержати практичні навички аналізу графів, використовуючи методи функціонального і логічного програмування.

5.2.Підготовка до роботи

Студент повинний знати основні визначення теорії графів.

Послідовність ребер, що з'єднують дві вершини , називається ланцюгом. Якщо цей ланцюг організований в орграфе і дуги мають одне і теж напрямок з у , то вона зветься шляху.

Довжиною шляху називається сума довжин дуг, що входять у цей шлях.

Якщо заданий орграф , у якому дуги позначені числами (числа називають чи вагами довжинами дуг), то він може бути представлений у виді матриці ваг розмірності |V|×|V|, що випливає з виду:

, для

= Weight(v_i, v_j), де i<>j, якщо в графі існує дуга (v_i, v_j);

, де i<>j, якщо немає ребра (дуги) (v_i, v_j).

Алгоритм Флойда служить для визначення

Дано: непорожній зважений граф G=(V, E) з довільними вагами ребер (дуг). Потрібно знайти довжини найкоротших шляхів між усіма парами вершин графа, якщо в графі немає циклів (контурів) негативної сумарної довжини, або знайти наявність таких контурів.

Ініціалізація:

1. Побудуємо матрицю D⁰ розмірності |V|×V|, елементи якої визначаються за правилом:

d_ii⁰= 0;

d_ij⁰= Weight(v_i, v_j), де i<>j, якщо в графі існує дуга (v_i, v_j);

d_ij⁰=+Ґ, де i<>j, якщо немає ребра (дуги) (v_i, v_j).

2. m:=0.

Основна частина:

1. Побудуємо матрицю D^m+1 по D^m, обчислюючи її елементи в такий спосіб:

d_ij^m+1=min{d_ij^m, d_i(m+1)^m + d_(m+1)j^m}, де i<>j; d_ii^m+1=0 (*).

Якщо d_im^m + d_mi^m < 0 для якогось i, то в графі існує цикл (контур) негативної довжини, що проходить через вершину v_i; ВИХІД.

2. m:=m+1; якщо m<|V|, те повторюємо крок (1),

інакше

елементи останньої побудованої матриці D^|V| дорівнюють довжинам найкоротших шляхів між відповідними вершинами;

ВИХІД.

КІНЕЦЬ

Якщо потрібно знайти самі шляхи, то перед початком роботи алгоритму побудуємо матрицю P з початковими значеннями елементів p_ij=i. Щораз, коли на кроці (1) значення d_ij^m+1 буде зменшуватися відповідно до (*) (тобто коли d_i(m+1)^m + d_(m+1)j^m<d_ij^m), виконаємо присвоювання p_ij:=p_(m+1)j. Наприкінці роботи алгоритму матриця P буде визначати найкоротші шляхи між усіма парами вершин: значення p_ij буде дорівнює номеру передостанньої вершини в шляху між i і j (або p_ij=i, якщо шлях не існує).

Примітка: якщо граф - неорієнтований, те всі матриці D^m є симетричними, тому досить обчислювати елементи, що знаходяться тільки вище (або тільки нижче) головної діагоналі.

Реалізація алгоритм Флойда

{int c[p][p];//матриця довжин дуг

int t[p][p];// матриця довжин шляхів

int h[p][p];// матриця шляхів

for(int i=0;i<p;i++)

for(int j=0;j<p;j++)

cin>> c[i][j];

for(int i=0;i<p;i++)

for(int j=0;j<p;j++)

{ t[i][j]=c[i][j];

if(c[i][j]==555) h[i][j]=0; //немає дуги з i у j

else h[i][j]=j;// є дуги з i у j

}

for(int i=0;i<p;i++)

{ for(int j=0;j<p;j++)

for(int k=0;k<p;k++)

if(i!=j&&t[j][i]!=555&& i!=k && t[i][k]!=555 &&

( t[j][k]==555 ||t[j][k]>t[j][i]+t[i][k]))

{h[j][k]=h[j][i];// запам'ятати новий шлях

t[j][k]=t[j][i]+t[i][k];// запам'ятати довжину нового шляху

}

for(int j=0;j<p;j++)

if(t[j][j]<0)break;

}

}

5.3. Варіанти завдань до лабораторної роботи №5.

Використовуючи варіанти завдань з лабораторної роботи №5, довільно задавши номера вершин і відстані, знайти мінімальний шлях, для заданих в інтерактивному режимі крапок початку і кінця шляху.

5.4. Контрольні питання.

1. Дайте визначення хроматичного числа графа?

2.Скільки фарб необхідно для розфарбування планарного графа?

3.Які відмінності точного і наближеного алгоритму розфарбовування?

4.Чи завжди алгоритм послідовного розфарбовування будує мінімальне розфарбування?

6.РІШЕННЯ ЗАДАЧ У ПРОСТОРІ СТАНІВ.

6.1. Мета роботи

Одержати практичні навички складання і рішення задач у просторі станів.

6.2.Підготовка до роботи

При підготовці до роботи студенти повинні освоїти основні підходи до рішення задач з неповною інформацією, представлення задач у просторі станів, методи пошуку в просторі станів.

Алгоритми пошуку з поверненнями.

Алгоритми з поверненням відносяться до області програмування орієнтованої на рішення задач штучного інтелекту. Алгоритми цього класу задач шукають рішення не за заданими правилами обчислень, а шляхом проб і помилок. Звичайно процес проб і помилок розбивається на двох задач. Ці задачі найбільше природно виражаються в термінах рекурсії і вимагають дослідження кінцевого числа підзадач.

Один з підходів реалізації алгоритмів з поверненням.

Procedure Tttt; (*спроба*)

Begin

Repeat

If підходить then

Його запис;

If рішення не повне then

Tttt(i+1);

If невдача then

Стирання

End;

End;

End;

Until удача OR немає кандидатів;

End;

//програма пошуку кліток на шахівниці з який кінь обійде всю

//дошку не побувавши двічі в жодній із кліток

const int dx[8]={2,1,-1,-2,-2,-1, 1, 2};

const int dy[8]={1,2,2, 1,-1,-2,-2,-1};

const int nx=15; int h[15][15];

void move (int i,int x, int y,bool &q);

void ShowDesk(int dk[ ][nx],int nx);

int n;

void main(void)

{

bool nq; char ch;

cout<<" Уведіть розмір дошки: "<<'\n';

cin>>n;

……

h[i][j]=1; //ініціалізація першого ходу

nq=false;

move(2,i,j,nq);

………

}

void move (int ii,int x, int y,bool &q)

{int k,u,v;

bool q1;

k=0;

if(q==true) return;

do

{if (k<8) k++;

else k=0;

q1=false;

u=x+dx[k];

v=y+dy[k];

if(u>=0&&u<n&&v>=0&&v<n&&h[u][v]==0)

{h[u][v]=ii;

if(ii<n*n){ move(ii+1,u,v,q1);}

else{q=q1=true;return;}

if(q1==true) {q=q1;return;}

h[u][v]=0;

} }

while(k<8);

q=q1;

}//move

Уведіть розмір дошки: 5

Рішення:0,0 Показати дошку(Y/N)?y 1 20 15 8 3 14 9 2 21 16 19 22 13 4 7 10 5 24 17 12 23 18 11 6 25	Рішення:3,1 Показати дошку(Y/N)?y 25 16 11 4 23 10 5 24 17 12 15 18 9 22 3 6 1 20 13 8 19 14 7 2 21	Продовжити(Y/N)?y Рішення:4,0 Показати дошку(Y/N)?y 25 22 17 10 5 16 11 6 23 18 21 24 15 4 9 12 7 2 19 14 1 20 13 8 3
Рішення:4,4 Показати дошку(Y/N)?y 25 20 9 14 3 8 15 4 19 10 21 24 13 2 5 16 7 22 11 18 23 12 17 6 1	Усі варіанти пройдені

6.3. Варіанти завдань до лабораторної роботи №6.

1-3.Жодна зі стріл не знаходиться на одній чи лінії діагоналі з іншої. Пересуньте 3 стріли, кожну на одну із сусідніх кліток так, щоб при цьому всі 9 стріл розташувалися знову таким чином, щоб жодна не лежала на одній прямій ні з якою іншою стрілою (Рис.7.1. – мал.7.3.).

4. Мається три стовпчики. На першому стовпчику знаходяться п'ять дисків. Вони розташовані в порядку зменшення розмірів. Необхідно перенести їх на третій стовпчик так, щоб вони розташовувалися в первісному стані. Потрібно переміщати тільки один диск, при цьому більший диск не повинний лежати на меншому (Рис.7.22.)

5-8. Є річка і через неї два мости. Необхідно знайти шлях з одного пункту в іншій при можливому руйнуванні одного моста (Рис.7.4. – мал.7.8.).

9-12. Є річка і через неї три мости. Необхідно знайти шлях з одного пункту в іншій при можливому руйнуванні одного моста (Рис.7.9. – мал.7.11.).

13-16. Є двоє дверей і один вихід. Необхідно знайти вихід (Рис.7.12. – мал.7.15.).

17.Розставити слонів на шахівниці так, щоб жоден слон не міг убити інших слонів.

18. Розставити ферзів на шахівниці так, щоб жоден ферзь не міг убити інших ферзів.

19. Мається чотири стрижні. На одному з них знаходяться диски, різних розмірів, зменьшиними до верха (піраміда). Потрібно перенести ці диски на четвертий стрижень, використовуючи два допоміжних стрижні. При цьому за один раз можна перенести тільки один диск, а більший по розміру диск не припустимо ставити на диск меншого розміру.

20. На шахівниці знаходиться тура. Необхідно її убити конем. Причому тура не повинна атакувати коня.

21. На шахівниці знаходиться офіцер. Необхідно її убити конем. Причому офіцер не повинний атакувати коня.

22.Мається чотири табурети. На крайньому табуреті знаходяться 8 голівок сиру різних розмірів, зменьшиними до верха (піраміда). Необхідно, перекладаючи круги сиру з одного табурета на іншій, перенести їх на четвертий табурет. При цьому необхідно щоб круг сиру меншого розміру не повинний покриватися навкруги більшого розміру. Потрібно вирішити цю задачу з найменшим числом перекладання. Ваша програма повинна виконати її за 33 ходи.

23. Мається чотири табурети. На крайньому табуреті знаходяться 10 голівок сиру різних розмірів, зменьшиними до верха (піраміда). Необхідно, перекладаючи круги сиру з одного табурета на іншій, перенести їх на четвертий табурет. При цьому необхідно щоб круг сиру меншого розміру не повинний покриватися навкруги більшого розміру. Потрібно вирішити цю задачу з найменшим числом перекладання. Ваша програма повинна виконати її за 49 ходів.

24. Мається чотири табурети. На крайньому табуреті знаходяться 21 голівка сиру різних розмірів, зменьшиними до верха (піраміда). Необхідно, перекладаючи круги сиру з одного табурета на іншій, перенести їх на четвертий табурет. При цьому необхідно щоб круг сиру меншого розміру не повинний покриватися навкруги більшого розміру. Потрібно вирішити цю задачу з найменшим числом перекладання. Ваша програма повинна виконати її за 321 хід.

25. На мал.16. показано вісім грибків, на першому і третьому сидять чорні жаби, а на шостому і восьмому білі жаби. Головоломка полягає в тому, щоб, пересуваючи за один раз по одній жабі в будь-якому напрямку уздовж прямих ліній від одного грибка до іншого, поміняти жаби місцями, тобто білі жаби повинні зайняти грибки 1і 3, а чорні 6 і 8. Зрозуміло, на одному грибку одночасно може знаходитися лише одна жаба (Рис.7.16.).

26.Дано шахівницю з 49 кліток (Рис.7.17.). Святий Георгій хоче вразити дракона. Покажіть як, починаючи з центральної клітки, він зуміє відвідати кожну клітку рівно один раз, проробивши безупинний ланцюжок ходів конем, наприкінці якого, на своєму останньому ході він вразить дракона.

27-30. Дан граф, що складається з двох сукупностей крапок {1,...,5} і {6,…,10}... Відстані між крапками задаються довільно. Знайти найкоротша відстань між двома довільно заданими крапками з однієї й іншої сукупності (Рис.7.18. – 7.21.).

6.4. Контрольні питання

1.Приведіть приклади класів задач, що допускають представлення в просторі станів.

2.Назвіть основні методи пошуку в просторі станів і розкрийте їхню суть.

3.Які критерії якості роботи методом перебору?

4.У чому складається підхід, заснований на зведенні задач до підзадач?

7.РІШЕННЯ ЗАДАЧ ОПТИМІЗАЦІЇ ПОТОКІВ У МЕРЕЖАХ.

7.1. Мета роботи

Одержати практичні навички рішення мережних задач. У результаті виконання лабораторної роботи студенти повинні опанувати методом Форда – Фалкерсона для максимального потоку в мережах.

7.2.Підготовка до роботи

При підготовці до роботи студенти повинні вивчити основні поняття теорії потоків у мережах . Варто звернути увагу на способи завдання мережі.

У роботі розглядається один з основних класів рішення задач про максимальний потік у мережі. Уперше ця задача була вирішена Фордом і Фалкерсоном у 1962р.

Студентам пропонується один з варіантів даного алгоритму, заснованого на побудові приєднаної мережі.

Алгоритм послідовно будує приєднану мережу, знаходить у ній шлях від джерела до стоку (якщо він існує), модифікує цей потік уздовж цього шляху.

Перемінні, стосовні до побудованої приєднаної мережі SX, відрізняються від перемінних, стосовних до вихідної мережі , першою буквою .В алгоритмі викликається функція для перебування шляху з S у стік t . Крім цього використовується функція AD, що є індикатором чи погодженості непогодженості дуг у мережі .

Вхідні дані: Мережа , пропускні здібності C[u][v]

, джерело і стік .

Вихідні дані: потік ,

BEGIN

for повторити

for повторити

if(F[u][v]<C[u][v]){CX[u][v]=C[u][v]-F[u][v];//погоджена дуга

AD[u][v]=1;}

else {CX[u][v]=F[u][v];

AD[u][v]=-1;}// неузгоджена дуга

End for(v)

Викликати функцію перебування шляху з S у t приєднаної мережі.

if PRZ==0 те пошук завершується

//(PRZ -ознака досяжності стоку- потік F максимальний)

else

{DELE min{CX[u][v];u,v WAY}

for

if (AD[u][v]==1) F[u][v]= F[u][v]+DEL;

else F[u][v]= F[u][v]-DEL;

End for(u)

END

Функція перебування шляху з S у t приєднаної мережі.

Вхідні дані: Мережа ;

Вихідні дані: Шлях з у ,

ПОЧАТОК //Begin

//вибір початкових даних для вибору нового шляху

//покласти всі позначки

покласти список

покласти =0 // шляху з S у t не існує

While ( !=0) поки список не дорівнює нулю повторювати

{

нехай - будь-яка вершина зі СПИСОК

видалити зі СПИСОК

позначити всі непомічені вершини, у які ведуть дуги з , заносячи нові вершини в СПИСОК

if ( !=0) //якщо позначена,

{{те =1

побудувати шлях зворотним переглядом із з використанням

}

перейти в КІНЕЦЬ

}

інакше

продовжувати

}

КІНЕЦЬ

7.3. Варіанти завдань до лабораторної роботи №7.

Потрібно скласти програму для перебування максимального потоку в мережі з заданими параметрами з використанням описаного вище алгоритму. Функція, що виконує пошук максимального потоку в мережі може мати наступний прототип:

void maxfl (int N, int M[N][N], int F[N][N], int C[N][N], int FM[N][N]);

N – кількість вершин у мережі

M – матриця суміжності

C – матриця пропускних здібностей

F – матриця потоків по кожній дузі

FM – величина отриманого максимального потоку.