четвер, 23 травня 2019 р.

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



Класифікація алгоритмів 
в компетентнісних завданнях 
з теми «Алгоритми та програмування»

Під час розв’язування компетентнісних задачах з інформатики створюються, реалізуються, тестуються та використовуються:
·        алгоритми форматування(редагування) об’єктів за даними параметрами;
·        алгоритми переміщення(розміщення) об’єктів за даними параметрами;
·        алгоритми видалення(приховування) об’єктів за даними параметрами;
·        алгоритми перевірки властивостей об’єктів за даними параметрами;
·        алгоритми  зміни або заміни властивостей об’єктів за даними параметрами;
·        обчислювальні алгоритми: алгоритми-калькулятори;
·        алгоритми пошуку  об’єктів за даними параметрами;.
·        алгоритми фільтрування змінних величин у лінійному масиві;
·        алгоритми (створення)генерування об’єктів: алгоритми-генератори; 
·        алгоритми перестановки та впорядкування числових та символьних  величин.

 В ході розв’язування компетентнісних задач  з інформатики на початкових етапах розв’язування проводиться аналіз властивостей об’єктів та даних умови для того, щоб використати уміння та навички під час реалізації різних видів алгоритмів, а саме створюються:
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.8.  Цикл післяумовою має цикл з післяумовою.
1.7.  Рекурсивні алгоритми:
                    1.7.1.  Алгоритм з рекурсивною процедурою;
                    1.7.2.  Алгоритм з рекурсивною функцією;
1.8.  Ітераційні алгоритми без рекурсії:
                    1.7.1.  Алгоритм з процедурною ітерацією без рекурсії;
                    1.7.2.  Алгоритм з ітераційною функцією без рекурсії;

https://russian-kenguru.ru/konkursy/kit- це посилання на російський конкурс з інформатики "КИТ".


Компетентнісні завдання для самостійного  опрацювання.

Приклад  1. Рекурсивний алгоритм факторіалу невід’ємного числа.
Побудуємо математичну модель рекурсивного алгоритму факторіалу невід’ємного числа.
Означення. Факторіалом цілого невід'ємного числа називається добуток всіх натуральних чисел від 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) слід зробити рекурсивних викликів.
Завдання 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
Для того щоб можливо було написати рекурсивну функцію необхідно виділити основні рекурентні співвідношення. Ми знаємо, що 4= 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.
Завдання 4. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою програмування.

Приклад 5.  Використання алгоритму розгалуження в задачах на рух.

Завдання 5. На вокзалі з потягу зійшли два пасажира і направились одночасно в один і той же пункт А. Перший пасажир половину часу йшов зі швидкістю v1 м/год, а другу половину часу йшов зі швидкістюv2 м/год. Другий пасажир йшов першу половину шляху зі швидкістю v2м/год, а другу половину шляху зі швидкістю v1 м/год. Допоможіть слідчому, дізнатися, яку відстань долали пасажири від виходу із потяга до пункту призначення і хто першим прибуває в пункт А.  Скласти і реалізувати алгоритм  для вияснення, хто першим прибуває у пункт призначення і на скільки раніше, ніж інший, якщо відомо, що перший пасажир витрачає на весь свій шлях хвилин?
program  TOURIST_1;                                                                                               {назва    алгоритму}
var  v1,v2,t1,t2, s1 : real;                       {оголошення  змінних величин:v1,v2,t1,t2, s1,s2 – це дійсні числа}
begin                                                                                                             { початок  виконання  алгоритму}
  writeln( 'v1='); readln(v1); writeln( 'v2='); readln(v2);  writeln( 't1='); readln(t1);      
   s1:=(v1+v2)*t1*0.5;            {обчислення за фор-лою відстані від потяга до пункту}
writeln('Довжина шляху пасажирів', s1, '  метрів ');                                            { виведення результату}
t2:=(v1+v2)* (v1+v2)*t1*0.25/( v1*v2);         {обчислення за фор-лою  часу другого пасажира}
writeln('Час руху другого пасажира: ',t2, '  хвилин ');   { виведення результату}
  if  t2 –t1=0 then writeln('У пункт  А  пасажири прибувають одночасно');   
