Класифікація алгоритмів
в компетентнісних завданнях
з теми «Алгоритми та програмування»
Під час розв’язування компетентнісних задачах з інформатики створюються, реалізуються, тестуються найчастіше використовуються:
· алгоритми форматування(редагування) об’єктів за даними параметрами;
· алгоритми переміщення(розміщення) об’єктів за даними параметрами;
· алгоритми видалення(приховування) об’єктів за даними параметрами;
· алгоритми перевірки властивостей об’єктів за даними параметрами;
· алгоритми зміни або заміни властивостей об’єктів за даними параметрами;
· обчислювальні алгоритми: алгоритми-калькулятори;
· алгоритми пошуку об’єктів за даними параметрами;.
· алгоритми фільтрування змінних величин у лінійному масиві;
· алгоритми (створення)генерування об’єктів: алгоритми-генератори;
· алгоритми перестановки та впорядкування числових та символьних величин.
В ході розв’язування компетентнісних задач з інформатики на початкових етапах розв’язування проводиться аналіз властивостей об’єктів та даних умови для того, щоб використати уміння та навички під час реалізації різних видів алгоритмів, а саме створюються:
1.Нелінійні алгоритми:
1.1. Алгоритми розгалуження :
1.1.1. Алгоритми з повним розгалуженням;
1.1.2. Алгоритми з певним розгалуження;
1.2. Алгоритми з узагальненим вибором:
1.2.1. Алгоритми з повним узагальненим вибором;
1.2.2. Алгоритми з неповним узагальненим вибором;
1.3 . Циклічні алгоритми:
1.3.1 Циклічні алгоритми з лічильником з кроком +1;
1.3.2 Циклічні алгоритми з лічильником з кроком -1;
1.3.3 Циклічні алгоритми з лічильником з кроком +m;
1.3.4 Циклічні алгоритми з лічильником з кроком –m;
1.4. Циклічні алгоритми з передумовою:
1.4.1. Циклічні алгоритми з простою передумовою;
1.4.2. Циклічні алгоритми з складеною передумовою;
1.5. Циклічні алгоритми з післяумовою:
1.5.1. Циклічні алгоритми з простою післяумовою;
1.5.2. Циклічні алгоритми з складеною післяумовою.
1.6. Вкладені циклічні алгоритми:
1.6.1. Цикл лічильником має цикл з післяумовою;
1.6.2. Цикл лічильником має цикл з передумовою;
1.6.3. Цикл лічильником має цикл з лічильником;
1.6.4. Цикл передумовою має цикл з лічильником;
1.6.5. Цикл передумовою має цикл з передумовою;
1.6.6. Цикл передумовою має цикл з лічильником;
1.6.7. Цикл ісляумовою має цикл з лічильником;
1.6.8. Цикл післяумовою має цикл з передумовою;
1.6.9. Цикл післяумовою має цикл з післяумовою.
1.7. Рекурсивні алгоритми:
1.7.1. Алгоритм з рекурсивною процедурою;
1.7.2. Алгоритм з рекурсивною функцією;
1.8. Ітераційні алгоритми без рекурсії:
1.7.1. Алгоритм з процедурною ітерацією без рекурсії;
1.7.2. Алгоритм з ітераційною функцією без рекурсії;
Завдання для самостійного опрацювання.
Приклад 1. Рекурсивний алгоритм факторіалу невід’ємного числа.
Побудуємо математичну модель рекурсивного алгоритму факторіалу невід’ємного числа.
Означення. Факторіалом цілого невід'ємного числа m називається добуток всіх натуральних чисел від 1 до m і позначається m!.
Приклади: 3!=1*2*3=6; 4!=1*2*3*4=24; 6!= 1*2*3*4*5*6=720.
Якщо створити функцію: q(m) = m!, то мають місце рекурентні співвідношення:
k! = k*q(k – 1) (*)
q(0) = 1 (**)
Перша рівність описує крок рекурсії - метод обчислення q(k) через q(k - 1). Друга рівність вказує, коли при обчисленні функції слід зупинитися. Якщо його не використовувати, то функція буде працювати нескінченно довго.
Наприклад, значення q(7) можна обчислити таким чином:
7! = 7 * q(6) = …= 7 * 6 * 5 * q(4) = 7 * 6 * 5 * 4 * q(3) =
= 7 *6* 5 * 4 * 3 * q(2) = 7 * 6 * 5 * 4 * 3 * 2 * q(1) =
= 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1 = 7*720 = 5040
Очевидно, що при обчисленні q(k) слід зробити k рекурсивних викликів.
Завдання 1. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою програмування.
Приклад 2. Рекурсивний алгоритм піднесення до степеня числа.
Побудуємо математичну модель рекурсивного алгоритму піднесення до степеня числа.
Найпростішим та досить важливими для інформатики є числа, які є степенями 2. Отже, розглянемо на прикладі таких чисел рекурсивний алгоритм піднесення числа до степеня, який пізніше спробуємо реалізувати ітераційним методом.
Означення. Добуток р*р*р*……*р*р декількох однакових дійсних множників р називають степенем дійсного числа р, і записють степінь числа рm.
Приклад. 43=4*4*4=64; 0,36=0,3*0,3*0,3*0,3*0,3*0,3=0,000729
Для того щоб можливо було написати рекурсивну функцію необхідно виділити основні рекурентні співвідношення. Ми знаємо, що 40 = 1 та 41 = 4. Кожна наступна степінь 4 утворюється за принципом множення на 4 числа, що утворилося раніше. Отже, справедливими будуть такі формули:
R(0) = 1,
R(1) = 4,
R(k) = 4 * R(k - 1).
Завдання 3. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою програмування.
Приклад 3. Рекурсивний алгоритм суми цифр цілого невід’ємного числа.
Побудуємо математичну модель рекурсивного алгоритму суми цифр цілого невід’ємного числа.
Означення. Сумою цифр s(m)=m1+m2+m3+…+ mk
цілого невід'ємного числа m= m1m2m3…+mk
називається сума усіх розрядів цілого невід'ємного числа і позначається s(m)
Приклади: s(123)=1+2+3=6; s(1234)=1+2+3+4=10;
s(123456) = 1+2+3+4+5+6=21.
Суму чисел натурального числа k можна знайти за допомогою функції s(k), визначеної в такий спосіб:
s(0) = 0 (*)
s(k) =k mod 10 + s(k div 10) (**)
Умова продовження рекурсії: сума цифр числа дорівнює останній цифрі плюс сума цифр числа без останньої цифри (числа, поділеної без остачі на 10).
Умова закінчення рекурсії: Якщо число дорівнює 0, то сума його цифр дорівнює 0.
Наприклад, сума цифр числа 576 буде обчислюватися так:
s(576) = 6 + s(57) = 6 + 7 +s (5) = 6 + 7 + 5 + s(0) = 6 + 7 + 5 + 0 = 18.
Завдання 3. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою програмування.
Приклад 4. Відбір в розвідку [ACM, 1999]. Із n солдатів, вишикуваних в шеренгу, потрібно відібрати кількох в розвідку. Для здійснення цього виконується наступна операція: якщо солдат в шерензі більше ніж 3, то видаляються всі солдати, які стоять на парних позиціях, або всі солдати, які стоять на непарних позиціях. Ця процедура повторюється до тих пір, поки в шерензі залишиться 3 або менше солдатів. Їх і відсилають в розвідку. Обчислити кількість способів, якими таким чином можуть бути сформовані групи розвідників рівно з трьох осіб.
Вхідні дані. Кількість солдатів в шерензі n (0 <k ≤ 105).
Вихідні дані. Кількість способів, якими можна відібрати солдат в розвідку описаним вище способом.
Приклад вхідних та вихідних даних:
Введення Виведення
10 2
4 0
Математична модель рекурсивного алгоритму відбору розвідників.
Нехай функція r(m) кількість способів, якими можна сформувати групи розвідників з m осіб в шерензі. Оскільки нас цікавлять тільки групи по три розвідника, то r(1) = 0, r(2) = 0, r(3) = 1. Тобто з трьох осіб можна сформувати тільки одну групу, з одного або двох - жодної.
Якщо m – парне число, то застосовуючи дану процедуру видалення солдат в шерензі, ми отримаємо або 0,5m солдатів, що стоять на парних позиціях, або 0,5m солдатів, що стоять на непарних позиціях. Тобто r(m) = 2 · r(0,5m) при парному m.
Якщо n непарне, то після видалення залишиться або 0,5m солдатів стояли на парних позиціях, або 0,5m + 1 солдат, які стояли на непарних позиціях. Загальна кількість способів при непарному m рівне
r(m) = r(m/2) + r(m/2 + 1).
Таким чином, отримана рекурентна формула для обчислення значення r(n):
r(m) = 2 · r(m / 2), якщо m - парне =2k;
r (m) = r (m / 2) + r(m/ 2 + 1), якщо m - непарне =2k-1;
r (1) = 0, r(2) = 0, r (3) = 1.
Завдання для самостійного опрацювання
Задача 1. Козак Вус подарував вам набiр з n цифр
(тобто чисел вiд 0 до 9 включно). I хоче дiзнатися у вас: яку максимальну
кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна
цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам
потрiбно вибрати будь-які цифри з набору, вибрати їхнiй порядок та скласти
число з цих цифр. Звернiть увагу, що ви не зобов’язанi використати всi цифри.
Ви ж не можете вiдмовити Вусу? :)
Маленька пiдказка вiд
Математичної Сови:
Остача (залишок) вiд
дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр
числа x на число 3.
Число a є
кратним числу b (тобто a дiлиться на b) лише, якщо
остача вiд дiлення числа a на число b дорiвнює 0.
Технічні умови Програма Newnumbers читає
з пристрою стандартного введення у першому рядку мiстить одне цiле число n (1
⩽ n⩽5 · 105) — кiлькiсть цифр. У другому рядку записано n цiлих
чисел, кожне з яких має значення вiд 0 до 9 включно. Програма виводить на
пристрій стандартного виведення одне ціле число — максимальну кількість чисел
кратних 3, що можна скласти з цього набору.
Приклади
Введення
|
Виведення
|
1
0 |
1
|
14
8 8 4 8 1 1 0 0 2 1 9 3 4 1 |
8
|
Зауваження до
прикладів
У першому прикладі ми
можемо скласти лише одне число 0.
У другому прикладі з
цього набору ми можемо скласти максимум 8 чисел. Один iз можливих
способів — це скласти такі числа: 0, 0, 48, 9, 3, 21, 81, 84.
Невикористаними у нас залишаться цифри 1, 1.
Задача 2. Дано набiр з n цифр
вiд 0 до 9 включно. Потрібно дiзнатися, яку максимальну кiлькiсть чисел з них
можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була
використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які
цифри з набору, вибрати їх порядок та скласти число з цих цифр. Звернiть увагу,
що ви не зобов’язані використати всi цифри.
Математична підказка:
·
Остача (залишок) вiд
дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр
числа x на число 3.
·
Число a є кратним
числу b (тобто a дiлиться на b) лише, якщо остача вiд
дiлення числа a на число b дорiвнює 0.
Технічні умови. Програма читає
з пристрою стандартного введення у першому рядку одне цiле число n (1
⩽ n⩽5 · 105) — кiлькiсть цифр. У
другому рядку записано n цiлих чисел, кожне з яких має
значення вiд 0 до 9 включно. Програма виводить на пристрій стандартного
виведення одне цiле число — максимальну кiлькiсть чисел кратних 3, що можна
скласти з цього набору.
Приклади
Введення
|
Виведення
|
1
0 |
1
|
14
8 8 4 8 1 1 0 0 2 1 9 3 4 1 |
8
|
Зауваження до прикладів
У першому прикладi ми можемо скласти лише одне число 0.
У другому прикладi з цього набору ми можемо скласти
максимум 8 чисел. Один iз можливих способiв — це скласти наступнi
числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться
цифри 1, 1.
Математична модель до завдання:
Максимальна кількість
чисел обчислюється за формулою
n =p(0=mod3)+min(k(1=mod3);
m(2=mod3))+(1/3)*(max(k(1=mod3); m(2=mod3) -min(k(1=mod3); m(2=mod3))
де p(0=mod3) - це кількість цифр, що кратні 3.;
k(1=mod3) -це кількість цифр, що мають вигляд 3х+1;
m(2=mod3)) - це кількість цифр, що мають вигляд 3х+2;
Кодування алгоритму на СІ++
#include <iostream>
#include <cmath>
using namespace std;
int main(){
long long kol, tsifra, ost;
cin >> kol;
long long n = 0, L = 0, m = 0;
for (long long i = 0; i < kol; i++){
cin >> tsifra;
ost = tsifra % 3;
if (ost == 0)
n = n + 1;
else if (ost == 1)
L = L + 1;
else
m = m + 1;
}
long long rez = n + min(L, m) + (max(L, m) - min(L,m))/3;
cout << rez;
}
Кодування
алгоритму на мові Рython
var k,l,o,m,n,i,min,max,rez:longint;
begin
readln(n);
k:=0; l:=0; m:=0;
for i:=1 to n do
begin
read(o);
o:=(o mod 3);
case o of
0:k:=k+1;
1:l:=l+1;
2:m:=m+1;
end;
end;
if l>m then begin max:=l;
min:=m; end
else begin max:=m; min:=l; end;
rez:=k+min+((max-min) div 3);
write(rez);
endA.
Кодування алгоритму на мові Pascal
var k,l,o,m,n,i,min,max,rez:longint;
begin
readln(n);
k:=0; l:=0; m:=0;
for i:=1 to n do
begin
read(o);
o:=(o mod 3);
case o of
0:k:=k+1;
1:l:=l+1;
2:m:=m+1;
end;
end;
if l>m then begin max:=l;
min:=m; end
else begin max:=m; min:=l; end;
rez:=k+min+((max-min) div 3);
write(rez);
end.
Кодування на мові Pascal генератора перевірочних тестів(текстових файлів з даними)
до алгоритму:
var f:text;
n,p,i,k,l,m,min,max,a,o,rez,c:longint;
pp:boolean;
begin
read(n);
read(p);
assign(f,'figures.test.20');
rewrite(f);
writeln(f,n);
for i:=1 to n do
begin
pp:=true;
case p of
1:begin while pp do
begin a:=random(10); c:=(a mod 3); if c=0 then pp:=false; end; end;
2:begin while pp do
begin a:=random(10); c:=(a mod 3); if c=1 then pp:=false; end; end;
3:begin while pp do
begin a:=random(10); c:=(a mod 3); if c=2 then pp:=false; end; end;
4:begin while pp do
begin a:=random(10); c:=(a mod 3); if ((c=0) or (c=1)) then pp:=false; end; end;
5:begin while pp do
begin a:=random(10); c:=(a mod 3); if ((c=0) or (c=2)) then pp:=false; end; end;
6:begin while pp do
begin a:=random(10); c:=(a mod 3); if ((c=2) or (c=1)) then pp:=false; end; end;
7:a:=random(10);
end;
write(f,a,' ');
o:=(a mod 3);
case o of
0:k:=k+1;
1:l:=l+1;
2:m:=m+1;
end;
if l>m then begin max:=l;
min:=m; end else begin max:=m; min:=l; end;
end;
rez:=k+min+((max-min) div 3);
writeln(f,'');
write(f,rez);
close(f);
write(rez);
end.
Тести для перевірки алгоритму:
Тест 1.
Ввід 4
5 5 8 8
Вивід 1
Тест 2.
Ввід 8
5 5 7 8 8 5 8 4
Вивід 3
Тест 3.
Ввід 16
5 5 7 8 6 8 5 8 4 6 6 3 4 2 8 0
Вивід 9
Тест 4.
Ввід 32
5 5 7 8 8 5 8 4 4 2 8 2 4 7 8 5 4 5 8 8 7 1 8 8 4 7 8 4 5 7 1 7
