Машина Тюрінга
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
к №3
Цикл по j, починається із i+1, триває до n.
Блок №4
Умова, яка порівнює елементи.
Блок №5
Процедура обміну місцями елементів.
Блок №6
Вихід з циклу по j.
Блок №7
Вихід з циклу по і.
Блок №8
Вивід на екран новоутвореного масиву А.
Мал1.2 Опис процедури Obmin
Блок №1
Надання змінній k значення і -ого елементу.
Блок №2
Надання і - тому елементу значення j-ого елемента.
Блок №3
Надання j - ому елементу значення k.
Математичний опис
- i:=1
- k привласнюваний індекс найменшого елементу підпослідовності ai,., an.
3. Якщо i?k, то ai і ak обмінюємо місцями.
. I:=i+1. Якщо i<?n, то переходимо на п. 2, інакше сортування закінчене.
Для складання алгоритму рішення цієї задачі скористаємося, як завжди, методом покрокової деталізації. Звернемо увагу на те, що для отримання результату нам потрібне N - 1 раз знаходити мінімальне значення в таблиці, довжина якої зменшується і визначається тим, який раз ми приступили до пошуку мінімуму. Так, в 1-й раз ми шукаємо мінімум серед елементів A1, A2,.., AN, в 2-ій - серед A2,.., AN, в i -й - серед Ai,.., AN. І ще один важливий момент. Оскільки після знаходження мінімального елементу його треба буде поміняти місцями з іншим елементом таблиці, то треба запам'ятати номер мінімального. Отже, перший крок деталізації можна представити таким оператором циклу : := 1
I<=N - 1
накінець знайти мінімальний елемент і його номер в таблиці Ai,.., АN (1) поміняти місцями Аi і мінімальний елемент (2)
:= I+1
кінець
Ще раз приведемо розроблений раніше алгоритм пошуку мінімуму.
1. K:= I; X:= A[I]; J:= I+1
якщо J<=N
інакше якщо A[J]<X
тоді X:= A[J]; K:= J
кінець
кінець
Після виконання цих дій значенням змінної Х буде значення мінімального серед елементів Ai,.., AN, а значенням До - номер цього елементу. Отже, пункт 2 можна записати конкретніше:
поміняти місцями елементи A1 і AK (2)
Відомо, що в загальному випадку для взаємної перестановки в пам'яті двох змінних потрібна третя, допоміжна, :
. C:= A[I]; A[I] := A[K]; A[K] := C.
Помітимо, проте, що в нашій конкретній ситуації ця третя змінна не потрібна, оскільки її роль грає змінна Х з пункту 1:
. A[K] := A[I]; A[I] := X.
Ми заощадили одне привласнення, але це немало, оскільки дії виконуються в циклі багаторазово.
Тепер можна записати повністю алгоритм сортування простим вибором.
алг ВИБІР(цілий N, дроб таб A[1: N])
арг A, N
рез A
нач дроб X, цілий I, J, K := 1
якщо I<=N - 1
інакше K:= I; X:= A[I]; J:= I+1
якщо J<=N
інакше якщо A[J]<X
тоді X:= a[J];K:= J
кінець:= J+1 кінець[K] := A[I]; A[I] := X; := I+1
кінець
кінець.
Контрольний приклад
Показане вище сортування працює за таким принципом:
1. Із заданого рядка масиву елементів знаходиться найменший. Цей елемент ставиться на перше місце, і рядок відповідно записується під індксом і=1
. Потім із рядка під індексом i=1 вибирається найменший елемент окрім прешого, і міняється із другим, тобто N-1.
. Із рядка і=2 вибираємо найменший елемент, і міняємо його із третім N-2.
. Із рядка і=3 вибираємо найменший елемент, і міняємо його із N-3. Оскільки в даному випадку елемент що стоїть на четвертій позиції є найменший, то він там і залишається.
. Із рядка і=4 вибираємо найменший елемент, і міняємо його із N-4.
. Із рядка і=5 вибираємо найменший елемент, і міняємо його із N-5.
. Із рядка і=6 вибираємо найменший елемент, і міняємо його із N-6.
. Із рядка і=7 вибираємо найменший елемент, і міняємо його із N-7.
.Оскільки всі елементи відсортовані, то рядок і=7 записуємо в результат.
Хвилевий алгоритм пошуку довгого шляху на зваженому орієнтованому графові.
Постановка задачі
Хвилевий алгоритм дістав свою назву через те, що сам принцип його функціонування заснований на "випусканні хвилі", якого-небудь гіпотетичного обурення за результатами якого є можливість судити про кількість суміжних з виділеною вершин, а так само про відстань(довжині дуги) до кожної з них.
Очевидно, що до кожної вершини можуть йти від вершини X н декілька шляхів суми довжин дуг по різних шляхах різні . При пошуку найдовшого шляху слід вибирати максимальну суму. Хвилі поширення ваги по різних шляхах доходять до кожної вершини послідовно, при черговій хвилі необхідно залишити або стару вагу вершини, або замінити його на новий (більший). Тому при розрахунку ваги вершини X i за рахунок хвилі, що підійшла до неї по дузі (X j, X i), виробляється обчислення ваги V i по формулі
i =max(V i, V j + l ji).
Ваги вершин в процесі поширення хвилі можуть мінятися неодноразово. При кожній зміні ваги V i вершини це збільшення ваги необхідно передати вершинам результату X i, тобто потрібні спеціальні засоби, що відбивають факти отримання вершиною нової ваги і передачу його іншим вершинам. Як такий засіб використовується масив номерів вершин, що отримали нову вагу(при кожній зміні ваги номер вершини включається в цей масив, якщо його там не було, при передачі ваги виключається).
Словесний опис алгоритму
1.Усі вершини графа отримують ваги V i =0, номер вершини X н
заноситься в масив М номерів вершин, що змінили вагу. Інші вершини X i не потрапляють в масив М.
- Якщо масив М порожній, виконується п. 3, інакше вибирається з
виключенням з його чергова вершина X i і перераховуються ваги вершин, що належать результату G(X i) вершини X i, :
Якщо вага V j