top>
6
9
4
[4,5]
5
0
3
5
6
7
4
[5]
Час роботи алгоритму пропорційно N 2 . h3> Алгоритм Флойда (найкоротші шляхи між усіма парами вершин).
Дано. Орієнтований граф G = , s - вершина джерело; матриця суміжності A (A: array [1 .. n, 1 .. n] of integer); для будь-яких u, v € V вага дуги ненегативний (А [u, v]> = 0). Результат. Матриця D найкоротших відстаней між усіма парами вершин графа і найкоротші шляхи.
Ідея алгоритму. Позначимо через D m [i, j] оцінку найкоротшого шляху з i в j з проміжними вершинами з безлічі [1 .. m]. Тоді маємо: D 0 [i, j]: = A [i, j] і Друге рівність вимагає пояснення. Нехай ми знаходимо найкоротший шлях з i в j з проміжними вершинами з безлічі [1 .. (m +1)]. Якщо цей шлях не містить вершину (m +1), то D ( m +1) [i, j] = D m [i, j]. Якщо ж він містить цю вершину, то його можна розділити на дві частини від i до (m +1) до j. Час роботи алгоритму пропорційно N 3 .
Глава 2 Система завдань і вправ.
Класифікація задач.
Набір завдань, розроблений нами і викладений нижче можна систематизувати за наступними критеріями:
За тематикою.
В В В За рівнем складності завдання.
В В В В В В В
Завдання високого рівня складності : це завдання олімпіадного рівня, що вимагають глибокого знання предмету, а також комплексного підходу до вирішення завдання (Приклад для нашого набору завдань, завдання про роботів, задача про кімнатах музею). p> Завдання середнього рівня складності: це завдання, що вимагають хороших знань предмета і навичок застосування знань на практиці, т.е в процесі вирішення завдань (Приклад: задача про сім'ях, завдання про футболістів, завдання про міліцію і диспетчера).
Завдання низького рівня складності: це завдання, для вирішення яких необхідні загальні знання предмету і не вимагають особливих навичок застосування знань на практиці, т.к. дані завдання спрямовані на формування даних навичок.
В
Ситуативні завдання: це завдання, формулювання яких являє собою ситуацію з життя. Це необхідно для більш наочного подання завдання, а також для того, щоб зробити завдання більш цікавою для вирішення. p> Завдання з суворою формулюванням: це з...
