РОЗВ'ЯЗОК ВСТУПНОЇ РОБОТИ 2011 Печать
Добавил(а) Administrator   
21.09.11 10:25

3.

!2 л

8 л

 5 л

12

0

0

4

8

0

0

8

4

8

4

0

3

4

5

3

8

1

11

1

0

6

1

5

6

6

0

 

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

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

 

 

 

 

 

 

 

1

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

 

 

 

2

 

 

 

 

 

3

 

 

 

3

 

 

 

3

 

 

 

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

 

4

 

4

 

4

 

4

 

4

 

4

 

4

 

 

7.

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

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

Кількість сходинок

Варіанти

Кількість способів

1

1

1

2

11, 2

2

3

111, 12, 21

3

4

1111, 112, 121, 211, 22

5

5

 

8

6

 

13

7

 

21

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, якщо такого шляху не існує.

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

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

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

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