9 клас. Інформатика. Дистанційне навчання: Дистанційна освіта з інформатики 17.05.2021-22.09.2021

Дистанційна освіта з інформатики за травень 2021 року

в період

17.05.2021-22.09.2021

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

Створення та аналіз математичної моделі квадратних рівнянь з параметром для "коректного" опрацювання в алгоритмі пошуку коренів із відомими властивостями.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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. Рекурсивний алгоритм сортування лінійного масиву чисел з процедурою

Завдання. Реалізувати і протестувати алгоритм сортування мовою Паскаль лінійного масиву на 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.

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

Задача 1. Випадковим чином задається двомірний масив(цe таблиця чисeл) , що складається із nxn елементів, якщо n менше 100. Вивести масив на екран у вигляді таблиці чисел та знайти суму елементів, що розташовані на обох діагоналях масиву. Вивести одномірними масивами елементи окрeмо верхнього і окрeмо нижнього трикутника матриці без головної діагоналі знайти суму елементів верхнього трикутника та сума елементів нижнього трикутника квадратної матриці nxn.

Розв′язання.

Реалізація алгоритму мовою програмування Pascal:

Program Summa_trukutnuk_matriza;

const m=4; n=4;

var sum,f,s, d, c:real; b:array[1..m*n] of real;

xn:array[1..m*n] of real; xv:array[1..m*n] of real; a:array[1..m,1..n] of real;

i,j,p, g, k:integer;

begin

writeln(' Ввeдіть кількість рядків квадратного масиву, яка мeншe 100 ');

readln(k); s:=0;

for i:=1 to k do

for j:=1 to k do begin

a[i,j]:=int(random*20-10);

b[(i-1)*k+j]:=a[i,j]; end; writeln(' ');

writeln(' Масив випадкових чисeл: '); writeln(' ');

for i:=1 to k do begin

for j:=1 to k do begin write(' a[',i,';',j,']:= ',a[i,j] {' b[',i-1*k+j,']= ',b[(i-1)*k+j]});

end; writeln(' '); end;

s:=0; for i:=1 to k do begin s:=s+a[i,i]; end;

f:=0; for i:=1 to k do begin f:=f+a[i,k+1-i]; end;

if k mod 2 =1 then sum:=s+f- a[k div 2 +1, k div 2 +1] else sum:=s+f;

p:=1; g:=1; for i:=1 to k do begin

for j:=k downto 1 do begin

if i<j then begin

xv[g]:= a[i,j]; g:=g+1; end; end; end;

for i:=1 to k do begin

for j:=1 to i-1 do begin

if i>j then begin

xn[p]:= a[i,j]; p:= p+1; end; end; end;

writeln(' Масив чисeл нижнього трикутника матриці : ');

d:=0; for i:=1 to ((k-1)*k) div 2 do begin d:=d+ xn[i];

write(' xn[',i,']= ', xn[i]); end; writeln(' ');

writeln(' Масив чисeл вeрхнього трикутника матриці : ');

c:=0; for i:=1 to ((k-1)*k) div 2 do begin

c:=c+ xv[i]; write(' xv[', i, ']= ', xv[i]); end; writeln(' ');

writeln(' Сума чисел головної діагоналі матриці:', s); writeln(' ');

writeln(' Сума чисел бічної діагоналі матриці :', f); writeln(' ');

writeln(' Сума чисел на обох діагоналях: ', sum); writeln(' ');

writeln(' Сума чисел верхнього трикутника матриці ' , c); writeln(' ');

writeln(' Сума чисел нижнього трикутника матриці ' , d); writeln(' '); end.

Протестувати декілька разів програму.

Тест1. m=8; n=8;

Тест2. m=9; n=9;

Тест3. m=12; n=12;

Результати тестування надішліть на електронну адресу учителя.

Завдання 2. Створити та реалізувати алгоритми розв′язування систем лінійних рівнянь.

Метод Крамера.

Розв′язування систем лінійних рівнянь з двома невідомими (х; у).

|a1*x + b1*y = c1

|a2*x+b2*y=c1

Метод визначників:

     |c1 b1|           |a1 c1|

     |c2 b2|           |a2 c2|

 x = ---------     y = ---------

      |a1 b1|           |a1 b1|

      |a2 b2|           |a2 b2|

Обчислюємо визначники квадратних матриць 2х2:

x = (c1*b2-c2*b1)/(a1*b2-a2*b1)

y = (a1*c2-a2*c1)/(a1*b2-a2*b1)

Алгоритм Крамера мовою Pascal:

Program KRAMER;

const m=40; n=50; k=60;

var a1,a2,b1,b2,c1,c2,x,y,d,dx,dy:real;

begin

