Середовища для навчання програмування

Класифікація алгоритмів 

в компетентнісних завданнях 

з теми «Алгоритми та програмування»

Під час розв’язування компетентнісних задачах з інформатики створюються, реалізуються, тестуються та найчастіше використовуються:

·        алгоритми форматування(редагування) об’єктів за даними параметрами;

·        алгоритми переміщення(розміщення) об’єктів за даними параметрами;

·        алгоритми видалення(приховування) об’єктів за даними параметрами;

·        алгоритми перевірки властивостей об’єктів за даними параметрами;

·        алгоритми  зміни або заміни властивостей об’єктів за даними параметрами;

·        обчислювальні алгоритми: алгоритми-калькулятори;

·        алгоритми пошуку  об’єктів за даними параметрами;.

·        алгоритми фільтрування змінних величин у лінійному масиві;

·        алгоритми (створення)генерування об’єктів: алгоритми-генератори; 

·        алгоритми перестановки та впорядкування числових та символьних  величин.

 В ході розв’язування компетентнісних задач  з інформатики на початкових етапах розв’язування проводиться аналіз властивостей об’єктів та даних умови для того, щоб використати уміння та навички під час реалізації різних видів алгоритмів, а саме створюються:

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.

Приклад. 4³=4*4*4=64;  0,3⁶=0,3*0,3*0,3*0,3*0,3*0,3=0,000729

Для того щоб можливо було написати рекурсивну функцію необхідно виділити основні рекурентні співвідношення. Ми знаємо, що 4⁰ = 1 та 4¹ = 4. Кожна наступна степінь 4 утворюється за принципом множення на 4 числа, що утворилося раніше. Отже, справедливими будуть такі формули:

R(0) = 1,

R(1) = 4,

R(k) = 4 * R(k - 1).

Завдання 3. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою програмування.

Приклад  3. Рекурсивний алгоритм суми цифр цілого невід’ємного числа.

Побудуємо математичну модель рекурсивного алгоритму суми цифр цілого невід’ємного числа.

Означення. Сумою цифр  s(m)=m₁+m₂+m₃+…+ m_k

цілого невід'ємного числа m= m₁m₂m₃…+m_k 

називається сума усіх розрядів цілого невід'ємного числа  і позначається 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 ≤ 10⁵).

Вихідні дані. Кількість способів, якими можна відібрати солдат в розвідку описаним вище способом.

Приклад вхідних та вихідних даних:

Введення      Виведення

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.

Завдання 4. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою програмування.

Фронтальне опитування

1.  Яке походження терміна «алгоритм»?
2.  Що ми розуміємо під поняттям «алгоритм»?
3.  Що таке допустимі команди виконавця?
4.  Які є способи опису алгоритмів?
5.  Які властивості повинен мати алгоритм?
6.  Що означає скінченність (дискретність) алгоритму?
7.  Що таке формальність алгоритму?
8.  Що означає масовість алгоритму?

Приклад 5. Рекурсивний алгоритм сортування лінійного масиву чисел з процедурою

Завдання 1. Реалізувати і протестувати алгоритм сортування мовою Паскаль лінійного масиву на 10 цілих чисел.

Program SORT;

var a: array [1..10] of integer; {Масив елементів}

    n: integer;

procedure QuickSort (L, R: Integer); {Швидке сортування масиву A []}

var i, j, x, s, y: integer;

begin    i:=l; j:=r;    x:=a[(l+r) div 2];

  repeat

      while (A[i]<x) do i:=i+1;

      while (x<A[j]) do j:=j-1;

       if (i<=j) then

       begin

      y:=A[i]; a[i]:=a[j]; a[j]:=y;

      i:=i+1; j:=j-1;

    end;

  until (i>j);

  if (l<j) then QuickSort (l, j);

  if (i<r) then QuickSort (i, r);

end;

begin

     writeln ( 'введіть 10 елементів масиву:');

     for n:=1 to 10 do a[n]:=random(200)-random(300);

    { for n:=1 to 10 do readln (a[n]);}

     QuickSort (1, 10); {На вході: ліва і права межа сортування}

     writeln ( 'після сортування:');

     for n:=1 to 10 do write(a[n], '        ' ‘);

