неділя, 18 березня 2018 р.

Сортування чисел методом «Бульбашкою»


Практична робота 24.   Сортування  чисел  методом «Бульбашкою»
Завдання 1.Реалізувати алгоритм сортування методом «Бульбашкою», що використовує чотири допоміжні процедури та функції.
program sorting;                                         { назва  алгоритму }
const maxcnt=5;                                        { назва  постійної довжини масиву  чисел}
type vector=array[1..maxcnt] of real;           {назва динамічного масиву із дійсних чисел  }
var cmpcnt,swpcnt:  integer;                        {назва змінних величин:  цілих чисел }
     trace:  boolean;                                     {назва змінних величин:  логічних (так/ні) }
procedure writevector(n: integer; m: vector);  {допоміжна процедура друкування масиву}
var i: integer;                                                 {назва змінних величин:  цілих чисел }
begin      writeln('   це m[1]  елемент відсортованого рядка' , m[1]:6:2);   {цикл друку}
  for i:=2 to n do writeln('  це m[', i, '] -ий елемент відсортованого рядка ', m[i]:6:2);
  writeln;  end;                           {закінчення процедури друкування елементів масиву }
function   less(a, b: real): boolean;                {допоміжна функція порівняння елементів}
begin       cmpcnt:=cmpcnt+1;                  { неповне розгалуження для  порівняння чисел }        
  If  trace   then  writeln('Порівняння', a:6:2, ' з ', b:6:2);   less:=a<b;  end;
   procedure swap(var a,b:real);                       {допоміжна процедура - обмін елементів }
var c:real;                                              {назва змінних величин:  дійсних  чисел }
begin        swpcnt:=swpcnt+1;      c:=a; a:=b; b:=c    end;  {виконується   обмін елементів }
procedure bubble(n: integer; var m: vector);      {процедура  сортування  - "Бульбашка" }
var i,j:integer;                                                     {назва змінних величин:  цілих чисел }
begin
  for i:=n-1 downto 1 do                   {цикл з лічильником від більшого до меншого }
    for j:=1 to i do                         {вкладений цикл з лічильником від меншого до більшого }
   if less(m[j+1],m[j]) then begin    { неповне розгалуження з використанням  логік-функції}
            swap(m[j],m[j+1]);       {використання процедури обміну елементами }
            if   trace   then    writevector(n,m)  end;  end;  { процедура  друку елементів }
{Основний алгоритм, який використовує допоміжні алгоритми}
var    n,i: integer;                {назва змінних величин:  цілих  чисел }
          m: vector;                    {назва змінних величин:  масиву  чисел }
         ans: char;                     {назва змінних величин:  буквених символів }
begin
  repeat                               {цикл з післяумовою  для введення довжини масиву   }
    write('Введено розмір масиву(від 1 до ', maxcnt, '): ');
    n:=1+random(5);   writeln('n=', n);      {випадкове  ціле чисел – це довжина масиву}
  until (1<=n) and (n<=maxcnt);                {Умова перевірки закінчення циклу}
  writeln('Введено масив випадкових чисел:');
  for i:=1 to n do  begin              {цикл з лічильником  для введення елементів масиву }
    m[i]:=2+random(159);  writeln('Введено  випадковe число:', m[i]);
  writeln;   end;                  {цикл з лічильником  для виведення елементів масиву }
  write('Показати процес роботи? (y/N) '); readln(ans);            {діалог з користувачем}
   trace:=(ans='y')or(ans='Y');
  writeln('Обрано метод сортування "Бульбашка":');        cmpcnt:=0; swpcnt:=0;
   bubble(n,m);               {виклик процедури сортування «бульбашкою» чисел }
  writeln('Всього виконано ', cmpcnt, ' порівнянь та ', swpcnt, ' перестановок');
  writeln(' Відсортований масив в порядку зростання:');    writevector(n,m);   end.

Алгоритми підрахунку розфарбуваних об’єктів


Практична робота 22.  Алгоритми  створення   розфарбуваних об’єктів

Завдання 1.  Петрик П’яточкін вишикував  у рядок слоненят та рахує їх по кожному кольору окремо. Всього буває 8 кольорів слоненят. У рядок вишикувались N (N>10) слоненят. Скільки слоненят кожного кольору стоїть перед Петриком? Створити алгоритм для підрахунку слоненят кожного кольору окремо, пройшовши всього один раз перед строєм. Кольори позначити цифрами від 1 до 8.
Program   SLON1;
const k=1000;
var a: array[1..k]  of  integer;       b: array[1..k] of  integer;      i, c, n, m: integer;
begin       n:=1+random(12);       writeln('кількість усіх слонів n=', n,' ');  
 writeln('Повна  послідовність  пофарбованих слонів  ');
 for i:=1 to n  do  begin   a[i]:=1+random(8); writeln(i,'ий слон  має колір:   ', a[i],' '); end; writeln;
 for c:=1 to 8 do    b[c]:=0;  writeln(' Кількість слонів  за  однаковим  кольором  ');
 for i:=1 to n do     b[a[i]]:=b[a[i]]+1;
 for i:=1 to 8 do    writeln(i, '-ий колір має:  ', b[i], '   слонів');  end.
