Як відомо, сьогодні олімпіади з информатики побудовані таким чином:
* шкільний тур. При цьому рекомендуються деякі задачі (до того ж, здебільшого
математичні задачі).
* районний тур, в якому приймають участь члени команд, які стали переможниками
шкільних турів.
* міський тур (2 етапи)
Потрапити на район, місто, уникнувши шкільну дистанцію, тепер неможливо,
оскільки все розподілено по предметах.
Олімпіада з інформатики-це виявлення талантів з курсу програмування.
В основу програмування включені такі дуже важливі компоненти, як математика,
англійська мова та мова програмування. Тому бажано, щоб олімпіади з математики
і інформатики були незалежні одна від другої, не проводились в один день.
Приклад 1:
Компілятор Turbo Pascal має опцію "Complete boolean eval".
Якщо ця опція включена, програма буде обчислювати всі логічні вирази до
кінця, навіть якщо результат можна отримати заздалегідь. Припустимо, при
i=0
в операторі if (i<0)and(j=6) then...else після обчислення i<0
одразу
стає зрозуміло, що значення всього виразу - false, і виконуватись
повинна частина else. Вищевказана опція визначає, чи буде обчислюватись
вираз j=6.
Правильне використання цієї настройки має велике значення при програмуванні.
Розглянемо таку ситуацію: ми маємо матрицю m x n і для обробки
її елементів треба реалізувати порівняння двох сусідніх (по вертикалі або
горизонталі) елементів.
if (a[n,m]=a[n+1,m]) then .....
Але що як у цей момент n було максимальним, і праворуч (або нижче) немає сусіднього елементу? Треба перевірять:
if (n<MaxN) then
begin
if (a[n,m]=a[n+1,m]) then .....
...........
end;
Але відключивши опцію "Complete boolean eval" та знаючи, що порівняння елементів не буде виконуватись, якщо перша умова не істинна, можна все написати набагато простіше:
if (n<MaxN)and(a[n,m]=a[n+1,m])
then .......
Приклад 2:
Практика програмування доводить, що в кожну програму, яка розробляється,
обов'язково вкрадеться помилка. Про це є навіть приказка: "Якщо ваша програма
відкомпілювалась і почала працювати з першого разу без помилок, скажіть
про це системному програмісту, і він виправить помилки у компіляторі."
І тут доречно підкреслити на прикладі важливість відлагоджувача-інструмента,
котрий дозволяє слідкувати за логікою роботи кожного рядка програми, фіксувати
де вона "спотикається", а потім виправляти помилки.
Почнемо з прикладу обчислення факторіалу, який може бути компонентою
деяких задач. Нижче приведена програма на мові Сі.
#include <stdio.h>
int factorial(int n) {
/* Loop variable Змінна
циклу */
int i;
int result;
/* Init result variable
Ініціалізація змінної результату */
result = n;
/* Multiply numbers
1 to n Множення чисел від 1 до n*/
for ( i = 0; i <
n; i++ )
result *= i;
return result;
}
void main(void) {
int n;
/* Get value Отримання
значення */
printf("What value?");
scanf("%d", &n);
/* Print factorial Друк
факторіалу */
printf("%d", factorial(n));
}
Виконайте програму декілька разів для різних чисел. Ви побачите, що
незалежно від того, яке значення ви вводите, в результаті ви отримуєте
0. Це неправильно!
Тепер на допомогу приходить відлагоджувач. При його допомозі можна
по кроках відслідкувати роботу функції factorial().
Встановіть контрольну точку на початку функції factorial().
Далі, запустіть програму и введіть число. Після цього виконання зупиниться
на контрольній точці. Тепер необхідно встановити слідкування за змінною
result, оскільки як раз в цій змінній знаходиться результат функції. Виведіть
цю змінну у вікні слідкування. Продовжуйте виконувати функцію по шагах,
слідкуючи за значенням змінної. Скоро ви побачите, що після виконання наступної
строки значення result стане 0. Це строка
result *= i;
Найгірше всього те, що значення змінної після цього ніколи не змінюється. Ви побачите це за допомогою вікна слідкування. Оскільки змінна result отримала невірне значення в циклі, то помилка як раз там. А оскільки там тільки один рядок, множення на i, це значить, що i змінюється якось невірно. Якщо ви подивитесь на початок циклу for, то побачите, що i змінюється від 0 до n.
for ( i = 0; i< n; i++ )
А це означає, що при першому проході циклу трапляється множення на нуль.
Отже, ми знайшли проблему!
Помилка в тому, що змінна i повинна змінюватися не від 0 до n, а від
1 до n. Змініть рядок
for ( i = 0; i< n; i++ )
на
for ( i = 1; i< n; i++ )
Тепер необхідно виконати програму ще раз. Спробуйте знову ввести різні
значення. Тепер одержане значення більше не дорівнює нулю, тобто проблема
ліквідована.
Та не тут то було! Значення факториалу чомусь неправдоподібно велике.
Перевіримо ще раз. Запустіть відлагодження та встановіть слідкування за
змінною result. Ви побачите, що при першому проходженні циклу result стає
рівним 5, а потім 10, 20 і т. п. А чому result починається зі значення
5? Адже нам потрібно починати зі значення 1. Продивившись текст програми,
ви побачите, що result спочатку ініціюється значенням n.
result = n;
Насправді нам потрібно, щоб змінна result ініціювалася значенням 1.
Виправте цю помилку. Замініть
result = n;
на
result = 1;
Знову спробуйте виконати програму для різних значень. Тепер програма
виконується вірно для будь-яких чисел!
2. Далі, кожен учасник повинен мати добре уявлення про класичні алгоритми
-
* сортування,
* бінарний пошук,
* перебір,
* генератор перестановок,
* задача комівояжера і т. д.
Робота ціх алгоритмів добре описана у другій частині посібника з інформатики
(А.
Р. Есаян, В. И. Ефимов и др. Информатика.-М.: Просвещение, 1991.),
а задачі наведені в Частині 3 "Практичних робіт" за редакцією Н. В.
Морзе, Київ 1998.
Учень повинен також навчитися правильно використовувати ці алгоритми
в програмах, тобто виділяти їх як підзадачу в задачі, якщо це необхідно
для її виконання, якщо це повинно бути одним з допоміжних алгоритмів. Оскільки
реалізація стандартних алгоритмів буде знайома учню, це сбереже час для
більш глибокої обробки нестандартної логіки задачі. Звичайно, слід показати
декілька класичних задач та їх реалізацію на мові програмування, яка використовуєьться,
і, накінець, запропонувати учню розв'язати кілька подібних. Напр.
* отримати всі перестановки
* реалізувати методи динамічного програмування
* програмно реалізувати невідому кількість вкладених один в одного
циклів
* включити в програму теорію графів
* реалізація теорії ігр
3. Досить корисно попрацювати з учнем над задачами, які були запропоновані на олімпіадах минулих років. Якщо є можливість, можна представити розв'язок олімпіадних задач - або авторську реалізацію, або реалізацію учасників олімпіади. Далі, запропонувати деякі для розв'язку самостійно.
4. Останнім часом з'явилася тенденція появлення математичних задач на олімпіадах з інформатики. На це слід звернути увагу, оскільки можна спрогнозувати, що на олімпіаді буде геометрична задача з графічним виведенням результату на екрані (можлива анімація). Тому, згідно прогнозу, можна приділяти багато уваги подібній темі. Зрозуміло, якщо типові задачі будуть змінюватися, необхідно своєчасно помітити зміну та реагувати належним чином. В будь якому випадку, задачі мають тенденцію повторюватися!