Бібліотечка вчителя інформатики
Максименко М. М.
Деякі прийоми розв’язування олімпіадних задач з інформатики
(методичний посібник
для вчителів інформатики та учнів)
Конотоп 2008
Зміст
Теорія чисел в програмуванні 2
Алгоритм знаходження всіх простих чисел, що не перевищують деякого заданого натурального числа n. («Решето Ератосфена») 4
Кількість усіх можливих дільників даного натурального числа 4
Знайди число 5
Найбільший спільний дільник 5
Більярд 6
Діагональ 6
Точки перетину 7
Ланцюговий дріб 7
Ознаки подільності 7
Комбінаторні сполучення 8
Підрахунок кількості комбінаторних сполучень 8
Генерація всіх можливих переставлень. Задача1. 8
Генерація всіх можливих переставлень. Задача2. 9
Генерація всіх можливих розміщень 9
Генерація всіх можливих розміщень. Задача2. 10
Генерація всіх можливих сполучень 10
Генерація всіх можливих сполучень. Задача2. 11
Поліноми 11
Додавання поліномів 11
Множення поліномів 12
Ділення поліному на поліном 12
«Закодовані» малюнки 13
Опрацювання матриць, що складаються з 0 та 1. 13
Кути 13
Прямокутники 15
Ламана 16
Різнобарвні прямокутники 17
Зафарбування 18
Мікроорганізми 18
Бактерії 19
Трафарет 21
Плакати 21
Плакати2 23
Калькулятори 23
Калькулятор 23
Калькулятор. Задача 2 24
Знаки арифметичних дій 24
Знаки арифметичних дій. Задача 2 24
Література 25
Теорія чисел в програмуванні
Ознайомлення з теорією чисел – хороша школа для тих, хто прагне стати програмістом. Нагадаємо деякі відомості, що можуть стати нам в пригоді.
Розглянемо довільне натуральне число n. Числа, на які ділиться n, називаються його дільниками. Усі натуральні числа можна поділити на два класи:
Числа, які не діляться на жодне число, крім одиниці й самого себе – прості числа.
Числа, які, крім одиниці й самого себе, мають ще й інші дільники (такі дільники називатимемо Власними дільниками) – складені числа.
Число a називається дільником числа n, якщо існує таке ціле число b, що n=a*b. Очевидно, число b також буде дільником n.
Близнятами називаються два простих числа, які відрізняються лише на дві одиниці, тобто є послідовними непарними числами. Наприклад, 5 і 7, 11 і 13.
Довільне складене число n можна розкласти на добуток простих чисел, кожне з яких буде власним дільником n. Якщо натуральне число n складене, то воно має хоча б один простий дільник, не більший від  .
Алгоритм знаходження всіх простих чисел, що не перевищують деякого заданого натурального числа n. («Решето Ератосфена»)
Випишемо всі натуральні числа від 2 до n. У цій послідовності викреслимо кожне друге число після 2, тобто числа 4, 6, 8, … Потім викреслимо кожне третє число після 3 (враховуючи числа, викреслені раніше), тобто ті, що діляться на 3. Закінчивши другій етап викреслювань, виконаємо операцію для числа 5, потім для числа 7 і т.д. отже, ми викреслимо з написаного ряду всі складені числа. А не викресленими залишаться всі прості числа, що не перевищують n.
Цей метод можна дещо спростити. По-перше, досить виписувати лише непарні числа, що не перевищують n, залишаючи на початку ряду число 2, і робить зазначені вище викреслювання, але вже починаючи з трійки. По-друге, тільки-но дійдемо до першого простого числа, більшого від , викреслювання можна більше не робити. Всі числа, що залишилися не викресленими, аж до самого n, будуть простими.
Кожне натуральне число, крім одиниці, можна розкласти на добуток простих множників єдиним способом. Дуже часто трапляється, що кілька із знайдених простих дільників деякого натурального числа рівні. Тоді в розкладі цього числа множники, що повторяються, записуємо у відповідних степенях:
Ця остаточна формула розкладання натурального числа на прості множники називається канонічним розкладом числа. Тут k – кількість різних простих дільників числа.
Кількість усіх можливих дільників даного натурального числа  дорівнює: 
Сума всіх дільників числа дорівнює  .
Досконалими називаються числа, для яких s(n)=2n.
Якщо  - просте число, то число  - досконале.
Найменше спільне кратне K(a, b) двох натуральних чисел a і b є дільником будь-якого іншого спільного кратного цих чисел.
Найбільший спільний дільник D(a, b) двох натуральних чисел a і b ділиться на будь-який інший спільний дільник цих чисел.
Дуже важливою є така формула K(a, b)*D(a, b)= a*b
Алгоритм знаходження найбільшого спільного дільника (Алгоритм Евкліда)
Evclid(a, b)
if b=0
then return a
else return Evclid(b, a mod b)
або
Evclid(a, b)
if a=b
then return a
else begin if b>a
then b:=b-a
return Evclid(a, b)
else a:=a-b
return Evclid(a, b)
Для довільних натуральних чисел a і b можна знайти цілі (додатні або від’ємні) числа k та l , що D(a, b)=k*a+l*b.
Якщо  та  , тоді  .
Ланцюговий дріб:
 Скорочено цей дріб позначають так: 
Наприклад 
Властивості остач
Якщо число  внаслідок ділення на число b дає остачу  , а число  остачу то:
 дасть остачу  ,
 дасть остачу  ,
 дасть остачу  ,
 дасть остачу 
При діленні на те саме число b.
Останню властивість особливо зручно використовувати тоді, коли дане число при ділення на якесь інше число дає остачу 1. у такому разі будь-який натуральний степінь даного числа при діленні на те саме число даватиме в остачі 1.
Ознаки подільності
Нехай 
Подільність на 2:  (mod 2)
Подільність на 3:  (mod 3)
Подільність на 5: =0 або =5
Подільність на 11:  (mod 11)
Подільність на 7:  далі коефіцієнти повторюються (mod 11)
|