Протестувати алгоритм декілька разів.

Завдання 2.  Вінні Пух любить складати віршики говорячи речення задом наперед. Якось йому попалось довге складне речення і він забув свій віршик, пробуючи його виговорити. Складіть програму, яка б допомагала ведмедику легко складати такі віршики. Зауваження: віршик може складатись як із 1 слова, так і з декількох, розділених пропусками. В кінці віршика ніколи не ставиться крапка. Довжина віршика менша за 255 символів.
Program   VINNI2;
var a,b: string;        i,n: integer;
begin    readln(a);    n:=length(a);  b:='  '; 
for  i:=n downto 1 do    b:=b+a[i];
 writeln ('Це твір-перевертень ВІННІ ПУХА: ',  b);  end.
Протестувати алгоритм декілька разів ввівши свій вірш в програму.

Завдання 3.  Кіт Леопольд пішов на рибалку та наловив риби. Кожну рибу він старанно зважив. Перша риба (найменша), яку він зважував важила рівно L грам. Кожна наступна рибина була на К грамів важча за попередню. Скільки заважила вся риба, яку наловив Леопольд, якщо відомо, що спіймав він N (N>0) риб?
Program   LEOPOLD3;
var    i, n, L, k, s, t :integer;
begin     n:=2+random(12);       writeln('кількість усіх риб  n=', n,'   ');     
L:=2+random(12);       writeln('вага найменшої рибини  L=', L,'  грам ');        
k:=3+random(12); writeln(' найменша різниця між вагою двох риб k=', k, '  грам');
 s:=0; t:=l;
 for i:=1 to n do   begin       s:=s+t;      t:=t+k;    end;     writeln (s);   end.
Протестувати алгоритм декілька разів.


Алгоритми створення квадратичної функції


Практична робота 20. «Алгоритми створення квадратичної функції за трьома відомими точками мовою Pascal»
Завдання 1. Створити алгоритм який за трьома відомими точками в прямокутній  системі координат генерує формулу квадратичної функції використовуючи розв’язання  системи 3-х рівнянь з трьома невідомими методом Крамера. Ця задача називається «інтерполяція квадратичними поліномами» або знаходження «квадратичного тренду».
Розв’язання.  Випадковим чином задаються три точки деякої статистики:  (х1; у1), (х2; у2), (х3; у3). Вважається, що ці три точки належать деякій параболі,  що записується  формулою вигляду: у=ах2+bx+c.  Підставляємо кожну точку у формулу і отримуємо систему трьох рівнянь з трьома невідомими а, b, c. 
{| aх1*х1 + bх1 + c * 1 = y1 | }
{| aх2*х2 + bх2 + c * 1 = y2 }
{| aх3*х3 + bх3 + c * 1 = y1 }
Розв’язуємо систему відносно  а, b, c  за допомогою метода визначників (метод Крамера).
Program  Interpoljacia;
var a1, a2, a3, b1, b2, b3, c1, c2, c3, d1, d2, d3, x, y, z, e, ex, ey, ez, x1, x2, x3, y1, y2, y3: real;
begin
x1:=-(1+random(3)) *(-2+random(1)) *(-random(2)) + 1+random(3) ; 
y1:=-(1+random(3)) *(-2+random(1)) *(-random(2)) + 2+random(3) ;   
writeln( ' Якщо перша точка, що належить квадратичній функції х1=', x1, 'y1=', y1); writeln;
x2:=-(1+random(3)) *(-2+random(1)) *(-random(2)) + 1+random(3) ; 
y2:=-(1+random(3)) *(-2+random(1)) *(-random(2)) + 3+random(3) ;   
writeln( ' Якщо друга точка, що належить квадратичній функції х2=', x2, 'y2=', y2); writeln;
x3:=-(1+random(3)) *(-2+random(1)) *(-random(2)) + 1+random(3) ; 
y3:=-(1+random(3)) *(-2+random(1)) *(-random(2)) + 4+random(3) ;   
writeln( ' Якщо третя точка, що належить квадратичній функції х3=', x3, 'y3=', y3); writeln;
a1:= x1*x1;    a2:= x2*x2;  a3:= x3*x3;   b1:= x1;    b2:= x2;  b3:= x3;  c1:=1;    c2:=1;  c3:=1;
d1:=y1;   d2:=y2;  d3:=y3;
 e:= (a1 * b2 * c3 + b1 * c2 * a3 + c1 * a2 * b3-a3 * b2 * c1-b3 * c2 * a1-c3 * a2 * b1);
 ex:=(d1 * b2 * c3 + b1 * c2 * d3 + c1 * d2 * b3-d3 * b2 * c1-b3 * c2 * d1-c3 * d2 * b1);
 ey:=(a1 * d2 * c3 + d1 * c2 * a3 + c1 * a2 * d3-a3 * d2 * c1-d3 * c2 * a1-c3 * a2 * d1);
 ez:=(a1 * b2 * d3 + b1 * d2 * a3 + d1 * a2 * b3-a3 * b2 * d1-b3 * d2 * a1-d3 * a2 * b1);
 if (e=0) and ((ex=0) or (ey=0) or (ez=0)) then
    writeln ( 'безліч рішень')
 else if (e <> 0) and ((ex = 0) or (ey = 0) or (ez = 0)) then
    writeln ( 'немає рішень')
 else begin
    x:=ex/e;     y:=ey/e;     z:=ez/e;
