Розбір задач за матеріалами http://www.vvman.lutsk.ua/file/k60.pdf
(Герасимчук Н. О. Розв'язання олімпіадних задач з програмування (навчальний посібник для слухачів відділення комп'ютерних наук МАН)
РОЗДІЛ 2. РОЗБІР ЗАДАЧ.
2.1. Масиви
Задача 1. Слоненята.
Ця задача взята з розділу “Задачі для початківців” Всеукраїнського Центру олімпіад
школярів в інтернеті, доступна в мережі за адресою:
http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=99
Сторінка для здавання на автоматичну перевірку задачі:
http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=823&task=slon
Задача Slon. Петрик П'яточкін вишикував у рядок слоненят та рахує їх по
кожному кольору окремо. Всього буває 8 кольорів слоненят. У рядок вишикувались
N (10<N<999) слоненят. Скільки слоненят кожного кольору стоїть перед
Петриком? Бажано їх порахувати пройшовши всього один раз перед строєм.
Технічні умови. Програма зчитує з клавіатури ціле число N - кількість
слоненят, потім, через пропуск — N чисел від 1 до 8, якими ми пронумерували
кожен колір в тій послідовності, в якій вони потрапляли на очі Петрику від початку
рядка. Програма виводить на екран в один рядок через пропуски пари цілих чисел,
де перше число пари - колір, а друге - кількість слоненят такого кольору.
Приклад
Введення Виведення
12 1 1 2 3 3 1 5 6 8 7 6 5 1 3 2 1 3 2 4 0 5 2 6 2 7 1 8 1
Аналіз задачі
Суть задачі — порахувати слоненят, при чому, слоненята можуть бути різних
кольорів. Всього 8 можливих кольорів. Це означає, що у нас буде 8 груп слоненят, а
отже, на підрахунок яких нам потрібно буде відвести 8 лічильників. Це може бути 8
цілочисельних змінних, при чому, виходячи з умови задачі, бачимо, що кожен з
лічильників не може перевищувати 999, бо загальна кількість слоненят N лежить в
межах (10<N<999). Замість 8 змінних, легше було б використати таку структуру, як
масив, що складатиметься з 8 елементів, кожен з яких може набувати цілочисельного
значення.
В умові перед нами ставиться задача, здійснити підрахунок пройшовши всього
один раз перед строєм. Це означає, що почергово проходячи перед кожним слоненям
ми повинні отримати колір цього слоненя й одразу збільшувати відповідний
лічильник. Отже, за один цикл ми повинні виконати всі підрахунки.
Тепер розберемося з вхідними та вихідними даними.
Перше число, яке ми отримуємо на вхід програми це N - кількість слоненят,
далі, ідуть записані через пробіл кольори кожного з N слоненят. Отже, програма
повинна спершу прийняти число N, а потім N чисел, які означають кольори слоненят.
В якості вихідних даних, програма повинна в один рядок вивести пари чисел,
де перше число символізує номер кольору, а друге число — кількість слоненят цього
кольору — і так для всіх восьми допустимих кольорів.
Складемо блок-схему алгоритму розв'язання задачі:
Надалі в блок-схемах в циклах ДЛЯ (for) у шестикутнику замість тексту “для і від 1 до N” будемо користуватися
записов i=1, N, що означає точно те саме, тобто, те, що змінна і почергово з кроком 1 починаючи з першого
значення 1 і закінчуючи останнім N змінюється.
Програмування розв'язку задачі
program Slon;
var m : array[1..8] of integer;
i, n, x : integer;
begin
read(n);
for i:=1 to 8 do m[i]:=0;
for i:=1 to n do
Begin
read(x);
inc(m[x]);
End;
for i:=1 to 8 do write(i, ' ', m[i], ' ');
end.
Де m — масив, в якому в i-му елементі зберігається інформація про кількість
слоненят, які мають і-ий колір, тобто, якщо в 3-му елементі масива після завершення
Задача 2. Зсунь елементи
Ця задача (922) з “E-Oplimp”, доступна в мережі за адресою:
http://www.e-olimp.com.ua/ua/problems/922
Задано одновимірний масив А цілих чисел довжини h. Зсунути елементи
масиву циклічно праворуч на 1 крок.
Технічні умови
Вхідні дані. У першому рядку задано натуральне число h - кількість елементів
масиву (h≤100). У другому рядку задано самі елементи масиву, значення кожного з
яких за модулем не перевищує 100.
Вихідні дані. В єдиному рядку вивести через проміжок h чисел: нові значення
елементів масиву.
Приклад
Введення Виведення
4
1 2 3 4
4 1 2 3
Аналіз задачі
Суть задачі є проста і зрозуміла. Виходимо з того, що є масив, в якому
потрібно виконати зсув (ця процедура нерідко може зустрічатися як складова
частина складних алгоритмів опрацювання масивів). Зсув вправо на 1 крок означає,
що кожен елемент в масиві змінює своє положення на одну комірку вправо -
“підсовується вправо”; лише для останнього (самого правого в масиві) елемента —
нікуди рухатися, отже він “міняється місцями” з першим.
- 34 -Програмування розв'язку задачі
Бачимо, що спочатку у вхідних
даних подається кількість елементів
масиву, а потім ідуть самі елементи цього
масиву. Отже, зчитати масив не складе
труднощів. Починаємо зсув з того, що в
тимчасову змінну last збережемо
значення останнього елемента масиву.
Далі, циклічно виконуємо безпосередньо,
сам зсув — з елемента під номером h до
елемента під номером 2 — в зворотньому
порядку — виконуємо переприсвоєння
значення (i-1)-го елемента i-тому.
Після цього, присвоюємо раніше
збережене значення в змінній last
першому елементу масива.
Під час виведення результуючого масиву, ми не повинні виводити ніяких
символів, тобто, якщо ми напишемо код виведення елементів масиву наступним
чином:
for i:=1 to h do
write(m[i],' ');
то в результаті, на екран буде виведено зайвий символ — пробіл, після останнього
елемента масиву. Таким чином, нам потрібно проконтролювати цю ситуацію — як
тільки ми будемо виводити останній елемент — потрібно після нього нічого не
виводити — лише символ закінчення рядка, який вставляється при використанні
процедури writeln. Отже, перепишемо код виведення масиву, матимемо:
for i:=1 to h do
if i<>h then write(m[i],' ')
else writeln(m[i]);
Розв'язок матиме вигляд:
- 35 -program zsuv;
var h, i, last : integer;
m : array[1..100] of integer;
begin
readln(h);
for i:=1 to h do read(m[i]);
last:=m[h];
for i:=h downto 2 do
m[i]:=m[i-1];
m[1]:=last;
for i:=1 to h do
if i<>h then write(m[i],' ')
else writeln(m[i]);
end.
Задача 3. Вінні
Ця задача взята з розділу “Задачі для початківців” Всеукраїнського Центру олімпіад
школярів в інтернеті, доступна в мережі за адресою:
http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=100
Сторінка для здавання на автоматичну перевірку задачі:
http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=823&task=vinni
Задача Vinni. Вінні Пух любить складати віршики говорячи речення задом
наперед. Якось йому попалось довге складне речення і він забув свій віршик,
пробуючи його виговорити. Складіть програму, яка б допомагала ведмедику легко
складати такі віршики. Зауваження: віршик може складатись як із 1 слова, так і з
декількох, розділених пропусками.
Технічні умови. Програма зчитує з клавіатури стрічку-віршик. В кінці віршика
ніколи не ставиться крапка. Довжина віршика менша за 255 символів.. Програма
виводить на екран стрічку, яку отримано внаслідок повороту.
Приклад.
Введення Виведення
роза азор
Все медведи любят мед дем тябюл идевдем есВ
- 36 -Аналіз задачі
Згідно з умовою задачі, нам потрібно зчитати рядок символів, а потім —
вивести на екран цей самий рядок символів, лише в оберненому порядку.
Для розв'язання задачі будемо використовувати масив символів. Так як нам
сказано, що стрічка повинна бути меншою за 255 символів, то відповідно і
розмірність масиву повинна бути 255:
var m : array[1..255] of char;
Здійснювати читання стрічки будемо допоки не досягнемо кінця стрічки, тобто
допоки виконується умова NOT EOLN. При читанні посимвольно, ми повинні мати
змінну-вказівник(i), яка вказуватиме, в яку позицію в масиві потрібно вставити
щойно зчитаний символ.
По завершенню читання (досягнення кінця стрічки) — нам потрібно вивести у
зворотньому порядку всі елементи масиву. Так як і вказує на позицію в масиві, куди
потрібно вставити щойно зчитаний символ, то відповідно, останнім символом буде
(і-1)-ий. Отже, зменшуємо і на одиницю, й починаємо низхідний цикл по і, допоки
і>0. В цьому циклі ми повинні виконувати наступні операції: виводити на екран
елемент масиву під номером i, а після цього — зменшувати значення і на 1.
Програмування розв'язку задачі
var m : array[1..255] of char;
i : byte;
begin
i:=1;
while (NOT EOLN) do
Begin
read(m[i]);
inc(i);
End;
dec(i);
while i>0 do
Begin
write(m[i]);
dec(i);
End;
end.
- 37 -Задачі на самостійне опрацювання
1. http://www.e-olimp.com.ua/ua/problems/494
Голосні
До голосних літер в латинському алфавіті відносяться літери A, E, I, O, U і Y. Інші літери
вважаються приголосними. Напишіть програму, яка підраховує кількість голосних літер в тексті.
Технічні умови. Вхідні дані. У вхідному файлі міститься один рядок тексту, який складається
лише із великих латинських літер та пробілів. Довжина рядка не перевищує 100 символів.
Вихідні дані. У вихідний файл вивести одне ціле число – кількість голосних у вхідному тексті.
2. http://www.e-olimp.com.ua/ua/problems/914
Модуль максимального
Задано одновимірний масив А дійсних чисел, пронумерованих від 1 до h. Визначити
значення модуля максимального елемента масиву.
Технічні умови. Вхідні дані. У першому рядку задано натуральне число h - кількість елементів у
масиві (h ≤ 100). У наступному рядку через пропуск задано h дійсних чисел - самі елементи масиву,
значення яких не перевищують по модулю 100.
Вихідні дані. Єдине число - відповідь до задачі, виведене з точністю 2 знаки після десяткової
крапки.
3. http://www.e-olimp.com.ua/ua/problems/908
Ті, що діляться на 6
Для N цілих чисел визначити суму й кількість додатних чисел, які діляться на 6 без остачі.
Технічні умови. Вхідні дані. У першому рядку задано кількість чисел N (0 < N ≤ 100), у
наступному рядку через пропуск задано самі числа, значення яких по модулю не перевищують
10000.
Вихідні дані. У єдиному рядку виведіть спочатку кількість вказаних чисел і через пропуск їх суму.
4. http://www.e-olimp.com.ua/ua/problems/907
Перший не більший за 2,5
Задано одновимірний масив А дійсних чисел, пронумерованих від 1 до h. Визначити
перший елемент масиву, який не перевищує 2.5.
Технічні умови. Вхідні дані. У першому рядку задано кількість елементів масиву h (0 < h ≤ 100), у
наступному рядку задано h дісних чисел, відокремлених пропуском.
Вихідні дані. Вивести у одному рядку спочатку індекс знайденого першого вказаного елемента
масиву і через пропуск його значення з точністю 2 знаки після десяткової крапки. У випадку
відсутності вказаного елементу в масиві вивести "Not Found" (без лапок).
5. http://www.e-olimp.com.ua/ua/problems/904
- 38 -Збільшити на 2
Задано одновимірний масив А цілих чисел. Збільшити на 2 кожний невід’ємний елемент
масиву.
Технічні умови. Вхідні дані. У першому рядку задано натуральне число h - кількість елементів
масиву (h≤100). У другому рядку через проміжок задано самі елементи масиву, значення кожного з
яких за модулем не перевищує 100.
Вихідні дані. В єдиному рядку вивести через проміжок h чисел: нові значення елементів масиву, у
тому ж порядку, в якому їх було задано.
6. http://www.e-olimp.com.ua/ua/problems/928
Сума найбільшого та найменшого
Задано одновимірний масив A цілих чисел. Визначити суму найменшого та найбільшого
елементів масиву.
Технічні умови. Вхідні дані. У першому рядку задано натуральне число h - кількість елементів
масиву (h≤ 100). У другому рядку через проміжок задано самі елементи масиву, значення кожного з
яких за модулем не перевищує 100.
Вихідні дані. В єдиному рядку вивести одне число - відповідь до задачі.
7. http://www.olymp.vinnica.ua/index_ua.php?lng=ua&cid=188
Sweets.
Маленький хлопчик потрапив до казкової країни і побачив там дорогу, вздовж якої
розкладено мішки з цукерками. На кожному мішку написана кількість цукерок. Хлопчик може
взяти в кожну руку два мішки, що лежать поруч. Яку найбільшу кількість цукерок він може взяти?
Технiчнi умови. Ви вводите з клавіатури кількість мiшкiв N (4<=N<=10000), а потiм N чисел через
пропуск - кількість цукерок у кожному мішку (всі числа непід'ємні і не перевищують 1000000). Ви
виводите на екран єдине шукане число.
2.2. Найбільший спільний дільник та найменше спільне кратне
Необхідні знання з теми
Найбільшим спільним дільником (надалі, використовуватимемо скорочення
НСД) дільник двох чисел є найбільше число, що ділить обидва дані числа без
залишку12
.
Наприклад, для чисел 25 та 15 НСД буде рівний 5.
Для того, щоб обчислити НСД часто користуються методом розкладу числа на
12 Розгядатимемо НСД саме додатніх чисел.
- 39 -прості множники. Наприклад, знайдемо НСД 792, 360 . Для цього нам потрібно
числа 792 та 360 подати у вигляді: 360 = 2
3
⋅ 3
2
⋅ 5
1
792 = 2
3
⋅ 3
2
⋅ 5
0
⋅ 111
.
Тепер, НСД отримуємо як добуток усіх спільних для обох чисел простих
множників: 2
3
⋅ 3
2 = 72 .
Варто відмітити наступні властивості НСД:
• Від перестановки чисел НСД не змінюється: НСД a , b = НСД b , a .
• НСД лежить в межах: 1 ≤ НСД a , b ≤ mina , b .
• Для того, щоб знайти НСД трьох чисел a ,b , c необхідно знайти
спершу НСД a , b , а потім використати знайдений результат й знайти
шукане НСД трьох чисел як НСД НСД a , b , c . Це ж правило
можна поширити для довільної кількості вхідних даних.
Для обчислення НСД існує дуже зручний метод, що потребує значно менше
обчислень. Це алгоритм Евкліда.
Алгоритм Евкліда заснований на тому, що НСД двох чисел не змінюється,
якщо від більшого числа відняти менше. Наприклад, 21 є НСД чисел 252 та 105:
252 = 21 ⋅ 12
105 = 21 ⋅ 5
. Оскільки 252 − 105 = 147 , НСД 147, 105 = 21 .
Оскільки більше з двох чисел постійно зменшується, повторне виконання
цього кроку дає все менші числа, поки одне з них не дорівнюватиме нулю. Коли одне
з чисел дорівнюватиме нулю, інше, відмінне від нуля і є НСД. Так виглядатиме
процес пошуку НСД 20, 12 :
- 40 -Схема виконання алгоритму пошуку НСД двох чисел
На кроці 4 ми дійшли до того, що b=0 , а отже, НСД 20, 12 = a = 4 .
Для того, щоб запрограмувати процес знаходження НСД за допомогою
алгоритму Евкліда, зручно ввести рекурсивне означення НСД, яке ґрунтується на
покращенні методу за рахунок обчислення остач від ділення на кожному кроці.
Тобто, для обчислення НСД 40, 4 ми б не виконували дії:
- 41 -
40 4
40−4=36 4
36−4=32 4
32−4=28 4
... ...А виконали б:
І одразу отримали результат: НСД 40, 4 = 4 .
Отже, рекурсивне означення НСД [7] :
Хоча, взагалі кажучи, користуючись властивістю НСД (від перестановки чисел
НСД не змінюється) НСД можна означити наступним чином:
що значно спрощує програмну реалізацію функції НСД.
function NSD(a, b : integer) : integer;
begin
if a=0 then NSD:=b
else NSD:=NSD(b mod a, a);
end;
Найменше спільне кратне (надалі - НСК ) двох чисел НСК a , b є
найменшим натуральним числом, яке ділиться без залишку на обидва числа a та
b .
Наприклад, для чисел 25 та 15 НСК буде рівне 75.
Для того, щоб обчислити НСК, як і для обчислення НСД користуються
методом розкладу числа на прості множники. Наприклад, знайдемо НСК 792, 360
. Для цього нам потрібно числа 792 та 360 подати у вигляді (як ми це робили вище):
360 = 2
3
⋅ 3
2
⋅ 5
1
792 = 2
3
⋅ 3
2
⋅ 5
0
⋅ 111
.
Тепер, НСК отримуємо як добуток простих множників обох чисел в
найбільшій степені: 2
3
⋅ 3
2
⋅ 5
1
⋅ 111 = 3960 .
Відмітимо, що:
• Для НСК також характерним є те, що від перестановки чисел НСК не
змінюється: НСК a , b = НСК b , a .
• Для того, щоб знайти НСК трьох чисел a ,b , c необхідно знайти
- 42 -
НСД a ,b={
a , якщоb=0,
b , якщоa=0,
НСД amod b ,b, якщоa≥b ,
НСД a , bmod a, якщоab.
НСД a ,b={
b , якщоa=0,
НСД bmod a ,a, якщоa≠0.
40 4
40 mod 4=0 4спершу НСК a , b , а потім використати знайдений результат й знайти
шукане НСК як НСК НСК a , b , c . Це ж правило можна поширити
для довільної кількості вхідних даних.
• НСК легко знаходиться з наступної формули:
Так як для прикладу НСД та НСК двох чисел ми використовували ті ж самі числа,
перевіримо отриманий результат.
Бачимо, що формула “працює”, а отже ми можемо сміливо нею користуватися.
Маючи описану функцію NSD, знаходження НСК можемо описати:
function NSK(a, b : integer) : integer;
begin
NSK:=a*b div NSD(a,b);
end;
Задача 1. НСД
Ця задача взята з “E-Olimp”, доступна в мережі за адресою:
http://www.e-olimp.com.ua/ua/problems/137
Знайти НСД (найбільший спільний дільник) N чисел.
Технічні умови
Вхід: У першому рядку кількість чисел N (1<N<101).
У другому - через пропуск N натуральних чисел, що не перевищують 30000.
Вихід: НСД цих чисел.
Приклад.
Введення Виведення
2
15 25
5
Аналіз задачі
Для розв'язання задачі потрібно використати правило:
- 43 -
НСД a , b⋅НСK a ,b=a⋅b ⇒ НСK a ,b=
a⋅b
НСД a ,b
НСД 360, 792=72,
НСК 360, 792=3960,
72 ⋅ 3960 = 360 ⋅ 792.• Для того, щоб знайти НСД трьох чисел a ,b , c необхідно знайти
спершу НСД a , b , а потім використати знайдений результат й знайти
шукане НСД трьох чисел як НСД НСД a , b , c . Це ж правило
можна поширити для довільної кількості вхідних даних.
Зрозуміло, що для розв'язання поставленої задачі потрібно мати описану
процедуру знаходження НСД двох чисел. І надалі, наприклад, для чотирьох чисел a,
b, c, d їх НСД шукатимемо наступним чином:
НСД НСД НСД a , b , c, d
Відповідно, за цим же принципом шукатимемо НСД більшої кількості чисел.
Отже, спочатку, нам потрібно зчитати 2 числа й знайти їх НСД. Це значення
зберегти в тимчасову змінну (z), і надалі, поступово читаючи нові числа —
переприсвоювати значення z, надаючи їй значення, що обчислюється, як НСД нового
числа і поточного значення z. Для цього достатньо наявності циклу від 3 до n, при
чому, якщо n=2 (тобто на вхід подається лише 2 числа), то тіло циклу не виконається
жодного разу, а одразу виведуться результати.
Програмування розв'язку задачі
var n, x, z, y, i : integer;
function NSD(a, b : integer) : integer;
begin
if a=0 then NSD:=b
else NSD:=NSD(b mod a, a);
end;
begin
readln(n);
read(x,y);
z:=nsd(x,y);
for i:=3 to n do
Begin
read(x);
z:=nsd(z,x);
End;
writeln(z);
end.
- 44 -Задача 2. НСК
Ця задача взята з “E-Olimp”, доступна в мережі за адресою:
http://www.e-olimp.com.ua/ua/problems/135
Знайти найменше спільне кратне (НСК) N натуральних чисел.
Технічні умови
Вхід: У першому рядку кількість чисел N (1 < N < 21).
У другому - через пропуск N натуральних чисел, що не перевищують 100.
Вихід: НСК цих чисел.
Приклад
Введення Виведення
2
2 3
6
Аналіз задачі
Розв'язання задачі, будемо здійснювати по аналогії з попередньою задачею,
тобто, використовуючи узагальнену формулу для знаходження НСК кількох чисел.
При чому, для знаходження НСК будемо користуватися формулою
З попередньої задачі, функція знаходження значення НСД в нас є. Єдина
проблема, з якою можемо зустрітися при розв'язанні задачі — це великі числа —
значення НСК. Отже, використаємо тип даних int64.
Програмування розв'язку задачі
var n, i, a, b : integer;
rez : int64;
function NSD(a, b : int64) : int64;
begin
if a=0 then NSD:=b
else NSD:=NSD(b mod a, a);
end;
function NSK(a, b : int64) : int64;
- 45 -
НСK a ,b=
a⋅b
НСД a , bbegin
NSK:=a*b div NSD(a,b);
end;
Begin
readln(n);
read(a,b);
rez:=nsk(a,b);
for i:=1 to n-2 do
Begin
read(a);
rez:=NSK(rez,a);
End;
writeln(rez);
End.
Задачі на самостійне опрацювання
1. http://www.e-olimp.com.ua/ua/problems/136
Відрізок
Задано відрізок, кінці якого мають цілочисельні координати.
Підрахувати кількість точок відрізку, які мають цілочисельні
координати.
Технічні умови. Вхідні дані. 4 числа — координати X1, Y1, X2, Y2
кінців відрізку. Всі вхідні дані не перевищують за модулем 2⋅109
.
Вихідні дані. Єдине число - шукана кількість точок.
2. http://www.e-olimp.com.ua/ua/problems/571
Найбільший спільний дільник
Задано N натуральних чисел. Напишіть програму, яка обчислює найбільший спільний
дільник цих чисел.
Технічні умови. Вхідні дані. У першому рядку вхідного файлу знаходиться натуральне число N
(N<=1000) - кількість чисел. Далі йде N натуральних чисел, кожне з яких не перевищує 2⋅109
.
Вихідні дані. У вихідний файл виведіть єдине число - найбільший спільний дільник заданих чисел.
3. http://www.e-olimp.com.ua/ua/problems/752
Цілі точки
- 46 -Многокутник (не обов'язково опуклий) на площині задано координатами своїх вершин.
Потрібно порахувати кількість точок з цілочисельними координатами, які лежать всередині нього
(але не на його границі).
Технічні умови. Вхідні дані. У першому рядку міститься N (3 ≤ N ≤ 1000) – число вершин
многокутника. У наступних N рядках йдуть координати (Xi, Yi) вершин многокутника у порядку
обходу за годинниковою стрілкою. Xi і Yi - цілі числа, які по модулю не перевищують 1000000.
Вихідні дані. У вихідний файл вивести одне число – шукану кількість точок.
2.3. Сортування
Необхідні знання з теми
Знання й розуміння методів сортування зазвичай є необхідним при
розв'язуванні олімпіадних задач.
На сьогодні, існують багато різних типів сортування, з-поміж них
найвідомішими є: “сортування бульбашкою”, “сортування вставками”, “сортування
вибором”, “швидке сортування”, “метод Шелла” та інші.
Сортування бульбашкою
Сортування бульбашкою — один із найпростіших методів сортування. Цей
метод сортування отримав свою назву через те, що якщо спостерігати за процесом
сортування, то можна помітити, що “найлегші” елементи ніби поступово спливають
вверх, як бульбашки.
Як видно, ідея методу полягає у тому, щоб у декілька кроків пробігати з
самого низу масиву до верху, й переглядати пари сусідніх елементів. У випадку, коли
в парі елементів перший елемент більший за другий — міняємо місцями ці
елементи. Повторювати перегляд масиву будемо до тих пір, поки масив не буде
повністю відсортований. 13
13 На ілюстрації сортування пунктирними лініями відділяються етапи входження в цикл while — див. далі
- 47 -При написанні алгоритму сортування, варто врахувати, що ми можемо значно
зменшити кількість “непотрібних” переглядів масиву у випадку, наприклад, коли
масив є повністю відсортований, або відсортований на певному етапі сортування.
Для того, щоб відслідкувати цей момент потрібно стежити за тим, чи на
попередньому кроці сортування ми переставляли сусідні елементи місцями. В тому
випадку, якщо перестановок не відбулося — це означатиме що їх уже й не потрібно
робити, а отже — масив повністю відсортований.
Опишемо масив:
const n=10;
var a : array[1..n] of integer;
Запрограмуємо алгоритм сортування у вигляді процедури згідно блок-схеми:
procedure sort_array;
{сортування методом бульбашки}
var treba : boolean;
i, j, t : integer;
begin
treba:=true;
while treba do
Begin
- 48 -treba:=false;
for i:=1 to n-1 do
if a[i]>a[i+1] then
Begin
t:=a[i];
a[i]:=a[i+1];
a[i+1]:=t;
treba:=true;
End;
End;
End;
Для зручності, опишемо додаткові процедури для роботи з масивом: процедуру
створення масиву з довільними значеннями елементів та процедуру виведення на
екран значення усіх елементів масиву — make_array та print_array відповідно:
procedure make_array;
{генерація масиву}
var i : integer;
begin
randomize;
for i:=1 to n do a[i]:=random(1000);
end;
procedure print_array;
{виведення масиву}
var i : integer;
begin
for i:=1 to n do write(a[i]:5);
writeln;
end;
Де процедура randomize встановлює генератор випадкових чисел на наступне
число. Функція random(x : integer) повертає випадкове значення в межах
[0 ; x ] . Якщо цю функцію використовувати без аргументу, то значення, яке
поверне функція буде випадкове дійсне число в межах [0; 1 ) . Для отримання
щоразу випадкових чисел потрібно у програмі перед використанням функції random
виконати процедуру randomize.
Для тестування, тіло основної програми опишемо наступним чином:
Begin
make_array;
writeln('Створений масив:');
print_array;
- 49 -sort_array;
writeln('Відсортований масив:');
print_array;
End.
Виконавши написану програму, будемо мати щось подібне до:
Створений масив:
878 749 625 816 746 815 36 780 538 307
Відсортований масив:
36 307 538 625 746 749 780 815 816 878
Варто розуміти, що результат виконання програми щоразу буде різним, так як
ми використовуємо елементи роботи з випадковими числами.
Спробуйте поекспериментувати з різними наборами даних — щоб остаточно
зрозуміти й засвоїти суть цього методу сортування.
Сортування вибором
Сортування методом вибору є одним з простих у реалізації методів сортування.
- 50 -Також, як і метод сортування бульбашкою, цей метод не потребує додаткової пам'яті.
В деяких ситуаціях дає кращі результати ніж сортування бульбашкою. Примітним є
те, що в житті ми здебільшого й користуємося цим методом сортування коли нам
потрібно відсортувати набір речей. Наприклад, розкладаючи гральні карти однієї
масті по старшинству.
Яким чином ми це робимо?
Спершу ми знаходимо найменшу карту (6) й кладемо її з лівого краю, окремо
від решти карт. Далі, шукаємо найменшу карту з решти — 7. Знайшовши її —
кладемо поруч біля 6. Таким чином у нас корти, ніби, розділилися на 2 групи: в
першій групі карти відсортовані, а в другій — ні. Попередні кроки повторюємо,
допоки на якомусь кроці не отримаємо лише одну групу карт — відсортованих.
Опишемо словесно алгоритм сортування вставками:
1. Знаходимо в масиві найменше значення
2. Міняємо знайдене найменше значення місцями із першим значеннями у
масиві
3. Повторюємо кроки 1-2, доки список не завершиться (починаючи з другої
позиції).
Тобто, для набору 5, 3, 2, 4, 1 процес сортування відбуватиметься
наступним чином:
Блок схема алгоритму матиме вигляд:
- 51 -Реалізовуючи алгоритм сортування вибором, будемо використовувати
попередні позначення й описані вище процедури заповнення та виведення масиву.
procedure sort_array;
{сортування методом вибору мінімального елемента}
var i, j, min, min_i, t : integer;
begin
for i:=1 to n do
Begin
min_i:=i;
min:=a[i];
for j:=i+1 to n do
if (a[j]<min) then
Begin
min:=a[j];
min_i:=j;
End;
t:=a[i];
a[i]:=min;
a[min_i]:=t;
End;
end;
В змінних min та min_i зберігаємо значення найменшого елементу та індекс
цього ж найменшого елементу відповідно.
- 52 -Задача 1. Медіана чисел
Ця задача (1141) взята з “E-Olimp”, доступна в мережі за адресою:
http://www.e-olimp.com.ua/ua/problems/1141
Медіаною набору різних чисел називається таке число m, що кількість чисел,
більших за m, рівна кількості чисел, менших за m. Наприклад, медіаною множини
{1, 4, 2, 5, 7} буде 4, так як існує два числа, більших 4 (числа 5 і 7), і два числа,
менших 4 (1 і 2). Множина {1, 5, 8, 3} не має медіани, так як жоден з її елементів не
задовольняє наведеним вище умовам.
Технічні умови
Вхідні дані. У єдиному рядку вхідного файлу задано n (n ≤ 1000) різних
натуральних чисел, кожне з яких не більше 1000.
Вихідні дані. Виведіть значення медіани вхідних чисел. Якщо медіани не
існує, вивести -1.
Приклад.
Введення Виведення
1 4 2 5 7 4
Аналіз задачі
Алгоритм розв'язку задачі відбуватиметься в такі етапи:
• читання масиву елементів,
• сортування елементів по зростанню,
• знаходження медіани.
Виходячи з умови можна сказати, що який би не був набір парної кількості
елементів, ми в будь-якому разі не зможемо знайти медіани. Отже, одразу після
завершення читання даних ми повинні відслідкувати цей випадок і одразу виводити
результат.
Якщо ж кількість чисел непарна, тоді необхідно буде здійснювати сортування.
Для наочності, використаємо сортування “бульбашкою”.
- 53 -Останнім етапом є знаходження медіани — вочевидь, медіана у
відсортованому масиві, з непарною кількістю елементів міститиметься саме на
позиції (n div 2)+1.
Програмування розв'язку задачі
Програмування розв'язку зрозуміле з вихідних кодів.
program mediana;
var m : array[1..1000] of integer;
n, i, temp : integer;
treba : boolean;
begin
n:=0;
while (not eoln) do
Begin
inc(n);
read(m[n]);
End;
if (n mod 2 = 0) then writeln(-1)
else
Begin
treba:=true;
while treba do
Begin
treba:=false;
for i:=1 to n-1 do
if m[i]>m[i+1] then
begin
temp:=m[i];
m[i]:=m[i+1];
m[i+1]:=temp;
treba:=true;
end;
End;
writeln(m[(n div 2)+1]);
End;
end.
Задача 3. Перестановка
Ця задача (1141) взята з “E-Olimp”, доступна в мережі за адресою:
http://www.e-olimp.com.ua/ua/problems/354
- 54 -Дано послідовність, що складається з N натуральних чисел. Написати
програму, що визначає, чи є ця послідовність перестановкою перших N натуральних
чисел.
Технічні умови
Вхідні дані. У єдиному рядку задано спочатку число N, а потім — N
натуральних чисел через пропуск. N - не більше 10000, а кожне з чисел менше
2000000.
Вихідні дані. Вивести 0, якщо послідовність виявиться перестановкою, а якщо
ні - мінімальне число, що не входить в цю послідовність.
Приклад.
Введення Виведення
3 1 4 2 3
Аналіз задачі14
Цю задачу можна розв'язати кількома методами. Звісно, можна перевіряти
входження кожного з чисел від 1 до n у вхідну послідовність; можна використати
знання про суму арифметичної прогресії. Ми ж вдамося до іншого методу:
• зчитати масив чисел
• посортувати числа в порядку зростання
• 0-му елементу масиву присвоїти значення “0”
• від 0-го і до останнього елемента масиву перевіряти значення різниці
сусідніх елементів масиву:
◦ як тільки знайдемо два елемента, різниця між якими відмінна від
одиниці — закінчуємо цикл перегляду елементів масиву й виводимо
знайдений результат.
Програмування розв'язку задачі
var n, i, rez : longint;
a : array[0..10000] of longint;
procedure sort_array;
14 Розв'язання задачі за [8].
- 55 -{сортування методом вибору мінімального елемента}
var i, j, min, min_i, t : longint;
begin
for i:=1 to n-1 do
Begin
min_i:=i;
min:=a[i];
for j:=i+1 to n do
if (a[j]<min) then
Begin
min:=a[j];
min_i:=j;
End;
t:=a[i];
a[i]:=min;
a[min_i]:=t;
End;
end;
begin
read(n);
for i:=1 to n do read(a[i]);
sort_array;
a[0]:=0; rez:=0; i:=0;
while (i<=n-1) and (rez=0) do
Begin
if a[i+1]-a[i]<>1 then rez:=a[i]+1;
inc(i);
End;
writeln(rez);
end.
Задачі на самостійне опрацювання
1. http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1017&
1017 — Ланцюг
Є N шматків ланцюга, кожен i -й з яких містить Li
ланок. Можна
розгинати довільні ланки та потім згинати їх знову, з’єднуючи окремі шматки.
Завдання. Напишіть програму, що за кількістю шматків ланцюга N та кількістю
ланок у шматках Li визначає мінімальну кількість ланок, яку потрібно розігнути
та зігнути знову, щоб з’єднати усі шматки в один ланцюг. Ланцюг не може мати
розгалужень, тобто кожна його ланка повинна бути з’єднана з двома іншими ланками
(крім двох ланок з країв ланцюга, що повинні бути з’єднані лише з однією ланкою).
- 56 -Вхідні дані. В першому рядку знаходиться ціле число N ( 2N 10000 ). В
другому рядку знаходяться N цілих чисел Li
( 1Li1000000000 ),
розділених пропуском.
Вихідні дані. В єдиному рядку повинно знаходитися ціле число — найменша
кількість ланок, яку потрібно розігнути та зігнути знову, щоб отримати один ланцюг
з усіх шматків.
2. Спробуйте розв'язати задачу Перестановка оптимальнішим методом, відмінним від
описаного.