if  t2 –t1>0 then writeln('У пункт  А раніше прибуває перший пасажирна: ', t2 –t1, '  хвилин. ');   end.                                                                                    
Протестуйте алгоритм для  таких значень  {v1; v2; t1}: а)(90; 80;30)=0,1 хв; б) (85; 85; 40)=0 хв; в)(60; 80; 20)=0,42 хвилини.
Приклад 6.  Використання алгоритмів в фінансових задачах.

Завдання 6.1.  Якщо через рівні проміжки часу на депозитну картку вноситься деяка постійна сума К грн(періодичні внески) під складні відсотки Р% , то заощадження обчислюється за формулою
S=K*(1+p/100)*(exp(ln(1+p/100)*n)-1)/( (1+p/100)-1).
Скласти і реалізувати алгоритм  для вияснення cум грошей на депозитній картці через декілька років.
program BABLO_2;                     {назва    алгоритму}
var  k,p,r, s : real;      n, i: integer;  {оголошення  змінних величин:k,p,r,n, s – це дійсні числа}
begin                                                                                      { початок виконання  алгоритму}
k:=1000+random(100);  writeln( ' Якщо сума, що вноситься на депозитk=', k); writeln;
p:=7+random(10);  writeln( ' Якщо відсоткова ставка для цього депозиту р=', p); writeln;
n:=1+random(10);  writeln( ' Якщо кількість років існування депозитуn=', n); writeln;
s:=1+p/100;   u:=1;                                 {обчислення початкового відсотку для виконання  алгоритму}
for i:=1 to n do begin                   {виконання циклу з лічильником по рокам для обчислення грошей}
u:=u*(1+p/100);    s:=1+p/100;    s:= K*s*(u-1)/(s-1); 
writeln( 'Кількість грошей на депозиті через', i, ' років S=', s); writeln;end; writeln('********'); end.
Протестуйте алгоритм декілька разів і порівняйте результати. Самостійно змініть діапазон вибору випадкових чисел в алгоритмі.

Завдання 6.2. Якщо протягом n років  на  депозитну картку  з сумою К грн нараховується разів щорічно деякий постійний складний відсоток Р% , то заощадження обчислюється за формулою
S=K* exp(ln (1+p/(100*m))*n*m)
Скласти і реалізувати алгоритм  для вияснення cум грошей на депозитній картці через декілька років.
program BABLO_3;                                                                             {назва    алгоритму}
var  k,: real;      u,m,n, i: integer;                          {оголошення змінних величин  дійсні числа та цілі числа}
begin                                                              { початок  виконання алгоритму і введення випадкових значень}
k:=1000+random(1000);  writeln( ' Якщо початкова сума на депозитіk=', k); writeln;
p:=7+random(10);  writeln( ' Якщо відсоткова ставка для цього депозиту р=', p); writeln;
n:=1+random(5);  writeln( ' Якщо кількість років існування депозитуn=', n); writeln;
m:=1+random(12);  writeln( ' Якщо кількість  нарахувань на депозит за рік m=', m); writeln;
s:=k; u:=n*m;                                                    {обчислення чисел для виконання  циклу в алгоритмі}
for i:=1  to  u  do  begin        {виконання циклу з лічильником по нарахуванням для обчислення грошей}
s:= K*exp(ln(1+p/(100*i)))*i*i;
writeln( 'Кількість грошей на депозиті  після', i, ' –го нарахування S=', s); writeln; end; writeln('*****');   end.
Протестуйте алгоритм декілька разів і порівняйте результати. Самостійно змініть діапазон вибору випадкових чисел в алгоритмі.

Приклад 7. Алгоритми пошуку властивостей цілих чисел

Завдання 7.1. Скласти і реалізувати алгоритм  для знаходження   кількості цифр, суми цифр натурального числа, подільності на цифри, якщо ціле число задане випадковим чином.
program SummaNumer;                     {назва    алгоритму підрахунку суми цифр цілого числа}
var  m, n, i, m1, k, s: integer;                {оголошення  змінних величин: цілі числа}
begin                            {початок   виконання алгоритму і введення випадкових натуральних чисел}
m:=(10+random(5))*(20+random(7)) *(random(20)) + 1+random(3) ;   
writeln( ' Якщо натуральне число  m=', m); writeln;  m1:=m; k:=0; s:=0; n:=0;
repeat    n:=m mod 10; k:=k+1; s:=s+n;  m:=m div 10;   until m=0; 
     {виконання циклу з  післяумовою  для обчислення}
