Дистанційна освіта з інформатики в період січня 2021 року
11.01.21- 15.01.21
Тема: Класифікація алгоритмів. Середовища для реалізації алгоритмів. Інтерфейс додатків для програмування.
Теоретична частина.
Знайомство з інтерфейсом середовища програмування Scratch. Для цього подивіться відео-урок.
Відео-урок: https://youtu.be/wSsd6iDFRXA
Класифікація алгоритмів
в компетентнісних завданнях
з теми «Алгоритми та програмування»
Під час
розв’язування компетентнісних задачах з інформатики створюються, реалізуються,
тестуються найчастіше використовуються:
· алгоритми форматування(редагування) об’єктів
за даними параметрами;
· алгоритми переміщення(розміщення) об’єктів
за даними параметрами;
· алгоритми видалення(приховування) об’єктів
за даними параметрами;
· алгоритми перевірки властивостей об’єктів за
даними параметрами;
· алгоритми зміни або заміни
властивостей об’єктів за даними параметрами;
· обчислювальні алгоритми:
алгоритми-калькулятори;
· алгоритми пошуку об’єктів за даними
параметрами;.
· алгоритми фільтрування змінних величин у
лінійному масиві;
· алгоритми (створення)генерування об’єктів:
алгоритми-генератори;
· алгоритми перестановки та впорядкування
числових та символьних величин.
В ході
розв’язування компетентнісних задач з інформатики на початкових етапах
розв’язування проводиться аналіз властивостей об’єктів та даних умови для того,
щоб використати уміння та навички під час реалізації різних видів алгоритмів, а
саме створюються:
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. Реалізувати та протестувати цей рекурсивний алгоритм мовою програмування Pascal
Реалізація: Використання рекурсії дозволяє легко (майже дослівно) запрограмувати обчислення за рекурентними формулах. Наприклад, нижче написана програма Pascal, використовує рекурсивну функцію для обчислення факторіалу n!:
program Factorial;
var n: integer;
function Fact(i:integer):longint;
begin
if (i=1) or (i=0) then Fact:=1
else Fact:=i*Fact(i-1);
end;
begin
write(‘Введіть число n:’);
readln(n);
writeln(‘Факторіал n!=’, Fact(n));
end.
Приклад 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. Рекурсивний алгоритм суми цифр цілого невід’ємного числа.
Побудуємо
математичну модель рекурсивного алгоритму суми цифр цілого
невід’ємного числа.
Означення. Сумою
цифр 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.
Приклад
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.
Як вам завантажити середовище програмування Scratch на смартфон?
Для цього подивіться відео-урок:
Відео-урок: https://youtu.be/OPo06hTlprY
Завдання 2.
Як вам завантажити середовище програмування PascalABC на смартфон?
Для цього подивіться відео-урок:
Відео-урок: https://youtu.be/VIJA60OBQNg
Завдання 3.
Як вам завантажити середовище програмування мовою Python 3 на смартфон?
Для цього подивіться сайт: thonny.org або
https://thonny.org/
Також ознайомтеся з можливостями інтегрованого середовища Thonny для програмування мовою Python на веб-сайті:
https://uk.m.wikipedia.org/wiki/Thonny
Інформація для "просунутих" юних програмістів.
Якщо ви хочете розробляти алгоритми онлайн різними мовами програмування, то вам варто ознайомитися і скористатися веб-сайтом: http://www.tutorialspoint.com/codingground.htm
Якщо ви близькі з open-source спільнотою, то ви напевно чули про Eclipse. Будучи доступним для Linux, Windows і OS X, Eclipse де-факто є open-source IDE для розробки на Java. Існує безліч розширень і аддонів, які роблять Eclipse корисним для різного роду завдань.
Одним з таких розширень є PyDev, що надає інтерактивну консоль Python і можливості для налагодження і автодоповнення коду. Встановити його просто: запустіть Eclipse, виберіть Help → Eclipse Marketplace, потім знайдіть PyDev. Натисніть «Install» і при необхідності перезапустити Eclipse.
Завдання 4.
Створити презентацію на декілька слайдів про навчальні мови програмування алгоритмів. У даній презентації дайте відповідь на такі запитання: "Чим відрізняються мови програмування низького та високого рівня?" "Які способи мислення використовують програмісти для розробки алгоритмів?" "Якими мовами програмування розробляється штучний інтелект для роботів-гуманоїдів?"
Результат виконання завдання 4 треба надіслати вашому учителю на електронну скриньку:
vinnser@gmail.com (Сергій Петрович).
Немає коментарів:
Дописати коментар