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

Проблемне запитання:

Чи можна нелінійний алгоритм замінювати лінійним алгоритмом?

Приклад 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=а*а=а².

********* лінійний алгоритм********

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 + 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*a - 1*b);

      end;

    3:

      begin

        write(' Введіть два довільні числа: ');

        read(a, b);

        writeln(1*a * 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 балів)