вівторок, 26 лютого 2019 р.

Нелінійні та лінійні алгоритми


Проблемне запитання:
Чи можна нелінійний алгоритм замінювати лінійним алгоритмом?
Приклад 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.
*********нелінійний алгоритм*******
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.
Приклад 3. Дано натуральне парне число а. Реалізувати алгоритм знаходження суми усіх парних чисел від 2 до 2а.
Аналіз проблеми: Математична модель
2+4 + 6 + 8 +...+ (2а-4) + (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. Масиви
Масив - однорідна упорядкована статична структура прямого доступу. Масив можна назвати a сукупністю фіксованого числа однакових компонентів, кожна з яких забезпечується індексом. Для того щоб описати масив, необхідно задати тип компонента і тип індексу. 
var <ідентифікатор>: array [тип індексу] of <тип компонент>;
Найчастіше в якості типу індексу вживається інтервальний тип, може бути і перераховується тип, а також будь-яким скалярним порядковим типом.
Приклад оголошення масиву:
var mass : array [1..10] of real ; {приклад опису одновимірного масиву}
var a : array [1..15, 1..4] of integer ; {приклад опису двовимірного масиву}
Всі завдання можна умовно уявити з декількох основних блоків:
  • блок введення значень елементів масиву (формування елементів масиву випадковим чином);
  • блок виведення вихідного масиву;
  • блок обробки масиву;
  • блок виведення результатів обробки.
Найбільш часто використовувані масиви при вирішенні завдань: одномірні, двовимірні.



Алгоритми вибору мовою програмування Pascal

Загальна форма запису:
case <селектор (логічний вираз, математичний вираз, змінна)> of
значення1 : оператор;
значення2 : оператор;
. . . . . . . . . .
значенняN : оператор
else оператор;
end;
В операторі може бути кілька дій, тобто використовуватися begin, end, а може бути порожній оператор. Значень може бути кілька.
Завдання 1.
З клавіатури вводиться цифра. Вивести письмову назву цієї цифри.
Розв’язання.
Кодування мовою програмування Pascal:
program Z1;
var
  a : integer;
begin
  write('введіть цифру: ');
  readln(a);
      case a of
        0 : writeln ('ви ввели нуль.');
        1 : writeln ('ви ввели одиницю.');
        2 : writeln ('ви ввели двійку.');
       3 : writeln ('ви ввели трійку.');
       4 : writeln ('ви ввели четвірку.');
       5 : writeln ('ви ввели пятірку.');
       6 : writeln ('ви ввели шістку.');
       7 : writeln ('ви ввели сімку.');
       8 : writeln ('ви ввели вісімку.');
        9 : writeln ('ви ввели цифру девять.')
        else writeln('ви ввели не цифру.');
      end;
end.
Задача 2.
Складіть програму, яка імітує своєрідний калькулятор, де 1-сума двох чисел, 2-різницю двох чисел, 3-твір двох чисел, 4-ціла частина від ділення, 5-залишок від ділення, 6 - квадратний корінь числа, інакше введений невідомий номер операції .
Розв’язання.
Кодування мовою програмування Pascal:
program Z2;
var
  a, b: real;
  i, c, d: integer;

begin
  writeln('Калькулятор.');
  writeln('1 - сума двох чисел;');
  writeln('2 - різниця двох чисел;');
  writeln('3 - добуток двох чисел;');
  writeln('4 - ціла частина від ділення;');
  writeln('5 - остача від ділення;');
  writeln('6 - квадратний корінь числа.');
  write('Введіть цифру: ');
  readln(i);
  case i of
    1:
      begin
        write('Введіть три довільні числа: ');
        read(a, b, c);
        writeln(1*a+1*b+1*c);
      end;
    2:
      begin
        write(' Введіть два довільні числа: ');
        read(a, b);
        writeln(1*- 1*b);
      end;
    3:
      begin
        write(' Введіть два довільні числа: ');
        read(a, b);
        writeln(1** b);
      end;
    4:
      begin
        write(' Введіть два довільні числа: ');
        read(c, d);
        writeln(c div d);
      end;
    5:
      begin
        write(' Введіть два довільні числа: ');
        read(c, d);
        writeln(c mod d);
      end;
    6:
      begin
        write('Введіть число: ');
        read(c); 
writeln(sqrt(c):4:5);
      end;
  else writeln('Помилка.');
  end;
end.


Задачі Case
1.     Дано ціле число, що визначає оцінку. Вивести опис оцінки (1-3: погано, 4-6: задовільно, 7-9: добре, 10-12: відмінно, інші випадки: помилка)
2.     Написати програму, яка вводить два цілих числа та виводить таке меню:
Введіть номер завдання:
1 – знаходження суми чисел;
2 – знаходження модулю різниці чисел;
3 – знаходження добутку чисел;

3. Програма повинна виконати завдання, номер якого буде введено
Написати програму, яка вводить радіус та виводить таке меню:
Введіть номер завдання:
1 – обчислення довжини кола
(L=2*3.1415926*R);
2 – обчислення площі круга
(S=3.1415926*R*R);
3 – обчислення об’єму сфери
(V=(4/3)* 3.1415926*R*R*R).
Програма повинна виконати завдання, номер якого буде введено
.
4.     Мастям гральних карт присвоєні номери: 1 — піки, 2 — трефи, 3 — бубни, 4 — черви. Значенням карт, що старші десятки, присвоєно номери: 11 — валет, 12 — дама, 13 — король, 14 — туз. Дано два цілих числа: N — значення (6 <= N <= 14) та M — масть карти (1<= M <= 4). Вивести назву карти у вигляді «шістка бубн», «дама чирв», «туз треф» та ін.
5.     Дано ціле число від 280 до 299. Вивести рядок – письмово запис назви цього числа. Наприклад, 256 – двісті п’ятдесят шість (11 балів)

Немає коментарів:

Дописати коментар