14.02.2022-20.02.2022 Етапи розвязування задач з програмування

 

14.02.2022-20.02.2022

Тема: Етапи розвязування задач з програмування

 

Теоретична частина

 

Властивості алгоритмів

 

Алгоритм – це скінчена однозначно визначена послідовність операцій(команд, вказівок), формальне виконання яких приводить до розв’язання певної задачі на кінцеве число кроків.

Виконавець алгоритму – це жив чи нежива істота, яка може виконати всі вказівки заданого алгоритму.

Припустимі команди – це команди, які можуть бути виконані виконавцем.

Неприпустимі команди – це команди, які не можуть бути виконані виконавцем.
Система команд виконавця – це сукупність припустимих команд.

 

Властивості алгоритмів

 

Дискретність – це означає  процес розв’язування задачі, який складається з окремих кроків або подій. Алгоритм складається із сукупності відокремлених одна від одної команд(вказівок), кожна з яких виконується за скінчений час. Тільки закінчивши виконання однієї команди, виконавець переходить до виконання другої команди.

Визначеність(однозначність) - це означає, що кожна команда алгоритму одназначно визначає дії виконавця і не припускає подвійного тлумачення. Суворо визначеним є й порядок виконання операцій.

Формальність – це означає, що будь-який виконавець, який володіє заданою системою команд виконавця, може виконати даний алгоритм, не вдаючись до суті цієї задачі.

Масовість – це означає, що алгоритм передбачає можливість зміни початкових даних або вхідних даних у деяких припустимих межах(універсальність алгоритму.

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

 

Базові структури алгоритмів

 

Базові структури алгоритмів – це структури, за допомогою яких створюється алгоритм для розв’язання певної задачі.

Основна особливість базових структур алгоритмів – це їх повнота, тобто цих структур достатньо для створення найскладнішого алгоритму.

Лінійний алгоритм – це послідовне виконання усіх команд один лише раз.

Розгалужений алгоритм – це перевірка умови і вибір певної операцій із заданої множини операцій.

Циклічний алгоритм – це повторення певної кількості команд декілька раз.

 

Способи запису алгоритмів

 

Словесний спосіб - це письмова форма запису команд природньою мовою.

Формульно-словесний спосіб – це мова математичних формул, мова хімічних процесів, навчальна алгоритмічна мова.

Графічний спосіб – це спосіб запису команд у вигляді блок-схем, структур.

Програмний спосіб – це запис алгоритму мовою програмування.

 

 

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

1.              Яке походження терміна «алгоритм»?

2.              Що ми розуміємо під поняттям «алгоритм»?

3.              Що таке допустимі команди виконавця?

4.              Які є способи опису алгоритмів?

5.              Які властивості повинен мати алгоритм?

6.              Що означає скінченність (дискретність) алгоритму?

7.              Що таке формальність алгоритму?

8.              Що означає масовість алгоритму?

 

Парадигми програмування

 

·         Агентно-орієнтована

·         Компонентно-орієнтована

·         Конкатенативна

·         Декларативна (контрастує з Імперативною)

·         Обмеженнями

·         Функційна

·         Потоком даних

·         Таблично-орієнтована (електронні таблиці)

·         Реактивна

·         Логічна

·         Подійно-орієнтована

·         Сервісно-орієнтована

·         Комбінаторна

·         Імперативна (контрастує з декларативною)

·         Процедурна

·         Предметно-орієнтована

·         Метапрограмування

·         Автоматизація процесу програмування

·         Узагальнене програмування

·         Шаблонне

·         Рефлексивно-орієнтована

·         Ітераційна

·         Паралельна

·         Структурна

·         Модульна

·         Рекурсивна

·         Об'єктно-орієнтована

·         Автоматна

·         Поділ відповідальності:

·         Аспектно-орієнтована

·         Суб'єктно-орієнтована

·         Прототип-орієнтована

 

 

 

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

 

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

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.  Алгоритм з ітераційною функцією без рекурсії;

 

 

Практична частина

 

 

Середовище програмування. Основна мова програмування, яка використовується при вивченні даної теми Python гілки 3, або його ще називають Python3. В залежності від наявних у вас пристроїв, можна обрати своє середовище (програму для написання програм). Налаштувати ваші пристрої для роботи допоможе підручник (опрацюйте п.7 підручника ст.61 -65 до вправи 3). Для користувачів OS Windows, бажано встановити Середовище Thonny, оскільки робота в ньому непогано описана в нашому підручнику.

Середовище Thonny Python IDE for beginners https://thonny.org/

Для завантаження можна прямо перейти за посиланням

Для Windows: https://github.com/thonny/thonny/releases/download/v3.3.2/thonny-3.3.2.exe

 

Завдання 1.  Створити, реалізувати, протестувати алгоритм мовою програмування Python у середовищі програмуванняThonny, який за даним списком цілих чисел виводить:
1) змінює у списку окремі елементи на інші; 2) найбільше число у списку; 3)найменше число у списку; 4) суму елементів, що мають парний номер в розташуванні; 5) суму елементів, що мають непарний номер в розташуванні; 6) суму лише парних елементів  у списку; 7) суму  лише непарних елементів  у списку.
Реалізація.