writeln('Випадкові коефіцієнти двох рівнянь: a1,b1,c1,a2,b2,c2');

a1:=random(m); a2:=random(m);

writeln('a1 = ', a1); writeln('a2 = ', a2);

b1:=random(n); b2:=random(n);

writeln('b1 = ', b1); writeln('b2 = ', b2);

c1:=random(k); c2:=random(k);

writeln('c1 = ', c1); writeln('c2 = ', c2);

{readln(a1,b1,c1,a2,b2,c2);}

writeln('Система двох лінійних рівнянь: ');

writeln(a1,'*x+',b1,'*y=',c1); writeln(a2,'*x+',b2,'*y=',c2);

d := (a1*b2-a2*b1);

dx := (c1*b2-c2*b1);

dy := (a1*c2-a2*c1);

if ( d=0 ) and ( (dx=0) or (dy=0) ) then

writeln('Безліч розв′язків у системи')

else if ( d<>0 ) and ( (dx=0) or (dy=0) ) then

writeln(' Немає розв′язків у системи')

else begin writeln('Єдиний розв′язок у системи');

x:=dx/d; y:=dy/d;

writeln('x = ', x); writeln('y = ', y);

end;

end.

Задача А3. Скласти програму розв’язання квадратного рівняння.

Розв’язання :

В загальному вигляді квадратне рівняння має вигляд:

ax² + bx + c = 0

Згадаймо, як ми його розв’язуємо на уроках математики і точно так само розв’яжемо на мові програмування з тією відмінністю, що на уроках математики ви розв’язували конкретне рівняння, а наша програма зможе розв’язати будь–яке квадратне рівняння (на множині дійсних чисел). Всі пояснення в коментарях до програми, але нам хотілося б, щоб ви найбільшу увагу звернули на розміщення і використання команд розгалуження.

Реалізація

program kwur;

label 10,20,30;

var a,b,c,d,x1,x2 : real;

begin

writeln( ‘ Програма розв’’язує квадратнi рiвняння! ’);

writeln(‘ Загальний вигляд квадратного рiвняння: ’);

writeln( ‘ Ax*x + B*x + C = 0 ’);

writeln( ‘ Введiть коефiцiєнти: ’);

10: write( ‘A = ’);readln(a);

if a = 0 then begin

writeln( ‘Цей випадок роз’’вяжiть самi. ’);

goto 10;

end;

20: write( ‘B = ’);readln(b);

if b = 0 then begin

writeln( ‘ Цей випадок розв’’яжiть самi. ’);

goto 20;

end;

30: write( ‘C = ’);readln(c);

if c = 0 then begin

writeln( ‘ Цей випадок розв’’яжiть самi. ’);

goto 30;

end;

d := b*b - 4*a*c;

if d > 0 then begin

writeln( ‘ Рiвняння має два коренi: ’);

x1 := (-b-sqrt(d))/(2*a);

x2 := (-b+sqrt(d))/(2*a);

writeln( ‘x1 = ’,x1:2:2, ‘ x2 = ’,x2:2:2);

end

else if d = 0 then begin

writeln( ‘ Рiвняння має один корiнь: ’);

x1 := -b/(2*a);

writeln( ‘x = ’,x1:2:2);

end

else writeln( ‘ Дане рiвняння коренiв не має. ’);

readln;

end.

Протестувати декілька разів програму.

Тест1. Введення даних з клавіатури

Тест2. Введення даних як випадкових чисел у програмі( треба змінити у програмі коди).

Результати тестування надішліть на електронну адресу учителя.

Детально розібравшись з усіма видами запису команди розгалуження на прикладі щойно приведеної програми ви позбавите себе від неприємних несподіванок у майбутньому.

Задача А4. На площині задано три точки своїми координатами. Чи лежать точки на одній прямій.

Розв’язання: Розв’язок здається напрошується: знайти відстань між всіма трьома точками і якщо сума двох з них дорівнює третій, то точки лежать на одній прямій, в противному випадку – ні. Що ж , перевіряємо:

Реалізація

program pixel3;

var x1,x2,x3,y1,y2,y3 : integer;

d1,d2,d3 : real;

begin

writeln('Координати точки А:');

write('Ха = ');readln(x1);

write('Ya = ');readln(y1);

writeln('Координати точки B:');

write('Хb = ');readln(x1);

write('Yb = ');readln(y1);

writeln('Координати точки C:');

write('Хc = ');readln(x1);

write('Yc = ');readln(y1);

{ Перевірка на підставі описаного вище способу }

d1 := sqrt(sqr(x1-x2)+sqr(y1-y2));

d2 := sqrt(sqr(x1-x3)+sqr(y1-y3));

d3 := sqrt(sqr(x2-x3)+sqr(y3-y3));

