Олімпіадне програмування

Що ж таке нестандартна задача? Матеріал підготовлено до обласного семінару вчителів інформатики

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

Дата проведення: 13.05.2015р.

Оголошена тема виступу: Розв’язування нестандартних задач і їх тестування з використанням сайту e-olimp-com.ua

Проблемні запитання:

Що таке нестандартна задача?

Що таке нестандартний розв'язок задачі?

До виступу було підготовлено презентацію.

Деякі аспекти визначення нестандартної задачі

Шукаючи визначення нестандартної задачі натрапив на твердження стосовно нестандартних математичних задач (див http://njestandartn-zadach.webnode.com.ua/news/shcho-zh-takje-njestandartna-zadacha-/). Якщо забрати слова про математику визначення цілком згодиться і для інформатики: "Це задача, для якої в курсі математики немає загальних правил і положень, які визначають точну програму їхнього розв’язування." От лише слово "програму" насторожує. Задача з програмування це і є програма. Тавтологія? Не думаю! Розв'язуючи задачі, навчаючись розв'язувати задачі, учень, можна так сказати, програмує свої дії. Програмує свої дії на програмування.

Стосовно сучасного курсу інформатики та стосовно навчання програмування, загальних правил і положень, які визначають розв'язування задач, взагалі дуже мало. По перше, загальні правила і положення дуже і дуже різні: за вимогами різних навчальних програм, різних навчальних посібників, різних авторських реалізацій програм та матеріалів посібників. Враховуючи загальну особливість програмування як високоінтелектуальної людської діяльності, до нестандартних можна, певною мірою, віднести більшість задач з програмування.

Мені також сподобалось інше визначення, що ж таке нестандартна задача: "З одного боку – це задача, для якої немає в курсі математики загальних підходів й алгоритмів її розв’язання. З іншого боку, одна і та ж задача може бути нестандартною для одних учнів і стандартною для інших, якщо учні володіють прийомами розв’язання такої задачі.

Основні підходи до розв'язування нестандартних задач

Існує усього два прийоми розв’язання нестандартних задач:

1. Поділ задачі на простіші підзадачі.

2. Введення додаткових (допоміжних) елементів.

Додаткові елементи це переважно спеціально використані величини, оголошені змінні, виділені та поіменовані частини пам’яті.

Розглянемо приклади задач де зустрічається:

1. Введення додаткової змінної;

2. Використання допоміжного одномірного масиву;

3. Використання допоміжного двовимірного масиву.

Задача 1. Вивести на екран більше з трьох чисел (a,b,c).

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

Спосіб перший. Алгоритм можна будувати як ланцюжок розгалужень:

Якщо a>b то, якщо a>c вивести a …. і так далі. Загальна конструкція буде досить складною.

Спосіб другий. Використати логічне множення, об'єднати умови оператором "і".

Якщо a>b і a>c вивести a. Якщо b>a і b>c вивести b. .... Вже набагато простіше.

Спосіб третій. Використаємо додаткову змінну d.

Якщо a>b то d:=a інакше d:=b. Якщо c>d то d:=c. Вивести d. Все.

Як додаткову можна використати і уже оголошену змінну,

Якщо b>a то a:=b. Якщо c>a то a:=c. Вивести a. Все.

Задача 2. Злітна смуга аеродрому. (Приклад використання допоміжного одномірного масиву.)

Злітна смуга аеродрому має цілочисельну довжину. Лтаки поробігають її від посадки до злету щоразу в інших місцях, від чого смуга нерівномірно зношується. Відомо пари цілих чисел, що вказують початок та кінець ділянки для приземлення-злету кожного літака. Визначити скільки разів літаки використали для злету-посадки найбільш зношену ділянку аеродрому.

Ідея розв'язання. Оскільки всі значення довжин цілочисельні, то можна використати допоміжний масив обсяг якого рівний довжині злітної смуги. Спочатку масив заповнюється нулями. Для кожного використання злітної смуги літаком значення комірок масиву у діапазоні від "точки" приземлення до "точки" злету збільшується на одиницю. Залишається знайти найбільше число, що зустрічається у допоміжному масиві. Це і є відповідь.

Задача 3. На шаховій дошці N×N у клітинці (x₁, y₁) стоїть голодний шаховий кінь. Він хоче потрапити у клітинку (x₂, y₂), де росте смачна шахова трава. Яку найменшу кількість ходів він повинен для цього зробити? Задача 997 з сайту e-olymp https://www.e-olymp.com/uk/problems/997 (Приклад використання допоміжного двовимірного масиву.)

Вхідні дані: Вхідний файл містить п'ять чисел: N, x1, y1, x2, y2 (5 ≤ N ≤ 20, 1 ≤ x1, y1, x2, y2 ≤ N). Ліва верхня клітинка дошки має координати (1, 1), права нижня - (N, N).

Вихідні дані: Вивести єдине число K - найменшу необхідну кількість ходів коня.

Написання програми мовою C#

Спочатку організуємо зчитування вхідних значень та перевіримо чи воно вірно виконується

using System;

class ShK

{

static void Main()

{

byte N = Convert.ToByte(Console.ReadLine());

string [] begin = Console.ReadLine().Split( );

string [] end = Console.ReadLine().Split( );

byte x1 = Convert.ToByte(begin[0]);

byte y1 = Convert.ToByte(begin[1]);

byte x2 = Convert.ToByte(end[0]);

byte y2 = Convert.ToByte(end[1]);

byte K = 0; // кількість ходів

// Console.WriteLine(x1 +" "+ y1 +" "+ x2 +" "+ y2);

Console.WriteLine(K);

Console.ReadKey(true);

}

}

Доповнимо програму оголошенням допоміжного масиву та заповненням його нулями. У початкову комірку запишемо "1" а у кінцеву "111" (у авторській реалізації сюди ставиться "-1", але використаний нами тип даних не допускає від'ємних значень. Також пересвідчимось, чи вірно значення записується у масив організувавши виведення масиву на екран.

using System;

class ShK

{

static void Main()

{

byte N = Convert.ToByte(Console.ReadLine());

string [] begin = Console.ReadLine().Split( );

string [] end = Console.ReadLine().Split( );

byte x1 = Convert.ToByte(begin[0]);

byte y1 = Convert.ToByte(begin[1]);

byte x2 = Convert.ToByte(end[0]);

byte y2 = Convert.ToByte(end[1]);

byte K = 0; // кількість ходів

byte [,] board = new byte[N,N];

byte i, j;

for (i = 0; i<N; i++)

{

for (j = 0; j<N; j++)

{

board[i,j] = 0;

}

}

board[x1,y1] = 1;

board[x2,y2] = 111;

for (i = 0; i<N; i++)

{

Console.WriteLine();

for (j = 0; j<N; j++)

{

Console.Write(board[i,j]+" ");

}

}

Console.WriteLine(K);

// Console.WriteLine(N, x1, y1,x2,y2);

Console.ReadKey(true);

}

}

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

for (i = 0; i<N; i++)

{

for (j = 0; j<N; j++)

{

if((board[i+2,j+3]==K)||(board[i+3,j+2]==K)||(board[i-2,j-3]==K)||(board[i-3,j-2]==K)||(board[i+2,j-3]==K)||(board[i+3,j-2]==K)||(board[i-2,j+3]==K)||(board[i-3,j+2]==K))

{

board[i,j]=K;

}

}

}

K++;

Та, нажаль, виникає інша перепона. Для перевірки умови програма звертається до комірок, що виходять за межі масиву. Вирішивши це можна оголосивши масив дещо більшого обсягу та "зсунувши" від початку комірки, на яких вивчатимуться можливі ходи шахового коня.

Ось уся програма у якій, для наочності все ще виводяться на екран елементи допоміжного масиву:

using System;

class ShK

{

static void Main()

{

byte N = Convert.ToByte(Console.ReadLine()); // зчитується розмір шахової дошки

string [] begin = Console.ReadLine().Split( ); // зчитуються текстові значення початкових координат коня

string [] end = Console.ReadLine().Split( );// зчитуються текстові значення кінцевих координат коня

byte x1 = Convert.ToByte(begin[0]); // текстові значення початкових координат коня перетворюються в цілочисельні

byte y1 = Convert.ToByte(begin[1]); // текстові значення початкових координат коня перетворюються в цілочисельні

byte x2 = Convert.ToByte(end[0]); // текстові значення кінцевих координат коня перетворюються в цілочисельні

byte y2 = Convert.ToByte(end[1]); // текстові значення кінцевих координат коня перетворюються в цілочисельні

byte K = 1; // встановлюється початкове значення кількості ходів

byte [,] board = new byte[N+10,N+10]; // оголошується допоміжний масив

byte i, j; // оголошуються параметри (лічильники) наступних циклів

for (i = 0; i<N+10; i++) // цикл, що пробігає рядочки

{

for (j = 0; j<N+10; j++) // цикл, що пробігає рядочки

{

board[i,j] = 0; // масив заповнюється нулями

}

}

board[x1+2,y1+2] = 1; // почткове положення коня (уся дошка зсовується на 2 праворуч)

board[x2+2,y2+2] = 111; // кінцеве положення коня (уся дошка зсовується на 2 донизу)

while(K<10)

{

for (i = 1+2; i<N+3; i++)

{

for (j = 1+2; j<N+3; j++)

{

if((board[i+1,j+2]==K)|(board[i+2,j+1]==K)|(board[i+2,j-1]==K)|(board[i-1,j+2]==K)|(board[i-1,j-2]==K)|(board[i-2,j-1]==K)|(board[i+1,j-2]==K)|(board[i-2,j+1]==K))

{

if (board[i,j]==111) {break;} else {board[i,j]=K; board[i,j]++;} // при знаходжені кінцевої клітинки цикл преривається

}

}

if (board[i,j]==111) {break;}; // при знаходжені кінцевої клітинки цикл преривається

}

//if (board[i,j]==111) {break; };

K++;

}

for (i = 0; i<N+5; i++)

{

Console.WriteLine();

for (j = 0; j<N+5; j++)

{

Console.Write(board[i,j]+" ");

}

}

Console.WriteLine();

Console.WriteLine();

Console.WriteLine(K);

// Console.WriteLine(N, x1, y1,x2,y2);

Console.ReadKey(true);

}

}