Сайт підготовки до олімпіади з інформатики

3.

5. Вгадати число можна за 4 спроби, використовуючи метод поділу по полам.

7.

http://ega-math.narod.ru/Quant/Shestpl.htm

9.Ідея. Розв’язком задачі є числовий ряд Фібоначі.

12.Наявна матриця розміру M*N, що являє собою деякий лабіринт. Одна клітинка лабіринту є входом а інша виходом. Знайти найкоротший шлях від входу до виходу, якщо він існує.

Вхідні данні : файл Labirint.dat, де першим рядком йде два числа N та M (0<N,M<100), а далі M рядків по N чисел відокремлених пробілами. Всі числа Amn можуть приймати значення 1,2,3,4. 1 - ділянка, що можна пройти. 2 - стіна. 3 - вхід. 4 - вихід.

Вихідні данні: число T>0, яке дорівнює довженні найкоротшого шляху, або -1, якщо такого шляху не існує.

Аналіз задачі.

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

Одним з найбільш ефективних алгоритмів пошуку найкоротшого шляху є алгоритм хвилі. Хвильовий алгоритм полягає в наступному:

1.        кожної клітинок i приписується число T - тимчасова мітка.

2.        заводяться два списки "фронту хвилі" NF і OF, а також перемінна T (поточний час);

3.        OF:={u1}; NF:={}; T:=1;

4.        для кожної з вершин i, що входять у OF, проглядаються сусідні вершини j, і якщо T[j] = -2, то T[j]=T, NF=NF + {j}.

5.        якщо NF = {}, то шлях не існує, перехід до кроку 8.

6.        якщо одна з вершин збігається з u2, то знайдений найкоротший шлях довжини T, перехід до кроку 8;

7.        OF:=NF; NF:={}; T:=T+1; повернення до кроку 4.

8.        Відновлюємо шлях проходячи масив P, шукая серед сусідів даної клітинки таку, щоб номер ітерації хвилі у неї був найменшим.

Джерела інформації

http://www.problems.ru

http://olympiads.ru