print('  *********ОПЕРАЦІЇ НАД елементами списків, що містять  різні цілі числа *******  ')

lst3=[16,27,38,92,73,94,10]     # оголошується в список lst3 з числами

print('lst1=', lst1)     #виводиться на екран cписок

lst3[0]=-18; lst3[1]=-29;  lst3[6]=-95;  # оголошується в списку заміна деяких елементів  на інші

print('lst3=', lst3)                    #виводиться на екран cписок

print('max(lst3)= ', max(lst3))   #виводиться на екран найбільший елемент в списку

print('min(lst3)= ',  min(lst3))    #виводиться на екран найменший елемент списку

print('Aлгоритм сумування елементів, що мають парний номер в розташуванні ')   

lst4=[161,274,386,924,738,942,104]     # оголошується в список lst1 з числами

s=0

for k in range(0, 7,2):   #цикл з лічильником від 0 до 7 з кроком 2(для парних номерів)

      s=s+lst4[k]           #сумування елементів списку, що мають парний номер

print('Сума елементів списку lst4, що мають парний номер =', s)  #виводиться сума

print('Aлгоритм сумування елементів, що мають непарний номер в розташуванні ')   

lst1=[61,74,86,24,38,42,34]     # оголошується в список lst1 з числами

d=0

for m in range(1, 7,2):   #цикл з лічильником від 1 до 7 з кроком 2(для непарних номерів)

      d=d+lst1[m]           # сумування елементів списку, що мають непарний номер     

print('Сума елементів списку lst1, що мають непарний номер =', d)  #виводиться сума

print('Aлгоритм сумування лише парних елементів  у списку')

lst5=[621,734,886,294,378,421,354]     # оголошується в список lst1 з числами

с=0

for n in range(0, 7,1):   #цикл з лічильником від 1 до 7 з кроком 2(для усіх елементів )

      if lst5[n]%2==0:        #перевірка елемента списку на парність

             с=с+lst5[n]           # сумування елементів списку,  що є парним числом    

print('Сума лише парних елементів списку lst1 =', с)  #виводиться на екран сума

print('Aлгоритм сумування лише непарних елементів  у списку')

lst2=[661,784,816,284,368,412,347]     # оголошується в список lst1 з числами

h=0

for n in range(0, 7,1):   #цикл з лічильником від 1 до 7 з кроком 2(для усіх елементів )

      if lst2[n]%2==1:        #перевірка елемента списку на парність

            h=h+lst2[n]           # сумування елементів списку, що є непарним числом

print('Сума лише непарних елементів списку lst2 =', h)  #виводиться на екран сума

print('Aлгоритм сумування лише елементів, що кратні 2 і 3  у списку')

lst6=[663,786,816,284,368,412,347]     # оголошується в список lst1 з числами

h=0

for n in range(0, 7,1):   #цикл з лічильником від 1 до 7 з кроком 2(для усіх елементів )

      if lst6[n]%6==0:        #перевірка елемента списку на парність

            h=h+lst6[n]           # сумування елементів списку, що є числом, яке кратне 6

print('Сума лише непарних елементів списку lst6 =', h)  #виводиться на екран сума

Протестувати алгоритм для  випадку: 1) lst2=[19, 28, 37, 46, 55, 64, 71]    

2) lst3=[13, 23, 33, 43, 53, 63, 73]    3) lst1=[-12, -23, -34, -45, -56, -67, -78] 

4) lst4=[134, 232, 331, 437, 535, 632, 736]    5) lst5=[-172, -283, -394, -465, -536, -617, -78]          

 6) 5) lst6=[-1752, -2283, -3994, -4365, -5136, -6517, -778       

 

Завдання 2.  Створити, реалізувати, протестувати алгоритм мовою програмування Python у середовищі програмуванняThonny, який за даним списком дробових  чисел виводить:
1) змінює у списку окремі елементи на інші; 2) найбільше число у списку; 3)найменше число у списку; 4) середнє арифметичне найбільшого та найменшого чисел у списку; 5) суму лише  елементів, що мають непарний номер і додатні; 6) суму лише додатних елементів  у списку; 7) суму  лише від’ємних елементів  у списку.
Реалізація.
print(' *********ОПЕРАЦІЇ НАД елементами списків, що містять дробові числа*******  ')

lst2=[-4.758, -5.804, 6.23,2.5,-8,4,6.8,-7.25]      # оголошується список lst2, який має посилання на список із трьох чисел

