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

Шкільний курс інформатики крім уявлень про засоби сучасних інформаційних технологій,  повинний дати знання основних понять алгоритмізації.  Важливість розділу “Алгоритмізація і програмування ” ніхто не заперечує. Опановуючи  алгоритмізацію і програмування учні розвивають  свій   інтелект,  пам'ять, мислення, уяву, творчі здібності. Але важкість для засвоєння і цікавість учнів до даного розділу є проблематичним. Щоб розв’язувати задачі необхідно засвоїти не лише певну суму знань, а й сам шлях, метод розв’язування.

Для оволодіння розділом “Алгоритмізації і програмування” і участі в олімпіадах з інформатики необхідно:

-                              засвоїти методи складання простих програм на використання базових структур і простих типів даних;

-                              розглянути основні підходи до розроблення та аналізу алгоритмів, вибору оптимальних методів розв’язування задач;

-                              ознайомити з розділами: теорія графів, обчислювальна геометрія, лінійне програмування і т.і.;

-                              навчити використовувати засоби програмування для самостійного розв’язання прикладних задач з математики, інформатики, фізики, для постановки комп’ютерних та обчислювальних експериментів.

З метою пропагування алгоритмізації і підготовки учнів до олімпіад з інформатики на базі Волинського ІППО в лабораторії інформатики працює школа для обдарованих дітей. Заняття проводяться для учнів  8-11 класів за програмою факультативного курсу «Школа олімпійського резерву з програмування. 9-11 класи» (Автор Лисенко Т.І.)[1]

На заняттях розглядаються і опрацьовуються наступні теми:

1.     Поняття мови програмування, їх класифікація. Мова програмування Pascal .

2.     Середовище програмування Delphi. Можливості використання вбудованого редактора.

3.     Структура програми мовою Паскаль. Операції виведення.

4.     Практикум по розв’язуванню задач на структуру слідування.

5.     Оператори управління. Оператор розгалуження та безумовного переходу. Проста і складена умови. Оператор множинного вибору.

6.      Цикли. Організація циклів.

7.      Масиви. Одновимірний масив. Опрацювання елементів одновимірного масиву. Організація пошуку елементів із заданими властивостями в масивах.

8.     Найпростіші алгоритми сортування масивів: метод “бульбашки”, метод прямого вибору.

9.     Двовимірний масив. Опрацювання елементів двовимірного масиву.

10. Рядкові дані. Процедури та функції опрацювання рядкових величин.

11. Текстові файли. Опрацювання текстових файлів.

12. Підпрограми. Процедури в мові PASCAL. Структура процедури. Підпрограми-функцiї. Структура функції. Поняття рекурсії

Також розбираються теми з розділу «Методи складання алгоритмів та їх аналіз»: «довга арифметика», пошукові алгоритми, алгоритми сортування,  обчислювальна геометрія, комбінаторні об’єкти, теорія графів, динамічне програмування, «жадібні» алгоритми.

Під час занять було проаналізовано методи розв’язування задач з відповідних тем та задачі з різного рівня олімпіад. Приклади задач:

1.      В мішку у Діда Мороза лежать цукерки трьох видів: шоколадні, іриски і льодяники. Дід Мороз знає, що якщо вийняти будь-які 100 цукерок з мішка, то серед них обов'язково знайдуться цукерки всіх трьох видів. Яка найбільша кількість цукерок може бути в мішку у Діда Мороза?

Розв’язок

Якщо цукерок одного виду буде 100 і більше, то можна взяти всі сто цукерок одного виду. Отже цукерок одного виду менше сто. Якщо цукерок одного і другого виду буде по 50, то можна взяти всі сто цукерок лише двох видів. Отже цукерок одного виду менше 50, а точніше 49 .

Загальна сума цукерок 148, тому що,

2.     Маємо 8 монет однакової вартості, серед них одна фальшива. Відомо, що фальшива монета трохи легша за інші. Як визначити фальшиву монету двома зважуваннями на терезах з двома шальками без гирок?

Розв’язок

Здійснимо два зважування, взявши у перше зважування по 3 монети на кожну шальку  а, у друге зважування по 1-й монеті на шальку.

Якщо у результаті першого зважування одна із купок легша, тоді порівнюємо усі монети, які лежать у легшій шальці.

