Проблемне запитання:
Чи можна нелінійний алгоритм замінювати лінійним алгоритмом?
Приклад 1. Дано два дійсні числа а та b. Реалізувати алгоритм для пошуку найбільшого та найменшого числа.
Аналіз проблеми. Математична модель задачі.
Спосіб числової осі.
Число (а+b)/2 - це середнє арифметичне, воно знаходиться точно між числами а та b на числовій осі. До речі (а+b)/2 - це число, яке ділить навпіл довжину відрізка АВ, з кінцями у даних точках А(а) та В(b).
Півдовжини відрізка: 0,5АВ=abs(a-b)
Тому max{a;b} = (а+b)/2 + abs(а-b)/2;
min{a; b} = (а+b)/2 - abs(а-b)/2.
********* лінійний алгоритм мовою Pascal********
program LIN1;
var a, b, max, min: real;
begin
a:=10+random(786);
b:=10+random(796);
max:=(а+b)/2 + abs(а-b)/2;
min:=(а+b)/2 - abs(а-b)/2;
writeln('max=', max, 'min=', min);
end.
*********нелінійний алгоритм Pascal*******
program NOTLIN2;
var a, b: real;
begin
a:=100+random(786);
b:=10000+random(796);
if (a-b)=0 then writeln('max=min=a=b', max)
else
if (a-b)>0 then
writeln(' min=b=', b, 'max=a=', a)
else writeln(' min=a=', a, 'max=b', b);
end.
Приклад 2. Дано натуральне число а. Реалізувати алгоритм знаходження суми усіх натуральних чисел від 1 до а.
Аналіз проблеми:
Математична модель
1+2 + 3 + 4 +...+ (а-2) + (а-1) + а =
= 1 + а +
+ 2 + (а-1) +
+ 3 + (а-2) +
+..... +
+а/2= (а+1)а/2
********* лінійний алгоритм********
program LIN2;
var a, s: real;
begin
a:=10+random(786);
s:=(а+1)*a/2;
writeln('s=', s);
end.
********* нелінійний алгоритм********
program NOTLIN2;
var a, i, s: real;
begin
a:=10+random(786); s:=0;
for i:=1 to a do s:= s+i;
writeln('s=', s);
end.
Приклад 3. Дано натуральне непарне число а. Реалізувати алгоритм знаходження суми усіх непарних чисел від 1 до 2а-1.
Аналіз проблеми:
Математична модель
1+3 + 5 + 7 +...+ (2а-5) + (2а-3) + 2а-1 =
= 1 + 2а -1 +
+ 3 + (2а-3) +
+ 5 + (2а-5) +
+..... +
+а/2= (2а)*а/2=а*а=а2.
********* лінійний алгоритм********
program LIN3;
var a, s: real;
begin
a:=111+2*random(786);
s:=а*a;
writeln('s=', s);
end.
********* нелінійний алгоритм********
program NOTLIN3;
var a, i, s: real;
begin
a:=111+random(786); s:=0;
for i:=1 to a do s:= s+2*i-1;
writeln('s=', s);
end.
Приклад 4. Дано натуральне парне число а. Реалізувати алгоритм знаходження суми усіх парних чисел від 2 до 2а.
Аналіз проблеми:
Математична модель
2+4 + 6 + 8 +...+ (2а-4) + (2а-2) + 2а =
= 2 + 2а +
+ 4 + (2а-2) +
+ 6 + (2а-2) +
+..... +
+2а/2= (2а+2)*а/2=2а*(а+1)/2=а(а+1).
********* лінійний алгоритм********
program LIN3;
var a, s: real;
begin
a:=111+2*random(786);
s:=а*(a+1);
writeln('s=', s);
end.
********* нелінійний алгоритм********
program NOTLIN3;
var a, i, s: real;
begin
a:=222+2*random(786); s:=0;
for i:=1 to a do s:= s+2*i;
writeln('s=', s);
end.
Висновок: можна замінювати нелінійні алгоритми на лінійні алгоритми, якщо аналізувати математичну модель завдання, це скорочує час виконання алгоритму.
Проте не завжди вдається створити математичну модель для завдання. Тому нелінійні алгоритми використовуються частіше, ніж лінійні.
Чи можна нелінійний алгоритм замінювати лінійним алгоритмом?
Приклад 1. Дано два дійсні числа а та b. Реалізувати алгоритм для пошуку найбільшого та найменшого числа.
Аналіз проблеми. Математична модель задачі.
Спосіб числової осі.
Число (а+b)/2 - це середнє арифметичне, воно знаходиться точно між числами а та b на числовій осі. До речі (а+b)/2 - це число, яке ділить навпіл довжину відрізка АВ, з кінцями у даних точках А(а) та В(b).
Півдовжини відрізка: 0,5АВ=abs(a-b)
Тому max{a;b} = (а+b)/2 + abs(а-b)/2;
min{a; b} = (а+b)/2 - abs(а-b)/2.
********* лінійний алгоритм мовою Pascal********
program LIN1;
var a, b, max, min: real;
begin
a:=10+random(786);
b:=10+random(796);
max:=(а+b)/2 + abs(а-b)/2;
min:=(а+b)/2 - abs(а-b)/2;
writeln('max=', max, 'min=', min);
end.
*********нелінійний алгоритм Pascal*******
program NOTLIN2;
var a, b: real;
begin
a:=100+random(786);
b:=10000+random(796);
if (a-b)=0 then writeln('max=min=a=b', max)
else
if (a-b)>0 then
writeln(' min=b=', b, 'max=a=', a)
else writeln(' min=a=', a, 'max=b', b);
end.
Приклад 2. Дано натуральне число а. Реалізувати алгоритм знаходження суми усіх натуральних чисел від 1 до а.
Аналіз проблеми:
Математична модель
1+2 + 3 + 4 +...+ (а-2) + (а-1) + а =
= 1 + а +
+ 2 + (а-1) +
+ 3 + (а-2) +
+..... +
+а/2= (а+1)а/2
********* лінійний алгоритм********
program LIN2;
var a, s: real;
begin
a:=10+random(786);
s:=(а+1)*a/2;
writeln('s=', s);
end.
********* нелінійний алгоритм********
program NOTLIN2;
var a, i, s: real;
begin
a:=10+random(786); s:=0;
for i:=1 to a do s:= s+i;
writeln('s=', s);
end.
Приклад 3. Дано натуральне непарне число а. Реалізувати алгоритм знаходження суми усіх непарних чисел від 1 до 2а-1.
Аналіз проблеми:
Математична модель
1+3 + 5 + 7 +...+ (2а-5) + (2а-3) + 2а-1 =
= 1 + 2а -1 +
+ 3 + (2а-3) +
+ 5 + (2а-5) +
+..... +
+а/2= (2а)*а/2=а*а=а2.
********* лінійний алгоритм********
program LIN3;
var a, s: real;
begin
a:=111+2*random(786);
s:=а*a;
writeln('s=', s);
end.
********* нелінійний алгоритм********
program NOTLIN3;
var a, i, s: real;
begin
a:=111+random(786); s:=0;
for i:=1 to a do s:= s+2*i-1;
writeln('s=', s);
end.
Приклад 4. Дано натуральне парне число а. Реалізувати алгоритм знаходження суми усіх парних чисел від 2 до 2а.
Аналіз проблеми:
Математична модель
2+4 + 6 + 8 +...+ (2а-4) + (2а-2) + 2а =
= 2 + 2а +
+ 4 + (2а-2) +
+ 6 + (2а-2) +
+..... +
+2а/2= (2а+2)*а/2=2а*(а+1)/2=а(а+1).
********* лінійний алгоритм********
program LIN3;
var a, s: real;
begin
a:=111+2*random(786);
s:=а*(a+1);
writeln('s=', s);
end.
********* нелінійний алгоритм********
program NOTLIN3;
var a, i, s: real;
begin
a:=222+2*random(786); s:=0;
for i:=1 to a do s:= s+2*i;
writeln('s=', s);
end.
Висновок: можна замінювати нелінійні алгоритми на лінійні алгоритми, якщо аналізувати математичну модель завдання, це скорочує час виконання алгоритму.
Проте не завжди вдається створити математичну модель для завдання. Тому нелінійні алгоритми використовуються частіше, ніж лінійні.
ПРАКТИЧНА РОБОТА 58.
Алгоритми з вкладеними циклами
та лінійними масивами
Завдання 1. Реалізувати алгоритм для знаходження суми від’ємних елементів в лінійному масиві, що утворюється з випадкових цілих чисел.
Program POSHUK1;
var a: array [1..20] of integer;
s: integer;
i: integer;
begin
writeln ('перелік 20 випадкових цілих елементів масиву:'); s:=0;
for i:=1 to 20 do begin a[i]:=498-random(999);
writeln (i, '-ий елемент масиву = ', a[i]);
if a[i]<0 then s:=s+a[i];
end;
writeln ( 'Сума від’ємних чисел =', s);
end.
Завдання 2. Реалізувати алгоритм для знаходження найбільшого спільного дільника(НСД) для чисел в лінійному масиві, що утворюється з випадкових цілих чисел та знаходження найменшого спільного кратного(НСК) для чисел в лінійному масиві.
Program POZYTYV2;
var a,b,c: array [1..6] of integer;
x,y,i: integer;
function NOD(x, y:integer):integer; {Функція пошуку найб. НСД}
begin if x <> 0 then NOD:=NOD(y mod x, x)
else NOD:=y;
end;
function NOK(x, y:integer):integer; {Функція пошуку наймен. НСК}
begin NOK:=(x div NOD(x, y))*y;
end;
begin {основна програма}
writeln ('перелік 6 випадкових цілих чисел масиву:');
for i:=1 to 6 do begin a[i]:=8*i - 4*random(99); writeln (i, '-е число = ', a[i]); end;
b[1]:=NOD(abs(a[1]), abs(a[2]));
c[1]:=NOK(abs(a[1]), abs(a[2]));
for i:=1 to 5 do begin
b[i+1]:=NOD(b[i], abs(a[i+1])); {Пошук НСД}
c[i+1]:=NOK(c[i], abs(a[i+1]));
writeln('***');
writeln(i, '-ий НСДільник чисел масиву =', b[i]);
writeln(i, '-ий НСKратне чисел масиву =', c[i]);
writeln('***'); end; writeln('НСД усіх чисел =', b[6]);
writeln('НСК усіх чисел =', c[6]);
end.
Завдання 3. Реалізувати алгоритм для знаходження найбільшого числа повторень однакових чисел в лінійному масиві, що утворюється з 20 випадкових цілих чисел.
Program POVTOR3;
var a:array[1..20] of integer;
i,j,m,p,n:integer;
begin
writeln('перелік 20 ВИПАДКОВИХ чисел в массиві А');
for i:=1 to 20 do begin
a[i]:=1-random(4);
writeln (i, '-ий елемент масиву = ', a[i]);
end;
m:=1; p:=1;
for i:=1 to 20 do begin
n:=0;
for j:=1 to 20 do begin
if a[i]=a[j] then inc(n);
end;
if n>m then begin
m:=n; p:=i;
end;
end;
writeln('найповторюване число в масиві:',a[p]);
writeln('кількість числа: ',a[p], ' =', m ); end.
Завдання 4. Реалізувати алгоритм для знаходження відповіді на питання: чи повторюються числа в лінійному масиві, що утворюється з 40 випадкових цілих чисел?
Program ALGORUTM4;
var a: array [1..40] of integer;
i, j: integer;
begin
writeln ( 'перелік 40 елементів масиву');
for i:=1 to 40 do begin a[i]:=i-random(999);
writeln (i, '-ий елемент масиву = ', a[i]); end;
for i:=1 to 40 do begin
for j:=i+1 to 40 do begin
if a[i]=a[j] then begin
writeln ( 'в масиві є однакові елементи= ',a[i], ' зокрема це ', i, '-ий та ', j,'-ий елементи');
halt;
end;
end;
end;
writeln ( 'усі елементи масиву різні');
end.
Завдання для самостійного опрацювання.
Завдання 5. Реалізувати алгоритм для знаходження відповіді на питання: чи є парні числа в лінійному масиві, що утворюється з 50 випадкових цілих чисел?
Завдання 6. Реалізувати алгоритм для знаходження відповіді на питання: чи є непарні числа в лінійному масиві, що утворюється з 60 випадкових цілих чисел?
Завдання 7. Реалізувати алгоритм для знаходження відповіді на питання: чи є круглі числа в лінійному масиві, що утворюється з 50 випадкових цілих чисел?
Завдання 8. Реалізувати алгоритм для знаходження відповіді на питання: чи є нульові числа в лінійному масиві, що утворюється з 60 випадкових цілих чисел?
Сайти для навчання програмуванню
Code.org – електронне середовища для навчання програмуванню початківців
Code School - Практичні завдання для
навчання програмуванню.
Codecacademy – інтерактивне навчання програмуванню.
Stuk.io - Навчання з нуля для майбутніх програмістів.
Udaccity – курси від Google, Facebook та інших великих компаній.
Platzi – курси по дизайну,
маркетингу, програмуванню.
Learnable - курси веб-розробці.
Code School - Практичні завдання для
навчання програмуванню.
Code.org – середовища навчання програмуванню для початківців
BasePails - Навчання Рубі та Раілз та іншим веб-технологіям
Treehouse - Розробка
на HTML, CSS, та додатків на ІОS.
One Month –
навчання основам створення веб-додатків за місяць.
Dash – створення
веб-сайтів.
Немає коментарів:
Дописати коментар