writeln('Сума цифр числа ', m1,   ' дорівнює числу: ', s); writeln;
writeln('Кількість цифр числа ', m1,   ' дорівнює числу: ', n); writeln;
if (m1 mod 2) =0 then writeln(m1,   ' - це парне число ') writeln;
if (m1 mod 2) =1 then  writeln(m1,   ' - це непарне число ') writeln;
if (s mod 3) =0 then writeln(m1,   ' - це число має вигляд 3k, ділиться на 3 націло') writeln;
if (s mod 3) =1 then writeln(m1,   ' - це число  має вигляд 3k+1') writeln;
if (s mod 3) =2 then writeln(m1,   ' - це число  має вигляд 3k+2') writeln; m:= m1 mod 100;
if (m mod 4) =0 then writeln(m1,   ' - це число  має вигляд 4k, ділиться на 4 націло') writeln;
if (m mod 4) =1 then writeln(m1,   ' - це число  має вигляд 4k+1') writeln;
if (m mod 4) =2 then writeln(m1,   ' - це число  має вигляд 4k+2') writeln;
if (m mod 4) =3 then writeln(m1,   ' - це число  має вигляд 4k+3') writeln; m:= m1 mod 10;
if (m mod 5) =0 then writeln(m1,   ' - це число  має вигляд 5k, ділиться на 5 націло') writeln;
if ( (s mod 3) =0)  and ((m mod 2)=0) then writeln(m1,   ' - це число  має вигляд 6k, ділиться на 6 націло') writeln;
if (m mod 7) =0 then writeln(m1,   ' - це число  має вигляд 7k, ділиться на 7націло') writeln;
m:=m1; m:= m mod 1000;
if (m mod 8) =0 then writeln(m1,   ' - це число  має вигляд 8k, ділиться на 8націло') writeln;
if (s mod 9) =0 then writeln(m1,   ' - це число має вигляд 9k, ділиться на 9націло') writeln;
if (m mod 10) =0 then writeln(m1,   ' - це число має вигляд 10k, ділиться на10 націло') writeln;
end.   {закінчення алгоритму}
Протестуйте алгоритм  чотири рази та перевірте правильність результатів.
Завдання 2. Скласти і реалізувати алгоритм  знаходження   кількості першої цифри  від початку у цілому числа, що задане випадковим чином.
Program Cifr1;                                                     {оголошення  назви алгоритму}
var n, x,c,c1,k: integer;                                          {оголошення  змінних величин:цілі числа}
begin
    n:=(10+random(5)) *(20+random(7)) *(random(20)) + 1+random(3);    {випадкове число}
writeln( ' Якщо натуральне число  n=', n); writeln;            {виведення на екран випадкового числа}
x:=n;     while n>9 do      n:=n div 10;    c1:=n;    k:=0;                   {цикл з передумовою}
repeat
       c:= x mod 10;       if c=c1 then k:=k+1;      x:=x div 10;   until x=0; {цикл з післяумовю}
writeln(' Кількість першої цифри дорівнює:   ' 
k);  end.
Протестуйте алгоритм  чотири рази та перевірте правильність результатів.
Завдання 3. Скласти і реалізувати алгоритм  знаходження   кількості другої від початку цифри у цілому числа, що задане випадковим чином.
Program Cifr2;                                                                                           {оголошення  назви алгоритму}
var n, x,c,c1,k: integer;                                                           {оголошення  змінних величин: цілі числа}
begin
    n:=(10+random(5)) *(20+random(7)) *(random(20)) + 1+random(3);         {випадкове число}
writeln( ' Якщо натуральне число  n=', n); writeln;            {виведення на екран випадкового числа}
x:=n;     while n>100  do  n:=n div 10; c1:=n div 10;                                             {цикл з передумовою}
writeln('n=', n); end;  c1:=n mod 10; writeln('c1=',c1); writeln('n=',n);    k:=0;                 
repeat       c:= x mod 10;   if c=c1 then k:=k+1;   x:=x div 10;   until x=0;           {цикл з післяумовoю}
writeln('Кількість другої цифри дорівнює:' 
k);  end.
Протестуйте алгоритм  чотири рази та перевірте правильність результатів.









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

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

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




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

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






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

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

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




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

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

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

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




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

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




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

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





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




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

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

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




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

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




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

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

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

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