Якщо у результаті першого зважування  монети будуть однакові переходимо до наступного зважування.

Якщо у результаті другого зважування виявляємо легшу монету, тоді виводимо.

3.     Дано п'ять мішків, помічених літерами А, Б, В, Г та Д, у яких знаходиться дріб вагою 1г, 2г, 3г, 4г та 5г (у кожному мішку дріб однакової ва­ги). Маємо також терези, що можуть визначати точну вагу покладеного на них предмета. Потріб­но з кожного мішка витягти можливо меншу кількість дробин так, щоб за результатами одно­го зважування визначити, у якому мішку який дріб знаходиться.

Розв’язок

Десяткова система:

1,10,100,1000,1000 дробин.

12345, 21345, ....

Можна використати іншу систему числення, наприклад п’ятіркову.

4.     Переставити значення змінних місцями без використання допоміжної змінної.

Розв’язок

5.     Задати два дійсних числа і замінити їх. Якщо перше менше,  то перше добутком, а друге сумою. Якщо друге менше рівне,  то навпаки, перше сумою, друге добутком.

Розв’язок

Оптимальним був би розв’язок без використання допоміжних змінних

якщо x

6.     Обчислити суму n елементів числового ряду: 1,2,4,7,11,…

Розв’язок

S:=0;

A:=1;

Для і:=1 до n пц

S:=S+A

A:=A+i

Кц.

7.     Обчислити суму n елементів числового ряду: 1,2,5,14,42,132,…

Розв’язок

Це числа Каталана, які обчислюються за формулою

n=9

1

2

5

14

42

132

429

1430

4862

8.     Вивести на екран ряд простих чисел на проміжку від 2 до N використовуючи решето Ератосфена.

Розв’язок

9.     Виконати операції з «довгими числами» (кількість цифр до 1000):

-                              зчитати «довге число» з текстового файлу, як послідовність цифр в масив;

-                              додати два «довгих числа» однакової довжини (однакова кількість цифр);

-                              додати два «довгих числа»  різної довжини;

-                              помножити «довге число» на одноцифрове число;

-                              перемножити два «довгих числа» одне на одне.

Такого типу задачі:

-                              сприяють розвитку і визначенню рівня розвитку логічного мислення в учнів; дозволяють визначити знання про основне поняття математики – число, а також про системи числення;

-                              визначають вміння записувати базові структури алгоритмів: слідування, розгалуження, цикл; визначають, чи учні знають певні задані числові ряди та різні способи їх подання;

-                              визначають рівень програмування учня, тобто вміння записувати програмний код розв’язку за описаним алгоритмом;

-                              дозволяють виявити вміння учнів підбирати і використовувати структуровані типи даних при розв’язуванні задач.

         На заняттях учні проявили високий інтерес до алгоритмізації при складання алгоритмів, доборі методів розв’язування, реалізації, тестуванні і налагодженні  програм. Є бажання і потреба в учнів для підвищення рівня розвитку продовжити роботу в школі в наступному навчальному році. Але для більш продуктивної роботи необхідно добирати і урізноманітнювати методи та  форми  роботи. Наприклад, проводити рейтингові змагання серед учнів, поєднувати навчання з відпочинком.

Для формування алгоритмічного мислення і успішної участі в олімпіадах з інформатики потрібно не тільки володіти мовою програмування, але і вміти придумувати і реалізовувати алгоритми розв’язку задач, які лежать на стику математики і програмування.

Література

1.       Інформатика. Програми для загальносвітніх навчальних закладів. – Запоріжжя: Прем'єр, 2003.

2.        Караванова Т.П. Основи алгоритмізації та програмування: 777 задач з рекомендаціями та прикладами: Навч. посіб. Доп. та випр. – К.: Генеза, 2006. – 288 с.: іл.

3.        Караванова Т.П. Методи побудови алгоритмів та їх аналіз: необчислювальні алгоритми: Навч. посіб. – К.: Генеза, 2006. – 224 с.: іл.

4.        Караванова Т.П. Методи побудови алгоритмів та їх аналіз: обчислювальні алгоритми: Навч. посіб. – К.: Генеза, 2008. – 334 с.: іл.