writeln ( 'Головний визначник е =', e);writeln ( 'a =', x); writeln ( 'b =', y); writeln ( 'c =', z);
writeln( ' Шукана квадратична функція  у=', x,  '*x*x+( ' ,  y,  ' )x+( ',  z,  ' ) ');  end; end.
Протестуйте правильність виконання алгоритму.

Алгоритми табуляції перестановок



Практична робота 19
«Алгоритми табуляції  перестановок на мові Pascal»

Завдання 1. Скласти і реалізувати алгоритм  для    табулювання значень  перестановок натуральних чисел. Наприклад:  Перестановки для трьох чисел:  123   132   213   231   321  312(усього шість).

Program Perestanovka1;                               { оголошення назви алгоритму }
const n=5;                                                  { оголошення  константи, кількість чисел в  перестановці }
var a: array [1..n] of integer;                       { оголошення масиву цілих чисел  для запису  перестановок }
      index: integer;                                                { оголошення  цілої змінної для кодування чисел в перестановках}
procedure generate (l, r: integer);                 { оголошення підпрограми генератора перестановок }
var i, v: integer;                                           { оголошення змінних цілих чисел  для  алгоритму }
begin
      if (l = r) then begin                                                { оголошення перевірки рівності двох індексів }
        for i:=1 to n do write (a [i], '');        { оголошення циклу з лічильником  для виведення  перестановок }
        writeln;
      end    else    begin                                  
        for i:=l to r do begin            { оголошення циклу з лічильником  для генерації  перестановок }
           v:=a[l]; a[l]:=a[i]; a[i]:=v;                      {Обмін a[i], a[j]}
           generate (l + 1, r);                         {Виклик нової генерації перестановок - це рекурсія в алгоритмі}
           v:=a[l]; a[l]:=a[i]; a[i]:=v;                    {Обмін a [i], a [j]}
        end;        end;    end; 
begin
      for  index:=1  to  N  do  a[index]:=index;    { цикл  з лічильником  для генерації  перестановок }
      generate(1, n);     end.    {виклик  процедури  для генерації  перестановок }
Протестуйте алгоритм  чотири рази  тобто треба  змінити число табуляції: 1)соnst=3; 2) соnst=4;  3) соnst=6.

Завдання 2. Скласти і реалізувати алгоритм  для знаходження   табулювання значень кубічної функції, що задана рекурсивною формулою у=((а1х+а2)х+а3)х+a4.
program  Cubesfunction;                     {назва    алгоритму  табуляції}
var  a1, a2, a3, a4,  x, y, d: real;      i, k: integer;     {оголошення  змінних величин: дійсні числа та цілі числа}
begin           { початок   виконання алгоритму і введення випадкових коефіцієнтів  кубічної функції}
 a1:=1+random(3);  writeln( ' Якщо cтарший коефіцієнт кубічної функції a1=', a1); writeln;
a2:=2+random(7);  writeln(' Якщо квадратичний коефіцієнт кубічної функції a2=', a2); writeln;
a3:=-(4+random(10));  writeln(' Якщо лінійний коефіцієнт кубічної функції a3=', a3); writeln;
a4:=-(3+random(10));  writeln(' Якщо вільний коефіцієнт кубічної функції a4=', a4); writeln;
x:=-(1+random(20));  writeln(' Якщо початковий аргумент кубічної функції x=', x); writeln;
d:=1+random(3);  writeln( ' Якщо величина кроку табуляції  кубічної функції d=', d); writeln;
k:=15+random(5);  writeln( ' Якщо кількість кроків табуляції k=', k); writeln;
for i:=1 to k do begin       {виконання циклу з лічильником по kрокам для обчислення  значень функції}
x:=x+(i-1)*d;    y:=((a1*x+a2)*x+a3)+a4;       { виведення результатів табулювання на  екран монітора}
writeln( ' номер кроку табуляції  i=', i,  ' аргумент функції  х=', x, ' значення функції  y=', y); writeln; end; writeln('********'); end.   {закінчення алгоритму}
Протестуйте алгоритм  чотири рази та порівняйте результати табуляції і виберіть той варіант, при якому можна знайти найточніше наближення   нулів кубічної функції, тобто випадок ((a1*x+a2)*x+a3)*x+a4=0.