end.

Завдання 5. Знайдіть інваріантні властивості  в цьому рекурсивному алгоритмі сортування чисел в одновимірному масиві.

Завдання 6.

Дев'ять сервісів для навчання програмуванню.

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

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

1. Code.org

Пропоную всім почати саме з цього ресурсу. Він створений спеціально для новачків і орієнтований на навчання школярів, хоча, звичайно, підійде користувачам будь-якого віку і складів розуму. Серед партнерів сайту такі титани, як Apple, Google, Facebook, Amazon. На першому занятті Марк Цукерберг розповідає, навіщо взагалі потрібно вчитися програмувати.

Раджу пройти всі випуски для початківців. Все просто і легко, ви розберетеся з азами програмування і дізнаєтеся, як алгоритм перетворюється в JavaScript-код.

2. Codecombat

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

На початку все просто, ви пишете код і відразу бачите на екрані, як він буде виконуватися. Потім завдання стають більш винахідливими, і вам доводиться думати все більше і навіть гуглити складні моменти.

Гра буде цікава практично всім. У неї можуть грати і новачки - дуже багато пояснюється у внутрішніх туторіали.

3. Bit's Quest

Ось ви освоїли дві простенькі іграшки, і прийшов час застосувати отримані знання з JavaScript і алгоритмам і пройти нетривіальні 14 рівнів.

У грі потрібно буде за допомогою JavaScript-коду управляти біт-Бакет ботом, виконуючи завдання до кожного рівня. Найчастіше завдання - дістатися до виходу з лабіринту, але іноді доводиться битися з ворожим кораблем.

Вам належить розібратися, що таке події, як використовувати функції, і може знадобитися застосувати замикання.

Але залишимо ненадовго гри - їх дуже багато, і вони всі схожі. Звернемося до шкіл програмування, які допоможуть отримати більш фундаментальні і системні знання.

4. Hello Processing

По суті, це скрінкасти з інтерактивом, в якому вам розповідають, як можна за допомогою простих команд в JavaScript почати малювати геометричні фігури в браузері і якось ними навіть управляти.

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

5. Codecademy

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

Вибір курсів задовільний: є досить грамотні курси по HTML, CSS, JS, jQuery. Якщо раптом ви замислюєтеся про серверній стороні справи, для вас є заняття по PHP, Ruby, Python. Завжди було цікаво, як працювати з API сервісів? У «Кодакадеміі» теж цьому вчать.

6. Codeschool

Сервіс створений програмістами для програмістів, все як ми любимо - але він навряд чи підійде тим, хто поки по той бік консолі. Напевно, це найкорисніший ресурс для тих, хто вирішить стати професійним програмістом (але не робіть цього, прошу вас). Тут є все, що потрібно знати про сучасний інтернеті, є навіть курси по створенню iOS-додатків. Більшість курсів не безкоштовні, але воно того варте.

7. Hexlet

Гідний представник онлайн навчання з Росії. Зізнаюся, жодного курсу я там не проходив, але, судячи з відгуків моїх колег, сайт варто уваги.

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

І, звичайно, розробці на Android можна приділити час, якщо є далекосяжні плани на цю платформу.

8. Coursera

«Курсера», швидше за все, не підійде людям, які не хочуть програмувати професійно, так як матеріал розглядається докладно і глибоко, і потрібно серйозно підійти до питання навчання, щоб успішно пройти курс.

Рекомендую поглянути на Fundamentals of Computing. За результатами цього курсу, як стверджують автори, ви зможете почати програмувати на Python і вирішувати різні технічні завдання. Для початку навчання не потрібні навички програмування, але курси читаються англійською мовою, і не до всіх з них є російські субтитри.

9. Ruby Warrior

Сценарій гри: рубай-воїн повинен вбити всіх поганих хлопців і врятувати принцесу-блондинку (насправді немає). Керувати героєм потрібно за допомогою Ruby-коду.

Для проходження потрібно розбиратися в коді, але знань по Ruby буде досить самих базових.

Вас не будуть вчити програмувати, зате змусять вирішувати логічні завдання, причому іноді до рішень я доходив дуже довго.

Ця гра мені здалася найскладнішою - і найцікавішою.