Учитель інформатики Клебан В.В.
Семінар - практикум
«Як складне зробити простим?
Методи розв’язування олімпіадних задач.
Задачі на графи»
Вчитель інформатики Клебан В.В.
Нас не зламати!
Вчитель інформатики Клебан В.В.
З досвіду роботи вчителем інформатики!
Як заохотити дітей до навчання (програмування)?
Вчитель інформатики Клебан В.В.
З досвіду роботи вчителем інформатики!
З чого починати?
Вчитель інформатики Клебан В.В.
З чого починати?
Вчитель інформатики Клебан В.В.
Задачі на Графи
Теорія графів — розділ математики, що вивчає властивості графів. Наочно граф можна уявити як геометричну конфігурацію, яка складається з точок (вершини) сполучених лініями (ребрами).
Графи - це метод візуальної ілюстрації даних та відношень між ними.
Вчитель інформатики Клебан В.В.
Методи і прийоми
Застосування
Пошук найкоротшого шляху(числа ходів)
Знаходження найменшої ваги ребер
Пошук компонент зв'язності
2. Обхід в глибину(DFS)
Застосування
Пошук будь-якого шляху у графі.
Пошук лексикографічно першого шляху в графі.
Перевірка чи одна вершина дерева є предком іншої.
Приклади графів
Вчитель інформатики Клебан В.В.
Немирів
Салаші
Смолин
Яворів
Вербляни
Дрогомишль
Грушів
Вороблячин
Завадів
133
159
97
75
33
13
22
93
17
44
36
8
73
Приклади графів
Вчитель інформатики Клебан В.В.
Вчитель інформатики Клебан В.В.
Пошук в ширину (шукаємо найкоротші відстані від стартової до всіх інших )
Вчитель інформатики Клебан В.В.
Пошук в ширину (шукаємо найкоротші відстані від стартової до всіх інших )
4. Для усіх непозначених сусідів вершини з черги:
4.1 Оновимо усі відстані від поч. вершини
4.2 Позначимо їх
4.3 Додамо в кінець черги
5. Видалимо вершину з початку черги
6. Якщо черга непорожня перейдемо до п.3
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 1. Подарунок Левчика!
Левчик і Гануся були однокласниками, які до безтями були закохані один в одного! У 2021-22 навчальному році вони разом навчались у 8 класі Вороблячинського ЗЗСО І-ІІ ступенів ім. Героя України В. Коцюби та були найкращими учнями класу. Важкі часи були, оскільки у цей час прогресував страшний коронавірус. Усі діти спілкувались та навчались дистанційно і Левчику з Ганусею було неймовірно важко не бачити один одного.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 1. Подарунок Левчика!
У цей час вони захопились інформатикою і програмуванням. Гануся дуже швидко і легко навчалась, а Левчику прорамування давалось важче навіть попри те, що він брав додаткові уроки з інформатик, що й досі робить.
Оскільки Левчик і Гануся проживали по різні сторони с.Вороблячин, Левчик вирішив передати Ганусі подарунок через вчителів.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 1. Подарунок Левчика!
адже деяким вчителям директор дозволив до 10 хвилин спілкуватись прийшовши до школи, але не більше ніж 2 вчителі одночасно, а також деяким вчителям дозволив спілкуватись із найкращими учнями 8-го класу Левчиком і Ганусею, гарантовано що спілкуватись учням заборонено.
Гануся випадково в Інтернеті знайшла графік чергування вчителів на M днів, який склав директор.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 1. Подарунок Левчика!
Кожен вчитель, з Левчиком і Ганусею пронумерований від 1 до N. Гануся замітила, що директор не поставив на чергування їх з Левчиком разом. Їх кохання велика таємниця і Гануся вирішила дізнатись скільки мінімально вчителів дізнається про їх секрет, якщо вони оптимально
передаватимуть подарунок, так щоб вона його отримала, адже вона розуміє, якщо вчитель передаватиме подарунок він буде знати про їх таємницю. Допоможіть Ганусі.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 1. Подарунок Левчика!
Вхідні дані
У першому рядку міститься чотири натуральних числа - N, кількість вчителів з Левчиком і Ганусею, M кількість днів у графіку директора, L та H,(1 ≤ N ≤ 1000, 1 ≤ L,H ≤ N) - номери Левчика та Ганусі.
У наступних M рядках пара чисел і, j (0 ≤ і, j ≤ 1000)– номери учасників освітнього процесу, що чергують.
Вихідні дані
Виведіть К - мінімальну кількість вчителів, що знатимуть таємницю.
Якщо передати подарунок неможливо виведіть -1
Подарунок Левчика (рис б)
Вчитель інформатики Клебан В.В.
7
5
2
6
4
ЛЕВЧИК
3
1
ГАНУСЯ
Гуцова Л.
Романів О.
Мельнічук О.
Манько Н.
Мусаковська Н.
Баран І.
Подарунок Левчика
Вчитель інформатики Клебан В.В.
4
8
1
11
2
10
5
9
ГУЦОВА Л.
ШОВКУН Т.
РЯБЕЦЬ В.
ЛЕВЧИК
КЛЕБАН В.
МАНЬКО Н.
БАРАН І.
ГАНУСЯ
3
КРІЛЬ Г.
6
МАНЬКО А.
Вчитель інформатики Клебан В.В.
Пошук в ширину (Подарунок Левчика)
Вчитель інформатики Клебан В.В.
Пошук в ширину (Подарунок Левчика)
for i in range(m): - введеня пари чергових
x,y=list(map(int,input().split()))
g[x-1][y-1]=1 - якщо чергують відстань 1
g[y-1][x-1]=1 - пам'ятаємо рахунок поч. від 0 w.append(l-1) - добавляємо в чергу поч. точку
while w!=[]: - поки черга не пуста
for i in range(n): - перевіряємо усіх, хто чергує з вибраним вчителем
Вчитель інформатики Клебан В.В.
Пошук в ширину (Подарунок Левчика)
__ __if tf[i]==False and g[w[0]][i]==1: Якщо i-тий вчитель ще не позначений і чергує з тим що 1 в черзі
__w.append(i) додаємо його остатнього в чергу
__if v[w[0]]+1<v[i]: оновлюємо відстань до вителя
__ __v[i]=v[w[0]]+1
__ tf[w[0]]=True - позначаємо і-го вчителя
__w=w[1::] - видаляємо його з черги
Вчитель інформатики Клебан В.В.
Виведення результатів (Подарунок Левчика)
if v[h-1]==10**9:
print(-1) - вивести -1 якщо неможливо передати
else: - вивести відстань - 1
print(v[h-1]-1)
__
Вчитель інформатики Клебан В.В.
Виведення результатів (Подарунок Левчика)
7 8 1 7
1 3
3 2
2 4
2 1
3 5
3 6
5 7
5 6
2 - результат
7 8 1 4
1 3
3 2
2 4
2 1
3 5
3 6
5 7
5 6
1
7 8 1 7
1 3
3 2
2 4
2 1
3 6
5 7
Передати неможливо
Вхідні дані #1
Вхідні дані #2
Вхідні дані #3
Вчитель інформатики Клебан В.В.
Виведення результатів (Подарунок Левчика)
11 13 1 9
1 2
6 2 8 9
1 4 8 10
4 3 9 10
3 2 10 11
2 8 5 9
3 8
5 4
2 - результат
Вхідні дані #4
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 2. Втрата Левчика!
У 2022 році навчившись боротись із пандемією коронавірусу, розробивши алгоритми дій для захисту від вірусу вчителі і учні Вороблячинського закладу освіти отримали імунітет від нього та повернулись до навчання в очному режимі. Це дуже втішило закоханих. Не такий страшний цей вірус – комп’ютерний
вірус I LOVE YOU набагато сташніший, тай наслідки від нього величезні ($10.000.000.000).
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 2. Втрата Левчика!
Усі учасники освітнього процесу (вчителі та учні) невтомно працювали. Особливо відзначались найкращі учні 9-го класу Гануся з Левчиком, все ж кохання допомагає. Гануся вчергове перемогла на обласній олімпіаді програмування та готувалась до її IV етапу, для Вороблячинського ЗЗСО це був великий успіх. Усі її вітали.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 2. Втрата Левчика!
На третій день відбірково - тренувальних зборів до участі у IV етапі Всеукраїнської учнівської олімпіади з інформатики Гануся лише зміцнила свою перевагу над конкурентами (хіба фізмат ліцей це конкуренти для неї ?), коли страшна звістка сколихнула весь світ 24 лютого – збройна агресія росії проти України.
Ганусі і її вчителю було надзвичайно прикро, але ще болючіше було їй залишати коханого Левчика, адже вона та її батьки на наступний день вирішили поїхати у іншу державу – Щастиляндію.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 2. Втрата Левчика!
Але через усі дороги між містами України в цей час величезні затори до кордону.
Ганусі відомо, що на даний момент існує N безпечних населених пунктів, з’єднаних дорогами. Деякі дороги зруйновані бомбардуванням російськими терористами. Батьки попросили Ганусю порахувати, яка найменша кількість автомобілів до кордону?.
Згадавши уроки інформатики, а особливо практичні уроки “Як складне зробити простим?, методи розв’язування олімпіадних задач, задачі на графи.”-вона швидко склала матрицю суміжності міст і доріг між ними та передала Левчикові щоб він порахував, адже її комп’ютер поламався.
Допоможіть Левчику впоратись із завданням.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Вхідні дані
У першому рядку міститься три натуральних числа - N, кількість міст, L та H,(1 ≤ N ≤ 1000, 1 ≤ L,H ≤ N) - номери Левчика та Ганусі.
Далі у n рядках по n чисел - матриця суміжності міст: в i-му рядку на j-му місці стоїть "1", якщо міста i та j з'єднані дорогою, і "0", якщо дороги між ними немає. На головній діагоналі матриці стоять нулі.
Вихідні дані
Виведіть S - мінімальні кількість автомобілів по дорозі до кордону
Якщо шляху немає виведіть -1
Задача 2. Втрата Левчика!
Розглянемо:�Втрата Левчика
Вчитель інформатики Клебан В.В.
4
6
1
9
2
8
5
7
Немирів
Салаші
Смолин
Яворів
Вербляни
Дрогомишль
Грушів
Вороблячин
3
Завадів
133
159
97
75
33
13
22
93
17
44
36
8
73
Втрата Левчика
Вчитель інформатики Клебан В.В.
4
6
1
9
2
8
5
7
Немирів
Салаші
Смолин
Яворів
Вербляни
Дрогомишль
Грушів
Вороблячин
3
Завадів
133
159
75
13
22
17
44
36
8
73
Вчитель інформатики Клебан В.В.
Пошук в ширину (Втрата Левчика – що міняємо?)
n,m,h=list(map(int, input().split())) - введення n,l,h
g=[0]*n - масив суміжності
tf=[False]*n - точки відвідані
v=[10**9]*n - відстань до точок від заданої
w=[] - черга
v[l-1]=0 - відст. до поч. точки(Левчика)
for i in range(n): - матриця суміжності
g[i]= list(map(int, input().split()))
Вчитель інформатики Клебан В.В.
Пошук в ширину (Подарунок Левчика)
w.append(l-1) - добавляємо в чергу поч. точку
while w!=[]: - поки черга не пуста
for i in range(n): - перевіряємо усіх, хто чергує з вибраним вчителем
if g[w[0]][i]!=0: Якщо є сполученняi
if tf==False and : w.count(i)==0і вершина не
позначена і її немає в черзі
w.append(i) додаємо її остат. в чергу
if v[w[0]]+ g[w[0]][i] <v[i]: оновлюємо відстань
v[i]=v[w[0]]+ g[w[0]][i]
Вчитель інформатики Клебан В.В.
Виведення результатів (Втрата Левчика)
if v[h-1]==10**9:
print(-1) - вивести -1 якщо неможливо передати
else: - вивести відстань - 1
print(v[h-1])
Вхідні дані #1 2 Вихідні дані #1 2
7 1 4 Якщо 7 6 то 12
0 2 13 99 0 0 0
2 0 1 7 0 0 0
13 1 0 3 5 27 0
99 7 3 0 0 0 0
0 0 5 0 0 1 12
0 0 27 0 1 0 3
0 0 0 0 12 3 0
Вчитель інформатики Клебан В.В.
Виведення результатів (Втрата Левчика)
Вхідні дані #3 Вихідні дані #3
9 1 7 262
0 133 0 159 0 0 0 0 0
133 0 17 0 0 75 0 0 0
0 17 0 8 0 44 0 0 0
159 0 8 0 97 0 0 0 0
0 0 0 97 0 0 73 0 0
0 75 44 0 0 0 93 33 0
0 0 0 0 73 93 0 36 22
0 0 0 0 0 33 36 0 13
0 0 0 0 0 0 22 13 0
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 3. Перемога і кохання
Попри війну з росією учителі і учні в невеличкому селі Вороблячин продовжували працювати. Вчителі ставали лауреатами конкурсу «Вчитель року 2023», а здобувачі освіти переможцями різних олімпіад і конкурсів районного і обласного рівня. Левчик і Ганнуся закінчили школу з відзнакою, а заклад освіти змінив свою назву на Вороблячинська гімназія ім.Героя України В.Коцюби.
Левчик дуже сумував за Ганнусею і попри молодий вік пішов на фронт воювати, до односельчан, яких там було чимало, щоб пришвидшити перемогу.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 3. Перемога і кохання
І ось настав 2024 рік – Україна ПЕРЕМОГЛА московитів. Левчик повернувся у рідне село та вирішив полетіти і привезти чим швидше кохану Ганнусю додому, щоб бути разом. Проте він багато донатив на ЗСУ, тому був обмежений у фінансах.
Левчику відомо, що в Світі є N населених пунктів, деякі з них з’єднані авіарейсами, у кожному з населених пунктів є аеропорти у яких квиток коштує Аі грн. у будь-яке місто чи село.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Задача 3. Перемога і кохання
Левчик, щоб доказати Ганусі що він покращив знання з інформатики вирішив порахувати за скільки днів К він найшвидше зможе зустрітися з Ганнусею, якщо переліт з одного міста в інше займає 1 день. Також Левчику цікаво, який маршрут йому потрібно пройти до Ганнусі і додому, щоб потратити якомога менше грошей. Врахуйте що в зворотньому напрямі Левчику прийдеться платити вдвічі більше.
Розглянемо задачу
Вчитель інформатики Клебан В.В.
Вхідні дані
У першому рядку міститься три натуральних числа - N, кількість міст, L та H,(1 ≤ N ≤ 1000, 1 ≤ L,H ≤ N) - номери Левчика та Ганусі.
У другому рядку N чисел Аі (0 ≤ Аі ≤ 1000)– вартість квитків у кожному місті.
Далі у n рядках по n чисел - матриця суміжності міст: в i-му рядку на j-му місці стоїть "1", якщо міста i та j з'єднані дорогою, і "0", якщо дороги між ними немає. На головній діагоналі матриці стоять нулі.
Вихідні дані
У першому рядку виведіть К
У другому виведіть S - мінімальні затрати Левчика
У третьому виведіть через пропуск числа d[L], d[i], ..., d[L], де d[i] номери міст шляху Левчика.
Якщо шляху немає до Ганусі немає виведіть -1. Якщо шляху назад немає то в другому рядку виведіть - 2
Задача 3. Перемога і кохання
Перемога і кохання
Вчитель інформатики Клебан В.В.
4
1
2
5
3
6
1
1
2
2
2
4
7
7
7
15
15
15
7
4
1
4
2
Вхідні дані #1 Вихідні дані #1
6 5 2 2
15 4 7 4 2 1 55
0 1 1 0 0 0 5 6 2 1 3 5
1 0 0 0 0 0
1 1 0 0 1 0
0 0 0 0 0 0
0 0 1 1 0 1
0 1 0 0 1 0
Вхідні дані #2 Вихідні дані #2
6 5 4 1
15 4 7 4 2 1 -2
0 1 1 0 0 0
1 0 0 0 0 0
1 1 0 0 1 0
0 0 0 0 0 0
0 0 1 1 0 1
0 1 0 0 1 0
Вхідні дані #3 Вихідні дані #3
6 4 5 -1
15 4 7 4 2 1
0 1 1 0 0 0
1 0 0 0 0 0
1 1 0 0 1 0
0 0 0 0 0 0
0 0 1 1 0 1
0 1 0 0 1 0
Перемога і кохання
Вчитель інформатики Клебан В.В.
9
Салаші
Смолин
22
4
6
1
2
8
5
7
Немирів
Яворів
Вербляни
Дрогомишль
Грушів
Вороблячин
3
Завадів
97
33
13
93
36
8
73
8
Вчитель інформатики Клебан В.В.
Пошук в ширину (Задача 3. Перемога і кохання)
n,l,h=list(map(int, input().split())) - введення n,l,h
k=list(map(int, input().split()))
global g, v, v1
g=[0]*n - масив суміжності
а=[0]*n - масив що зберігає з якої вершини
ми прийшли у дану вершину
for i in range(n): - матриця суміжності
g[i]= list(map(int, input().split())) s=0 сума поїздки Левчика
Вчитель інформатики Клебан В.В.
Пошук в ширину (Задача 3. Перемога і кохання)
def BFS(start): - створюємо функцію для
пошуку мін. затрат Левчика
global g, v, v1
tf=[False]*n
v=[10**9]*n
l=start
v[l-1]=0
v1=[10**9]*n
v1[l-1]=0
a[l-1]=0
w=[]
w.append(l-1)
while w!=[]:
Вчитель інформатики Клебан В.В.
Пошук в ширину (Задача 3. Перемога і кохання)
while w!=[]:
for i in range(n):
if g[w[0]][i]!=0:
if tf[i]==False:
w.append(i)
if v[i]>k[w[0]]+v[w[0]]:
v[i]=v[w[0]]+k[w[0]]
a[i]=w[0]
if v1[i]>1+v1[w[0]]:
v1[i]=v1[w[0]]+1
tf[w[0]]=True
w=w[1::]
return v повертаємо відстані до вершин від початкової
Вчитель інформатики Клебан В.В.
Пошук в ширину (Задача 3. Перемога і кохання)
start=l
s=0
BFS(start) запускаємо ф-ю пошуку від Левчика
s=s+v[h-1] мін. Вартість дороги до Ганнусі
if v[h-1]==10**9:
print(-1) якщо немає дороги виводим -1
else:
print(v1[h-1]) мін. кількість днів польоту до Ганнусі
z=[ ] шлях до Ганусі (перевернутий)
z.append(h) додаємо кінцеву точку - місто Ганнусі
i=h-1
while a[i]!=(l-1): відновлюємо шлях поки не знайдем
початкову вершину – місто Левчика
z.append(a[i]+1)
i=a[i]
z.append(l) a=[-1]*n z=z[::-1] перевертаємо шлях
Вчитель інформатики Клебан В.В.
Пошук в ширину (Задача 3. Перемога і кохання)
start=h
BFS(start)
if v[l-1]==10**9:
print(-2)
else:
s=s+v[l-1]*2
i=l-1
z1=[ ]
while a[i]!=(h-1):
z1.append(a[i]+1)
i=a[i]
z1=z1[::-1]
z=z+z1
z.append(l)
print(s)
print(z)
Вчитель інформатики Клебан В.В.
Пошук в ширину (Задача 3. Перемога і кохання)
4
6
1
2
8
5
7
Немирів
Яворів
Вербляни
Дрогомишль
Грушів
Вороблячин
3
Завадів
97
33
13
93
36
8
29
8
9
Смолин
22
Вхідні дані #4 #4
9 1 7
8 93 8 97 29 33 13 36 22
0 1 0 1 0 0 0 0 0
1 0 1 0 0 1 0 0 0
0 1 0 1 0 1 0 0 0
1 0 1 0 1 0 0 0 0
0 0 0 1 0 0 1 0 0
0 1 1 0 0 0 1 1 0
0 0 0 0 1 1 0 1 1
0 0 0 0 0 1 1 0 1
0 0 0 0 0 0 1 1 0
Вихідні дані #4
3
412
1 2 6 7 6 2 1 шлях Левчика
Салаші
Вчитель інформатики Клебан В.В.
“Без захоплення і натхнення без осмислення розумової праці як процесу пошуку та знахідок навчання перетворюється у зазубрювання; з нього випадає головна мета школи – загальний розумовий розвиток, формування допитливого розуму, виховання ваги знань”
В.Сухомлинський
Далі буде…