07.02.2022-13.02.2022
Тема: Базові
алгоритмічні структури. Поняття процедури
Теоретична частина
Базові
алгоритмічні структури
Запитання: Які є структури нелінійних
алгоритмів?
Відповідь. Нелінійні алгоритми поділяються
на такі:
1) циклічні алгоритми
( цикли з лічильником, цикли з передумовою, цикли з післяумовою);
2) алгоритми розгалужень(умовний вибір; загальний
вибір).
Запитання: Що таке процедура в алгоритмі?
Відповідь. Процедура
(англ. subroutine) - це частина програми, яка реалізує певний алгоритм і
дозволяє звернення до неї з різних частин загальної (головної) програми. В
термінах мов програмування: функції (С), процедури (Pascal), методи (в
термінології об'єктно-орієнтованого програмування в мовах Python3, C++, Java, С# та ін.).
Запитання: Що таке рекурсивна процедура в
алгоритмі?
Відповідь. Процедура рекурсивна - це процедура в програмуванні, у тілі якої знаходиться явне
звернення до неї самої, або через іншу процедуру.
Застосування
рекурсивних процедур, у багатьох випадках допомагає скоротити алгоритми,
зробити їхню форму компактнішою.
Три
правила рекурсії:
1) Рекурсія повинна мати базовий
випадок( m=1, m=2, m=3, m=4, … m=k-1,
m=k,….);
2) Рекурсія повинна містити зміну стану
та можливість переходу до базового випадку;
3) Рекурсія повинна викликати саму себе.
Підпрограма часто використовується для
скорочення розмірів програм в тих задачах, в процесі розв'язання яких необхідно
виконати декілька разів однаковий алгоритм при різних значеннях параметрів.
Інструкції (оператори, команди), які реалізують відповідну підпрограму,
записують один раз, а в необхідних місцях розміщують інструкцію виклику
підпрограми.
Набір найвживаніших підпрограм утворює бібліотеку стандартних підпрограм.
В більшості мов програмування високого
рівня, підпрограми називаються процедурами та функціями. В залежності від мови
програмування, терміни «процедура» та «функція» можуть розрізнятися (як
правило, процедурою називають підпрограму, що не повертає результату, тоді як
функція має результат і може використовуватись як частина виразу) чи
розглядатись як синоніми (зокрема, в мові C, де в початковому варіанті всі
підпрограми могли повертати результат, їх здебільшого називають функціями). У
об'єктно-орієнтованому програмуванні функції-члени класів називають методами.
Класифікація алгоритмів
в компетентнісних
завданнях
з теми «Алгоритми та
програмування»
Під
час розв’язування компетентнісних задачах з інформатики створюються,
реалізуються, тестуються та найчастіше використовуються:
· алгоритми форматування(редагування)
об’єктів за даними параметрами;
· алгоритми
переміщення(розміщення) об’єктів за даними параметрами;
· алгоритми
видалення(приховування) об’єктів за даними параметрами;
· алгоритми перевірки
властивостей об’єктів за даними параметрами;
· алгоритми зміни або
заміни властивостей об’єктів за даними параметрами;
· обчислювальні алгоритми:
алгоритми-калькулятори;
· алгоритми пошуку
об’єктів за даними параметрами;.
· алгоритми фільтрування змінних
величин у лінійному масиві;
· алгоритми
(створення)генерування об’єктів: алгоритми-генератори;
· алгоритми перестановки та
впорядкування числових та символьних величин.
В
ході розв’язування компетентнісних задач з інформатики на початкових
етапах розв’язування проводиться аналіз властивостей об’єктів та даних умови
для того, щоб використати уміння та навички під час реалізації різних видів
алгоритмів, а саме створюються:
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.
Завдання 4. Самостійно реалізувати та протестувати цей рекурсивний алгоритм мовою
програмування.
Фронтальне
опитування
1.
Яке
походження терміна «алгоритм»?
2.
Що
ми розуміємо під поняттям «алгоритм»?
3.
Що
таке допустимі команди виконавця?
4.
Які
є способи опису алгоритмів?
5.
Які
властивості повинен мати алгоритм?
6.
Що
означає скінченність (дискретність) алгоритму?
7.
Що
таке формальність алгоритму?
8.
Що
означає масовість алгоритму?
Приклад
5. Рекурсивний алгоритм сортування лінійного масиву чисел з процедурою. Реалізувати і протестувати алгоритм сортування
мовою Паскаль лінійного масиву на 10 цілих чисел.
Реалізація
мовою програмування Pascal
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.
Зразки рекурсивних алгоритмів
мовою програмування Python3
Приклад 1. Створити
та реалізувати алгоритм мовою програмування
Python3 відоповідно до зразка у середовищі Thonny.
Реалізація 1. Процедура в алгоритмі виділена синім кольором
print("Нерекусивний алгоритм з
процедурою для знаходження степеня")
def stepin(base, exp):
res=1
for i in range(exp):
res=res*base
return res
k=6
n=2
b=stepin(k, n)
print("результат степеня",k,"^",n,"=", b)
Реалізація 2.
print("Рекурсивний алгоритм з процедурою для знаходження степеня")
def stepin(base, exp):
if exp==0:
return 1
elif
exp<0:
return
float(stepin(base,exp+1)/base)
else:
return
stepin(base,exp-1)*base
k=2
n=-2
b=stepin(k, n)
print("Результат степеня:",k,"^",n,"=", b)
Практична частина
Середовище програмування. Основна
мова програмування, яка використовується при вивченні даної теми 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. Створити та
реалізувати алгоритми мовою програмування
Python3 відоповідно до зразка у середовищі Thonny.
Відкрити в браузері онлайн-Python3 https://www.programiz.com/python-programming/online-compiler/
І виконати програми, що записані в завданнях.
Реалізація
1.
import random
print("Рекурсивний
алгоритм")
print("Друкування чисел")
def druk(a):
if
a==chyslo:
return
(a)
else:
print(a)
return(druk (a+1))
chyslo=random.randint(1,7)
print(druk(1))
Реалізація
2.
import random
print("Рекурсивний алгоритм")
print("Сумування цифр числа")
def suma(a):
if a==0:
return
(a)
else:
return
(a%10+suma(a//10))
n=random.randint(300,999)
print("Число:", n,"Cума:", suma(n))
Завдання 2. Створити та реалізувати алгоритми мовою
програмування Python3
відоповідно до зразка у середовищі Thonny.
Відкрити в браузері онлайн-Python3 https://www.programiz.com/python-programming/online-compiler/
І виконати програми, що записані в завданнях.
Реалізація
1.
import random
print("Рекурсивний алгоритм")
print("Факторіал числа")
def factorial(n):
if
(n==1)or(n==0):
return 1
else:
return
n*factorial(n-1)
n=random.randint(0,50)
print(n,"!=",factorial(n))
Реалізація
2.
import random
print("Рекурсивний алгоритм")
print("Cуми чисел від 1 до n ")
def sum(n):
if (n==1):
return 1
else:
return
n+sum(n-1)
n=random.randint(0,60)
print("Cума від 1 до", n,"=",sum(n))
Завдання 3. Реалізувати
поданні нижче способи створення списків
Відкрити в браузері онлайн-Python3 https://www.programiz.com/python-programming/online-compiler/
І виконати програми, що записані в завданнях.
1)
Перерахуванням всіх елементів (цей спосіб був розглянутий вище):
print('Алгоритм 1 створення елементів
списку перерахуванням
всіх елементів ' )
a =
[ "Андрій", "Віра", "Даша", "Коля",
"Юра"];
print(a)
Можна створити порожній список:
print('Алгоритм 2 створення порожнього списку, списку із нулів,
списку слів ' )
n=20; a=[]*n;
print('a=',a,
'type(a)=',type(a))
m=5;
b=['None']*m
print('b=',b,
'type(b)=',type(b))
m=10; c=[0]*m
print('c=',c,
'type(c)=',type(b))
a = [i for i
in range (10)]; print(a)
2)
За допомогою генератора випадкових чисел для списку:
print('Алгоритм 3 генерування чисел
випадковим чином або формулою ' )
import random
n=20; a=[]*n;
b=[]*n; c=[]*n;
a=[-3*random.randint(-20,-2)
for i in range(n) if i%3==0];
b=[-3*random.randint(-10,0)
+1 for i in range(n) if i%3==1];
c=[-3*i*i-6*i+2
for i in range(n) if i%3==2];
print('Генерування списку випадкових чисел -3*random.randint(-20,-2), тому a=',a, 'type(a)=',type(a))
print('Генерування списку
випадкових чисел -3*random.randint(-10,0) +1, тому b=',b, 'type(b)=',type(b))
print('Генерування списку формулою m[i]=3*i*i-6*i+2, тоді c=',c, 'type(c)=',type(b))
3)
Шляхом введення елементів з клавіатури (кожен елемент з нового рядка):
print('Алгоритм 4 введення чисел
з клавіатури' )
A=[0]*2;
B=[[0,0]]*2
print('Уведіть
числа для списку з клавіатури:')
for i in
range(2):
print("A[", i,"] =", end=" ")
A[i]=int(input())
print('Ви
створили такий список A=',A)
print('Ви
створили такий одновимірний масив розміром 1х2 із цілих чисел A=',A)
B=[A,A]
print('Ви
використали список А і створили новий список B=',B)
print('Ви
створили такий двовимірний масив 2х2 із цілих чисел B=',B)
print('Перший
спосіб виведення елементів двовимірного масиву В')
print("B[",
0,",",0,"] =", A[0], " B[",
0,",",1,"] =", A[1])
print("B[",
0,",",1,"] =", A[0], " B[",
1,",",1,"] =", A[1])
print('Другий
спосіб виведення елементів двовимірного масиву В')
for i in
range(2):
for j in range(2):
print("B[", i,",",j,"] =", B[i][j],
end=" ")
Запустіть
цю програму і створіть список, ввіши самостійно числа з клавіатури.
4) Шляхом введення елементів з клавіатури
(всі елементи в одному рядку через пропуск). Для цього використовується метод
a.split (), який повертає список рядків, які вийдуть, якщо вихідну рядок
розрізати на частини по прогалин:
print('Алгоритм
5 введення трьох чисел з клавіатури в один рядок з одним пропуском ' )
S=input() # користувач
вводить в рядок
три числа із одним пропуском між ними "1 2 3"
D=S.split()
print('Ви
створили такий список D=',D, type(D))
print('Ви
створили такий одновимірний масив розміром 1х2 із цілих чисел D=',D)
Завдання 4. Реалізувати
поданні нижче способи вивеведення списків
Cпособи
виведення списку
Списки
можна виводити різними способами.
1) Найпростіший спосіб -
просто дати команду вивести список:
print('Алгоритм
6’); b = [17, 409, 88]; print(b)
2)
Виведення кожного елемента списку по-окремо:
print('Алгоритм 7’);
a = [ "Андрій",
"Віра", "Даша", "Коля", "Юра"]
for i in range
(5):
print (a [i])
3)
Виведення кожного елемента списку по-окремо в одному рядку:
print('Алгоритм 8’);
a = [ "Андрій",
"Віра", "Даша", "Коля", "Юра"]
for i in range
(5):
print (a [i], end = " ")
4)
Виведення елементів списку без звернення до індексів елементів:
print('Алгоритм 9’);
fruits = [ "Яблуко",
"Банан", "Груша"]
for x in
fruits:
print (x, end = " ")
Завдання 5. Реалізувати
поданні нижче способи опрацювання списків
Опрацювання списків різними способами
зміни його елементів списку
Реалізація
алгоритму каскадного обміну
місцем розташування елементів у списку
print('Алгоритм 10 обміну місцями розташування між сусідніми
елементами в списку')
a=["Андрій", "Віра", "Даша",
"Коля", "Юра"];
print('Початкове розташування елементів у списку a=',
a)
for i in range (0,4):
a[i], a[i+1]=a[i+1], a[i]
print('a[',i,']=',a[i])
print('a[',i+1,']=',a[i+1])
print('Остаточне розташування елементів у списку
a=',a)
Реалізація алгоритму
заміни деяких елементів у списку
print('Алгоритм
11 заміни парних елементів в
списку на число нуль')
q=[1,
2, 3, 4, 5, 6]
print('Початкове
розташування елементів у
списку q=',
q)
for i in range
(6):
if q[i]%2==0:
q[i]=0
print('Остаточне
розташування елементів у
зміненому списку q=',q)
3)
Можна додавати елементи в кінець списку. Для цього використовується метод
a.append (x):
print('Алгоритм
12 дописування в кінець списку елементів в списку')
f=[1,
2, 3, 4, 5, 6]
print('Початкове
розташування елементів у
списку f=',
f)
for k in
range(7):
f.append(100+k+1)
print('Остаточне
розташування елементів у
зміненому списку f=',f)
4)
Чи можна розширювати список, додаючи в його кінець елементи іншого списку. Для
цього використовується метод a.extend(b):
print('Алгоритм
13 дописування в кінець списку елементів іншого
списку)
a=[1,
2, 3, 4, 5, 6]; b=[100,
200, 300];
print('Початкове
розташування елементів у
списку a=',
a)
print('Початкове
розташування елементів у
списку b=',
b)
for k in range(2):
a.extend(b); print('номер ітерації в циклі k=',k,'доповнений список а=',a)
b.extend(a); print('номер ітерації в циклі
k=',k,'доповнений
список b=',b)
print('Остаточне
розташування елементів у
зміненому списку a=',a)
print('Остаточне
розташування елементів у
зміненому списку b=',b)
5)
Списки можна копіювати:
print('Алгоритм 14 копіювання списку'
)
a=[1, 2, 3, 4, 5, 6]; c=b=[100, 200, 300];
print('Початкове розташування елементів у списку a=',
a)
print('Початкове розташування елементів у списку
с=b=', b)
for k in range(1):
a1=a
b1=c
print('Остаточне розташування елементів у скопійованому
списку a1=а=',a1)
print('Остаточне розташування елементів у
скопійованому списку b1=c=',b1)
5)
Функція знаходження довжини списку len (a):
print('Алгоритм 15 пошуку кількості елементів у списку' )
a=["Яблуко",
"Банан", "Груша"]
print('Початкове
розташування елементів у
списку a=',
a)
k=len(a)
print
('Кількість елементів списку k=len(a)=',k)
6)
Заповнення списку випадковими елементами із
різних числових проміжків:
print('Алгоритм 16 заповнення списку випадковими
числовими елементами' )
from random
import randint
x=7
a=[0]*(2*x+3);
print('Початкове
розташування елементів у
списку a=',
a)
for i in
range(x):
a[i]=randint(10,100)
print('Перше
тимчасове розташування елементів у списку a=', a)
for m in
range(x,2*x):
a[m]=randint(1000,100000)
print('Друге
тимчасове розташування елементів у списку a=', a)
for m in
range(2*x,2*x+2):
a[m]=randint(1,10)
print('Остаточне
розташування елементів у
списку a=',
a)
k=len(a)
print
('Кількість елементів списку k=len(a)=',k)
7)
Перестановка елементів списку в зворотному порядку. Метод a.reverse():
print('Алгоритм 17 заповнення списку випадковими
відємними елементами та зворотного запису спику' )
from random
import randint
y=3;
a=[0]*(2*y+5);
print('Початкове
розташування нульових
елементів у списку a=', a)
a=[2*randint(10,100)
for n in range(0, 2*y+5,1)]
print('Початкове
розташування випадкових
парних елементів у списку a=', a)
a=[2*randint(-100,-1)-1
for n in range(1, 2*y+5,3)]
print('Перше
тимчасове розташування непарних
відємних елементів у списку a=', a)
a.reverse()
print('Зворотне розташування елементів у списку a=', a)
k=len(a)
print
('Кількість елементів списку k=len(a)=',k)
8)
Сортування списку. Функція sorted(a):
print('Алгоритм 18 сортування елементів списку випадковими
відємними елементами у порядку спадання та зростання' )
from random
import randint
z=3;
a=[0]*(7*z+5);
print('Початкове
розташування нульових елементів у списку a=', a)
a=[2*randint(1,10)
for n in range(0, 4*z+1,1)]
print('Початкове
розташування випадкових парних елементів у списку a=', a)
a=[2*randint(-10,-1)-1
for n in range(1, 5*z+3, 3)]
print('Перше
тимчасове розташування непарних відємних елементів у списку a=', a)
sorted(a)
print('Упорядковане
розташування елементів у списку за ознакою зростання a=',
a)
a.reverse()
print('Упорядковане
розташування елементів у списку за ознакою спадання a=', a)
k=len(a)
print
('Кількість елементів списку k=len(a)=',k)
print ('Максимальний
елемент у
списку v= max(a)=',max(a))
print ('Мінімальний елемент у списку w= min(a)=',min(a))
print ('Сума усіх елементів у списку h= sum(a)=',sum(a))
print ('Середнє арифметичне
елементів у списку p= sum(a)/k=',sum(a)/k)
Завдання 6. Задача Jump2022 Жабенята роду Пепе дуже
вправні в математиці, а тому представляють надзвичайний інтерес для науковців.
Нещодавно вчені виявили, що якщо розмістити жабеня у якусь з клітинок на
смужці, і у кожній клітинці написати число, жабеня може стрибати вперед
чи назад, а стрибок може мати максимальну довжину у таку кількість
клітинок, яка написана на поточній. Більше того, жабенята достатньо
розумні, щоб знайти маршрут, навіть якщо він достатньо складний. Тепер, знаючи
числа, що написані на смужці, науковцям цікаво, чи існує маршрут з першої
клітини на останню за даних умов.
Технічні
умови Програма
jump2022 читає з пристрою стандартного виведення ціле число T (1 ≤ T ≤ 5) -
кількість смужок.
Далі
йдуть рівно T рядків, у кожному спершу ціле число N (1
≤ N ≤105 ) - довжина смужки, а далі
рівно N цілих невід’ємних чисел, кожне з яких не перевищує 105 - числа, що записані на
смужці. Програма виводить рядок з T літер “Y” та “N”,
де i-та літера позначає відповідь для i-тої смужки (Y, якщо існує
маршрут, N, якщо маршруту немає).
Приклад
|
Ввведення |
Виведення |
Коментар |
|
2 7 3 2 1 0 1 2 3 7 3 5 1 0 3 0 0 |
NY |
У першому випадку перестрибнути клітинку
№4 не вийде, а щойно жабеня потрапить у неї, вистрибнути воно вже не зможе. У другому випадку маршрут жабеняти може
виглядати, наприклад, як 1 -> 3 -> 2 -> 5 -> 7 (зверніть увагу, що жабеня може стрибати
назад) |
Реалізація мовою програмування Python3
import
enum
print('Введіть
кількість смужечок')
T
= int(input())
for
_ in range(T):
print('Введіть поточну смужечку перше число
- це кількість чисел у смужечці, а потім ці числа')
a = list(map(int, input().split()))[1:-1]
maxPos = 0
res = True
for i, jump in enumerate(a):
maxPos = max(maxPos, i + jump)
if maxPos == i:
res = False
break
print('Y' if res else 'N', end='')
Реалізація мовою програмування Pascal
var t,n,k,l,a,p,i,j:longint;
o:string;
begin
o:='';
readln(t);
for i:=1 to t do
begin
read(n); if n=1 then o:=o+'Y'
else
begin
read(a); k:=a+1; p:=1;
for j:=2 to n do
begin
read(a);
if k>=j then
begin
l:=a+j;
if l>k then
k:=l;
end
else p:=0;
end;
if
p=1 then o:=o+'Y' else o:=o+'N';
end;
end;
write(o);
end.
Реалізація мовою програмування C++
#include<iostream>
using namespace std;
int main(){
int
t;
cin
>> t;
for(int i = 0; i < t; i++){
int n;
cin >> n;
int a;
int maxPos = 0;
bool res = true;
for(int i = 1; i < n; i++){
cin >> a;
maxPos = max(maxPos, i + a);
if(maxPos == i){
res = false;
}
}
cin >> a;
if(res){
cout << 'Y';
}
else {
cout << 'N';
}
}
}
Результати виконання практичної частини
надіслати на електронну скриньку: 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 різних клітинкових фігурок?
Відповідь: а)так; зробіть це самостійно і поставте їх
номер б) ні.
Немає коментарів:
Дописати коментар