lst2[0]=-23.05       # оголошується в списку заміна нульового елемента на  число -20.05

lst2[1]=19.36       # оголошується в списку заміна першого елемента на число -18.35

lst2[2]=-11.57                           # оголошується в списку заміна другого елемента на число -10.55

MIN=min(lst2); MAX=max(lst2);  middle=(MIN+MAX)/2    # пошук та рахунок в списку MAX, MIN, middle

print('Список дробових чисел lst2=', lst2)                                                    #виводиться на екран cписок

print('Найменше число у списку min(lst2)= ',  MIN)                                     #виводиться на екран найменше число

print('Найбільше число у списку max(lst2)= ',  MAX)                                   #виводиться на екран найбільше число

print('Середнє арифметичне найбільшого та найменшого чисел middle(lst2)= ' ,middle)     # на екран cередина cписку

lst3=[1.6,2.7,-3.8,9.2,7.3,-9.4,-1.01]     # оголошується в список lst3 з числами

s=0

for k in range(0, 7,2):   #цикл з лічильником від 0 до 7 з кроком 2(для парних номерів)

    if k%3==0:        #перевірка елемента списку на подільність трьом

       s=s+lst3[k]           #сумування елементів списку, що мають парний номер

print('Сума елементів списку lst3, що мають парний номер =', s)  #виводиться сума

print('Aлгоритм сумування додатних елементів ')   

lst1=[6.1,7.4,-8.6,2.4,3.8,4.2,-3.4]    

d=0

for m in range(1, 7,2):   #цикл з лічильником від 1 до 7 з кроком 2(для непарних номерів)

     if lst1[m]>0:        #перевірка елемента списку на парність

       d=d+lst1[m]           # сумування елементів списку, що мають непарний номер    

print('Сума додатних елементів списку lst1, що мають непарний номер =', d)  #виводиться сума

print('Aлгоритм сумування відємних елементів  у списку')

lst2=[67.12,78.43,8.62,2.42,-34.82,4.22,3.47]    

с=0

for n in range(0, 7,1):   #цикл з лічильником від 1 до 7 з кроком 2(для усіх елементів )

      if lst2[n]<0:        #перевірка елемента списку на парність

             с=с+lst2[n]           # сумування елементів списку,  що є парним числом    

print('Сума лише відємних елементів списку lst2=', с)  #виводиться на екран сума

print('Aлгоритм сумування лише елементів  у списку, що в межах від -5 до 5')

h=0

for n in range(0, 7,1):   #цикл з лічильником від 1 до 7 з кроком 2(для усіх елементів )

    if (lst2[n]<5)and(lst2[n]>-5) :        #перевірка елемента списку на парність

            h=h+lst2[n]           # сумування елементів списку, що є непарним числом

print('Сума лише  елементів для заданого проміжку із списку lst2 =', h)  #виводиться на екран сума

     
 Протестувати алгоритм для випадку:  1) lst2=[1.8, 2.3, -3.5, 4.6, -5.9, 6.9, -7.1]

2) lst1=[1.1, 2.1, 3.1, 4.1, 5.1, 6.1, 7.1]    3) lst3=[-1.2, -2.3, -3.4, -4.5, -5.6, -6.7, -7.8]          

 

   Завдання 3.  Створити, реалізувати, протестувати алгоритм мовою програмування Python у середовищі програмуванняThonny, який за двома введеними цілими, однаковознаковими,  різнопарними числами r  та t  виводить:
3) послідовність чисел  вигляду  (6*(r-i)+7*(t+i) )//(t-r+i), де і- ціле число;            

Реалізація.
print('Третій циклічний алгоритм утворення числової послідовності')  

print('Введіть число r =')       # виведення  повідомлення на монітор

r =int(input())                            # введення з клавіатури числа r

print('Введіть число t =')        # виведення  повідомлення на монітор

t=int(input())                             # введення з клавіатури числа t

for i in range(10, -14, -9):    # команда повторення від 10 до -14 з кроком -9

     y=(6*(r-i)+7*(t+i) )//(t-r+i)             # присвоєння змінній у  частки двох чисел

     print(i,'-e число (4*(r-i)+2*(t+i) )//(t-r+i)=', y)   # виведення  результату на монітор

Протестувати алгоритм для трьох випадків: 1)r= -7; t= - 4;  2) t= 5; r = 4; 3) r= -67; t= -12.

 

 

 

 

 

Завдання 4. Реалізувати нелінійні алгоритми з повторення мовою програмування Python3  в середовищі Thonny відповідно до зразку:

Реалізація.

print("це алгоритм суми зростаючої послідовності чисел до 101: цикл 1 з передумовою")

b=1

g=0

while b<89:

          b=2*b+1

          g=3*g+b

          print("b=", b, " Результат: g=", g)