if (d1 = d2 + d3) or (d2 = d1 + d3) or (d3 = d1+d2)

then writeln('На однiй прямiй.')

else writeln('Не на однiй прямiй.');

readln

end.

Протестувати декілька разів програму.

Тест1. Введення даних з клавіатури

Тест2. Введення даних як випадкових чисел у програмі( треба змінити у програмі деякі рядки кодів).

Результати тестування надішліть на електронну адресу учителя.

Але давайте подумаємо, чи не можна розв’язати задачу іншим способом? Виявляється можна, для цього потрібно просто пам’ятати рівняння прямої, що проходить через дві точки виражене через координати, яке вивчалось на уроках геометрії. Ви можете сказати: так то через дві точки, а в нас їх аж три! Вірно, тим краще! Чому – спробуйте здогадатись самі і лише після цього приступайте до самостійної реалізації запропонованого способу. Якщо ж ні – то вам пропонується другий варіант розв’язання, детально розібравшись з яким ви, мабуть, вже не забудете рівняння прямої. Отже, спосіб другий:

Реалізація

program pixel3а;

var x1,x2,x3,y1,y2,y3 : integer;

begin

writeln('Координати точки А:');

write('Ха = ');readln(x1);

write('Ya = ');readln(y1);

writeln('Координати точки B:');

write('Хb = ');readln(x2);

write('Yb = ');readln(y2);

writeln('Координати точки C:');

write('Хc = ');readln(x3);

write('Yc = ');readln(y3);

{ Перевірка на підставі рівняння прямої }

if (х1 – х2)*(х3 – х2) – (у1 – у2) * (у3 – у2) = 0

then writeln('На однiй прямiй.')

else writeln('Не на однiй прямiй.');

readln

end.

Протестувати декілька разів програму.

Тест1. Введення даних з клавіатури

Тест2. Введення даних як випадкових чисел у програмі( треба змінити у програмі деякі рядки кодів).

Результати тестування надішліть на електронну адресу учителя.

Зверніть увагу на скільки стало менше змінних і виконуваних операцій. Ідея ж розв’язку полягала в тому, що ми до відомого рівняння прямої застосували правило пропорції і перенесли співмножники в одну сторону, в результаті чого отримали лінійне рівняння з двома невідомими. Після цього замість довільної точки прямої (х,у) підставили значення координат третьої точки. Якщо точка належить прямій, то отримане рівняння повинно дорівнювати нулю.

Дану просту задачу ми привели з однією метою: відмітити той важливий момент, що очевидне не завжди найкраще. Крім того, потрібно завжди дотримуватись правила (і не тільки при програмуванні): рішив поставлену задачу – добре, але пошукай інший спосіб – практично завжди він є! Знайшовши декілька способів розв’язання постав себе перед вибором – а який з них кращий? Ось вам ще одна демонстрація необхідності робити вибір в реальному житті. А якщо дотримуватись цього правила при вирішенні життєвих проблем, то запевняємо – успіх вам гарантовано!

Розглянемо ще одну цікаву задачу, яка також легко розв’язується з застосуванням рівняння прямої.

Задача А5. Два відрізки задано координатами своїх кінців. Визначити, чи перетинаються дані відрізки.

Розв’язання: Згадайте те, про що ми говорили раніше: очевидне не завжди найкраще! А це значить, що нам не потрібно шукати точку перетину відрізків, ми поступимо іншим чином. Будемо розглядати точки кінців одного відрізку відносно іншого відрізку. З геометрії відомо, що два відрізки перетинаються тоді і тільки тоді, коли кінці одного відрізку лежать в різних півплощинах відносно прямої, що проходить через інший відрізок. Причому потрібно розглядати обидва відрізка. Той факт, що дві точки лежать відносно прямої в різних півплощинах можна записати з використанням рівняння прямої таким чином:

Для точок С і D відносно прямої АВ:

((Xc-Xa)(Xb-Xa) - (Yc-Ya)(Yb-Ya))Ч((Xd-Xa)(Xb-Xa) - (Yd-Ya)(Yb-Ya))<0

Для точок A і B відносно прямої CD:

((Xa-Xc)(Xd-Xc) - (Ya-Yc)(Yd-Yc))Ч((Xb-Xc)(Xd-Xc) - (Yb-Yc)(Yd-Yb))<0

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

Реалізація

program line2;

var x1,x2,x3,x4,y1,y2,y3,y4 : integer;

begin

writeln('Координати точки А:');

write('Ха = ');readln(x1);

write('Ya = ');readln(y1);

writeln('Координати точки B:');

write('Хb = ');readln(x2);

write('Yb = ');readln(y2);

writeln('Координати точки C:');

write('Хc = ');readln(x3);