else:

       print("вихід із циклу")

print("це алгоритм суми спадної послідовності чисел до 0: цикл 2 з передумовою")

c=100

p=0

while c>-1:

          c=4*c-20

          p=5*p+2*c

          print("c=", c, " Результат: P=", p)

else:

        print("вихід із циклу")

 

Завдання 5. Реалізувати нелінійні алгоритми з повторення мовою програмування Python3  в середовищі Thonny відповідно до зразку:

Реалізація.

print("це алгоритм пошуку деякихрозвязків рівняння: 7a+2b=14")

s=0

k=0

for i in range(-20,20,1):

      for j in range(-20,20,1):

            s=7*i+2*j

            if s==14:

                print("Це розвязок рівняння: 7a+2b=14 ", "a=",i,"b=", j)

                k=k+1

print("Це кількість знайдених розвязок рівняння: k= ", k)

Протестуйте для рівнянь:  1) a+b=4;       2)  -2a+b=8;      3) -2a-8b=-18;  

 

 

Завдання 6. Реалізувати нелінійні алгоритми з повторення мовою програмування Python3  в середовищі Thonny відповідно до зразку:

Реалізація.

print("це алгоритм пошуку окремих розвязків рівняння: 8a+2b+6c=80")

s=0

k=0

for i in range(-10,10):

      for j in range(-10,10):

             for m in range(-10,10):

                    s=8*i+2*j+6*m

                   if s==80:

                       print("Це розвязок рівняння: 8a+2b+6c=80: ", "a=",i,"b=", j,"c=", m)

                       k=k+1

print("Це кількість знайдених розвязок рівняння: k= ", k)

Протестуйте для рівнянь:  1) a+b+c=4;       2)  -2a+b+4c=8;      3) -2a+b+4c=8.

 

 

 

 

Результати виконання практичної частини надіслати на електронну скриньку: vinnser@gmail.com

 

************************

Завдання на розвиток кмітливості

 

 

Означення клітинкової фігури:  Фігурка називається клітинковою, якщо вона складається з квадратиків розміром 1х1, кожен квадрати 1х1 має спільну сторону з неменше ніж одним квадратиком 1х1.

Одноклітинковий квадратик 1х1 вважають клітинковою фігуркою.

Зауваження. Два квадратики 1х1 не будуть клітинковими фігурками, якщо вони мають тільки одну спільну вершину.

Одноклітинкова та двоклітинкова фігурки це відповідно квадратик 1х1 та прямокутник 1х2.  Це фігурки під номерами 1 та 2.                                                            

Триклітинкових  фігурок всього є двох видів. Це фігурки під номерами 3 та 4.                                                            

 

	3				4			1		2
	5
					6				7
	8			9

Дослідити види 4-клітинкові та 5-клітинкові фігурок. 

Чотириклітинкових фігурок є п’ять видів. Це фігурки під номерами 5, 6, 7, 8, 9.

П’ятиклітинкових фігурок всього є 12 видів. Це фігурки під номерами 10, 11, 12, …, 21.

10						11					12			16
13			14					15
												20
17				18						19
							16
		21

 

 

Завдання:

1. Чи можна розрізати клітинковий квадрат 5х5 на різні 5 клітинкові фігурки?

Відповідь: так. Зробіть це самостійно і поставте їх номер

2. Яку найбільшу кількість клітинкових фігурок можна помістити в квадрат 5х5?

Відповідь: вісім.  Зробіть це самостійно і поставте їх номер

3. Яку найбільшу кількість клітинкових фігурок можна помістити в квадрат 4х4?

Відповідь: п’ять. Зробіть це самостійно і поставте їх номер

4. Чи можна розрізати клітинковий квадрат 4х4 на: а) усі різні 4-клітинкові фігурки; б) рівні 4-клітинкові фігурки?

Відповідь: а) ні, бо усі різні;б)так, для двох видів. Зробіть це самостійно і поставте їх номер

6. Яку найбільшу кількість 5-клітинкових фігурок можна помістити в квадрат 4х4?

Відповідь: три.  Зробіть це самостійно і поставте їх номер

7. Чи можна розрізати клітинковий квадрат 100х100 на: а) Т-подібні 4-клітинкові фігурки?

Відповідь: так. Зробіть це самостійно і поставте їх номер

8. Складіть таблицю 6-клітинкових фігурок.. Скільки видів таких фігурок?

9. Розмістіть найбільшу кількість 5-клітинкових кутиків у квадраті 5х5?

Відповідь: чотири. Зробіть це самостійно і поставте їх номер

10. Чи можна розрізати клітинковий квадрат 4х4 на: а) 5 різних клітинкових фігурок б) 6 різних клітинкових фігурок?

Відповідь: а)так; зробіть це самостійно і поставте їх номер  б) ні.