понеділок, 19 березня 2018 р.

Aлгоритми мовою Pascal. Цикли і розгалуження


Практична робота 10 
Програмування циклів мовою Pascal 








Завдання 1. Ліцей проводить вибори до учнівського парламенту. Скількома способами можна обрати цей парламент, якщо до парламенту подано: k заявок від  8-класників, m заявок від 9-класників, n заявок від 10- класників. Скласти і реалізувати алгоритм підрахунку усіх способів утворення шкільного парламенту мовою Pascal, за умови, що серед вибраних є не менше одиного представника із трьох паралелей, і до парламенту проходить тільки небільше половини від ТИХ, ХТО подав заявки. А саме, у парламенті має зайти не більше:  0,5k+1 осіб від  8-класників, небільше 0,5m+1  осіб від 9-класників, не більше 0,5n+1 осіб від 10- класників.
Розв’язання. У парламент може зайти: або один, або два, або три, …., або  0,5k+1 від  8-класників.  Кількість способів, обчислюємо як сума комбінацій: С1k/2+1  +С2k/2+1 +С3k/2+1+…+ +Сk/2k/2+1. Аналогічно знаходимо кількість способів для 9-класників: С1m/2+1  +С2m/2 +1+С3m/2+1+…+ +Сm/2m/2+1. Аналогічно знаходимо кількість способів для 10-класників: С1n/2+1  +С2n/2+1 +С3n/2+1+…+ +Сn/2n/2+1. А кількість вибору того, що у парламенті мають бути представники від трьох паралелей:
     р=(С1k/2+1  +С2k/2+1 +С3k/2+1+…+ Сk/2k/2+1)( С1k/2+1  +С2k/2+1 +С3k/2+1+…+ Сk/2k/2+1)(С1k/2+1  +С2k/2+1 +С3k/2+1+…+ Сk/2k/2+1).
program Parlament;
var i, k, m, n, v1, d1, b1, v2, d2, b2, v3, d3, b3:integer;
begin
  writeln('Введіть число заявок від 8-класників: k= '); readln(k); k:=(k div 2)+1;
  writeln('Введіть число заявок від 9-класників: m= ');  readln(m);  m:=(m div 2)+1;
 writeln('Введіть число заявок від 10-класників: n= ');    readln(n);  n:=(n div 2)+1;
v1:=1; d1:=1; b1:=1; v2:=1; d2:=1; b2:=1; v3:=0; d3:=0; b3:=0;           {початкові значення змінних}
for i:=1 to k do begin   v1:=i*v1;    v2:=(k-i+1)*v2;     v3:=(v2 div v1)+v3; end;      {цикл 8-их класів}
for i:=1 to m do begin d1:=i*d1;   d2:=(m-i+1)*d2; d3:=(d2 div d1)+d3; end;         {цикл 9-их класів}
for i:=1 to n do  begin b1:=i*b1; b2:=(n-i+1)*b2; b3:=(b2 div b1)+b3; end;            {цикл 10-их класів}
writeln('Кількість способів обрати членів парламенту від окремих паралелей:');
writeln(' v3= ', v3, ' способів тільки від 8-класників; ');
writeln(' d3= ',d3, ' способів тільки від 9-класників;');
writeln(' b3= ',b3, '  способів тільки від 10-класників; ');
writeln('Кількість способів обрати новий  учнівський парламент  ліцею;');
  writeln('  p= ', v3*d3*b3, ' способів');    writeln('     '); end.
Протестуйте правильність роботи алгоритму: {k;m;n}={(1;1;1)=1;  (2;2;2)=27;  (3;3;3)=27;  (4;4;4)=343;  (3;4;2)=63}

Завдання 2. Ліцей проводить вибори до Ради учнівського парламенту. Скількома способами можна обрати Раду  парламенту у складі  n осіб, якщо серед кандидатів  k  ліцеїстів та m ліцеїсток. Скласти і реалізувати алгоритм підрахунку усіх можливих способів створення Ради парламенту мовою Pascal. Вхідні дані: k, m, n. Вивід: кількість!
Розв’язання. Нехай кандидатів у Раду парламенту більше, ніж n. У Раду парламента може зайти: або одна, або дві,…., або  m  ліцеїсток.  Кількість способів обрати тільки ліцеїсток обчислюємо як  комбінації: С1m =m(1 місце в раді парламенту); С2m =m(m-1)/2( для двох осіб) ; С3m  ;…  Сmm.  (буває варіант Сnn =1, якщо n=m і в Раді парламенту лише ліцеїстки і немає ліцеїстів).  Аналогічно знаходимо кількість способів для ліцеїстів:
С1 k =k;  С2k =k(k-1)/2; ….., Сk-1k=k-1 (для k-1 ліцеїстів);Сkk=1 (для k ліцеїстів); С0k (для n-1 ліцеїсток і 1 ліцеїстa);
Таким чином, вибір усіх осіб у Раду парламенту за цих умов можна здійснити сумою добутків:
р= С1kСn-1m + С2kСn-2m +  … + Сn-2mС2k + Сn-1mС1k
program RadaParlament; const k1=15; m1=15;    var i,g,j, k, m, n, v1, d1, b1, v2, d2, b2, v3, d3, b3, p:integer;
a, b: array[1..k1*m1] of  integer;   c: array[1..k1,1..m1] of  integer;      begin
writeln('Введіть число заявок від юнаків: k<= ',k1); readln(k);
 writeln('Введіть число заявок від юнаків: m<= ',m1); readln(m);
 writeln('Введіть число  місць у Раді парламенту n<= ', k1*m1); readln(n);
 v1:=1; d1:=1; b1:=1; v2:=1; d2:=1; b2:=1; v3:=0; d3:=0; b3:=0; 
for i:= 1 to k do begin v1:=i*v1; v2:=(k-i+1)*v2; b[i]:= v2 div v1; v3:=b[i]+v3;  end;
 for i:=1 to m do begin d1:=i*d1; d2:=(m-i+1)*d2;a[i]:= d2 div d1; d3:=a[i]+d3;  end;
for i:=1 to k do  begin  for j:=1 to m do begin c[i,j]:=a[j]*b[i];
  writeln('j=',j,' i= ',i,' ', 'c[',i,';',j,']=',a[j]* b[i],'    ');  end; end;
     writeln('  Кількість способів створити Раду парламенту');
 for i:=1 to k do  begin  for j:=1 to m do begin   if  i+j=n then begin b3:=c[i,j]+b3;
  writeln('j=',j,' i= ',i,' ', 'c[',i,';',j,']=',a[j]* b[i],' ');end; end; end;writeln('^^^^^^^^');
writeln(' b3= ',b3, ' способів отримати Раду парламенту.');writeln(' '); end.

Протестуйте правильність роботи алгоритму: {k;m;n}={(5;5;10)=1;  (2;2;2)=4;  (2;2;3)=4;  (4;4;10)=0;  (4;4;5)=56}



Практична робота 9.
Aлгоритми мовою Pascal. Цикли і розгалуження 

Завдання 1. Скласти і реалізувати алгоритм мовою Паскаль, який перевіряє приналежність натурального числа до чисел Фібоначчі, тобто приналежність до ряду чисел, в якому кожне наступне число дорівнює сумі двох попередніх чисел(наприклад:1+1=2; 1+2=3; 2+3=5;  3+5=8 і т.д.).  До ряду чисел Фібоначчі належать: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 
Програма мовою Pascal.
program Fibonacсi;                                                                                                    {Оголошення назви алгоритму}  
var      a,b,c,n: integer;   asc: boolean;                             {Оголошення змінних величин : цілих та : логічних}  
 begin    write('Введіть натуральне число N=');  readln(n);                    {Оголошення про введення числа }  
  a:=0;b:=1;c:=0;                                                                {Оголошення початкових значень для цілих змінних}
  asc:=false;                                                                 {Оголошення початкового значення для логічної  змінної}
  while c<n do begin                                                                      {Оголошення початку циклу з передумовою}
    c:=a+b; a:=b;    b:=c;                             { Сума двох попередніх  змінних і переприсвоєння результатів }  
    if  n=c  then  asc:=true; b:=c;     end;                  { Перевірка критерію  числа Фібоначчі і     кінець циклу}  
    if asc = true then writeln(n,' - це число Фібоначчі')                       {Перевірка і вивід числа Фібоначчі}
  else  writeln(n,' - це не є числом Фібоначчі');  end.           {Перевірка і вивід результату, кінець програми}

Протестуйте правильність роботи цього алгоритму. Введення: 7; 8; 9; 54; 55; 832040.

Завдання 2. Скласти і реалізувати алгоритм мовою Паскаль, який перевіряє, чи  декілька натуральних чисел  являються взаємно простими. Два числа взаємно прості, якщо у них найбільший спільний дільник дорівнює 1. Наприклад: 2 та 3 – це взаємно прості числа; 4 та 8 – це не взаємно прості числа.    Програма мовою Pascal.
    program zysla2;                                                                          {Оголошення назви алгоритму}  
var a: array[1..100] of  integer;               {Оголошення про ряд чисел(числовий масив 1х100) в алгоритмі}  
    i,max,n,j: integer;                                                         {Оголошення про цілі змінні в алгоритмі}  
 begin     write('vvedite koli4estvo 4isel:');   readln(n);   {Оголошення про введення кількості чисел}  
   for i:=1 to n do                                                                      {Оголошення початку циклу з лічильником}
    begin   write(i, ') 4islo:'); readln(a[i]);   end;                 {Оголошення введення даних чисел по порядку}
   max:=a[1];
   for i:=2 to n do if max<a[i] then max:=a[i];       {Оголошення початку циклу з лічильником і перевірка}
   for i:=2 to max do                                                   {Оголошення початку циклу з лічильником}
    for j:=1 to n do                                                       {Оголошення початку циклу з лічильником}
     if a[j] mod i=0 then begin  write('TAK');         {Оголошення перевірки подільності чисел з лічильником}
             readln; end
     else  begin write('NI'); readln; end;            {Оголошення кінця перевірки та циклу з лічильником}
  readln;  end.
Протестуйте правильність роботи алгоритму. Введення:{2; 8; 9}=TAK,  {2; 25; 10}=NI, {3; 7; 14; 35}=NI  

Завдання 3. Скласти і реалізувати алгоритм мовою Паскаль, який перевіряє ряд випадкових натуральних чисел, які при діленні на сім дають остачу 2 та 1 і виводить такі числа на екран.
   Програма мовою Pascal
Program Ostaci;                                               {Оголошення назви алгоритму}  
Const n = 5;                                         {Оголошення про постійну величину:  n  - це кількість чисел в ряді}
Var   x : array [1..n] of Integer;      i : Integer; {Оголошення про ряд чисел(числовий масив) в алгоритмі}  
Begin    
     For i := 1 to n  do    x[i] := random(100);      {Цикл формування ряду випадкових чисел, менше 100} 
     For i := 1 to n do     Write(x[i]:3);  WriteLn; {Оголошення про виведення на екран ряду випадк. чисел}
     For i := 1 to n do                             {Цикл з лічильником для перевірки ряду випадкових чисел на остачі} 
         If (x[i] mod 7 = 2) or (x[i] mod 7 = 1)     {Оголошення про перевірку чисел на остачі на 2 та 1 }  
            then Write(x[i]:3, ' (', i, ') ');        {Оголошення про виведення на екран ряду перевірених  чисел}
             WriteLn; readln;   еnd.
Протестуйте правильність роботи алгоритму. 1) Введення: Const n = 7;   Const n = 19;  Const n = 22;
2)Змінити у програмі перевірку остач: перевірити числа на остачі: 4 та 6,  перевірити на остачі: 0 та 6.
3)Змінити у програмі перевірку подільності на 9: перевірити числа на остачі: 1 та 3,  перевірити на остачі: 0 та 5.




Практична робота 8.  
Програмування циклів мовою Pascal.

Завдання 1. Скласти і реалізувати алгоритм підрахунку різних букв у слові мовою Pascal.
 program Wordlitera;                                  { оголошення назви алгоритму }
var   s:string;        r:real;      i,j,n:integer;  {оголошення змінних величин алгоритму: рядкові, дійсні, цілі}
begin                                                               {оголошення початку  алгоритму }
    r:=0;                                                            {оголошення присвоєння нуля дійсній змінній}
    readln(s);                                                  {оголошення про зчитування з екрану рядкової змінної }
    for i:=1 to length(s) do begin               {оголошення циклу з лічильником  i в алгоритмі}
       n:=0;                                                         { оголошення про присвоєвоння нуля }
       for j:=1 to length(s) do begin                {оголошення циклу з лічильником  j в алгоритмі}
          if s[i]=s[j] then inc(n);                   { оголошення про перевірку на однаковість букв}
       end;                                              { оголошення про кінець циклу }
       r:=r+1/n;                                    {оголошення   лічильника кількості  різних букв} 
  end;      writeln('кількість різних букв у слові  r = ', r:1:0);  end.       { оголошення про кінець циклу, алгоритму }
Протестувати правильність виконання алгоритму: Ввести: карта;  агов; математика; інформатика-а-а.

Завдання 2. Скласти і реалізувати алгоритм знаходження цілих дільників натурального числа мовою Pascal.
program Numer;                                  { оголошення назви алгоритму }
var   a,n,c,d: integer;                          {оголошення змінних величин  a,n,c,d в алгоритмі: цілі}
begin                                                      {початок алгоритму }
    readln(a);                                        {оголошення про зчитування з екрану змінної }
    n:=1;                                                  { оголошення про присвоєвоння  лічильнику  1 }          
    while ( n <= sqrt(a) ) do begin         {оголошення циклу з передумовою(допоки … виконати…)  в алгоритмі}
       c:=a mod n;                                            {оголошення про знаходження остачі від ділення a:n}
       d:=a div n;                                         {оголошення про знаходження цілої частини від ділення a:n}
       if c = 0 then begin  writeln(n);        {Перевірка подільності націло, якщо  остача =0, то написати дільник}
          if n <> d then writeln( d );    {Перевірка неоднаковості дільників, якщо  дільники різні, то написати дільник}
       end;         inc(n);      end;   end.                                            { оголошення про кінець циклу та алгоритму }
Протестувати правильність виконання алгоритму: Ввести чисел: 4;  6; 8; 94;  96; 80; 99; 100; 272; 558; 997

Завдання 3. Скласти і реалізувати алгоритм знаходження простих натуральних чисел мовою Pascal.
Program Prime;
const LIMIT = 50;             {оголошення постійної величини  в алгоритмі: цілі}
var i,j,lim: integer;             {оголошення змінних величин  i, j, lim в алгоритмі: цілі}
begin                                  {початок основної програми  алгоритму}
  writeln;              {початок з нового рядку}
  for i:=1 to LIMIT do begin   {оголошення про початок циклу з лічильником i}   
      j:=2; lim:=round(sqrt(i));                      { оголошення про присвоєвоння  лічильнику  2 }          
      while (i mod j <> 0) and (j <= lim) do inc(j);  {цикл з складеною передумовою}
      if (j > lim) then write( i,' ' );   end;  end.        { перевірка, вивід і оголошення про кінець}
Протестувати правильність виконання алгоритму: Замінити:  LIMIT = 50 на LIMIT = 100; LIMIT = 997.

Завдання 4. Скласти і реалізувати алгоритм знаходження суми цифр натурального числа мовою Pascal.
Program Summa;
var a,x, i,s: integer;
begin
     writeln('введіть ціле число');  readln(a); 
     x:=a;  s:=0;
     while ( x < > 0 ) do begin
       s := s + (x mod 10);
       x := x div 10;       end;
     writeln( 'Сума цифр числа ', a, '  s= ',  s);
end.
Протестувати правильність виконання алгоритму: Ввести чисел: 4;  6; 8; 94;  96; 80; 99; 100; 272; 558; 997
Завдання 5. Самостійно скласти і реалізувати алгоритм знаходження послідовності чисел, що утворюється сумою усіх цифр натурального числа та  додаванням  цієї суми до самого числа мовою Pascal.
Наприклад: А(15 )=1+5+15=26, А(20)=2+0+20=22, А(95 )=9+5+95=109, А(24)=2+4+24=30,   А(111)=1+1+1+111=114. 
Завдання 6. Самостійно скласти і реалізувати алгоритм знаходження послідовності чисел, що утворюється добутком усіх цифр натурального числа та  множенням  цього добутку на саме число мовою Pascal.
Наприклад: А(15 )=1*5*15=75,  А(20)=2*0*20=0,А(95 )=9*5*95=4275,   А(24)=2*4*24=192, А(111)=1*1*111=111. 



Практична робота 7. 
Алгоритми розгалуження

Завдання 1. Cтворити та реалізувати мовою програмування Pascal, що визначає в скількох точках перетинаються два кола за шістьма чисел x1, y1, r1, x2, y2, r2, де x1, y1, x2, y2, - координати центрів кіл, r1, r2 – їх радіуси. Усі числа - дійсні, не перевищують 1000000000 за модулем, та задані не більш ніж із 3 знаками після коми.
Program Circus01;
var x1,y1,r1,x2,y2,r2, d:real;
begin
readln (x1, y1, r1, x2, y2, r2);   d:=sqr(x1-x2)+sqr(y1-y2);
if (x1=x2) and (y1=y2) and (r1=r2) then writeln (-1)
else  if (sqr(r1+r2)=d) or (sqr(r1-r2)=d) then writeln (1)
else  if (sqr(r1+r2)<d) or (sqr(r1-r2)>d) then writeln (0)
else writeln (2); end.

Завдання 2. Cтворити та реалізувати мовою програмування Pascal, що визначає
за розмірами прямокутних дверей a, b та розмірами шафи, що має форму прямокутного паралелепіпеда x, y, z, x, y, z < 10 чи можна пронести шафу у двері, якщо проносити її дозволяється так, щоб кожне ребро шафи було паралельне або перпендикулярне кожній стороні дверей.
program SHАFA2;
var a, b, c, x, y, z:real;
begin  readln (a, b, x, y, z);
if ((x<a) and (y<b)) or ((x<b) and (y<a)) or ((z<a) and (y<b)) or
((x<a) and (z<b)) or ((y<a) and (z<b)) or ((z<a) and (x<b))
then writeln (1) else writeln (0); end.

Завдання 3. Cтворити та реалізувати мовою програмування Pascal.
Гена збирається на туристичний зліт учнів своєї школи. У своєму класі його було призначено відповідальним за палатки. У себе вдома він знайшов 3 палатки: перша з них важить a1 кілограм і вміщує b1 чоловік, друга важить a2 кілограм і вміщує b2 чоловік, третя важить a3 кілограм і вміщує b3 чоловік.
У класі Гени k чоловік. Виясніть, чи може він вибрати палатки так, щоб у них змогли поміститись усі. При цьому враховуйте, що вибрані палатки повинні разом важити не більше w кілограм.
Вхідні дані: два цілих числа k та w (1 ≤ k ≤ 15, 1 ≤ w ≤ 30). Другий рядок містить шість цілих чисел: a1, b1, a2, b2, a3, b3 (1≤ a1, a2, a3 ≤ 10, 1 ≤ b1, b2, b3 ≤ 15).
program KLASS3;
var k,w,a1,a2,a3,b1,b2,b3: integer;
n1, n2, n3, n4,  m1, m2, m3, m4: integer;
begin  read (k,w);   readln (a1,b1,a2,b2,a3,b3);
m1 := a1 + a2; n1 := b1 + b2;   m2 := a1 + a3; n2 := b1 + b3;
m3 := a3 + a2; n3 := b3 + b2;   m4 := a1 + a2 + a3; n4 := b1 + b2 + b3;
if ( (a1<=w) and (b1>=k) ) or ( (a2<=w) and (b2>=k) ) or
( (a3<=w) and (b3>=k) ) or  ( (m1<=w) and (n1>=k) ) or
( (m2<=w) and (n2>=k) ) or  ( (m3<=w) and (n3>=k) ) or
( (m4<=w) and (n4>=k) ) then writeln('YES')   else writeln('NO');

end.


Завдання 4. Cтворити та реалізувати мовою програмування Pascal.
У різдвяний вечір на підвіконні стояли три квіточки, зліва направо: герань, крокус та фіалка. Кожен ранок Маша витирала підвіконня і міняла місцями квіточку, що стояла праворуч,з центральною квіточкою. А Таня кожен вечір поливала квіточки і міняла місцями ліву та центральну квіточки. Потрібно визначити порядок квітів вночі після того, як пройде k днів.
Вивести m рядків, що містять по три латинських літери: "G", "C" и "V" (великі літери без пропусків), які описують порядок квітів на вікні по закінченню k днів (зліва направо). Позначення: G – герань, C – крокус, V – фіалка.
program E4;
var  m, k, i: integer;
begin readln(m);
for i := 1 to m do begin  readln(k);
if (k mod 3 = 1) then writeln('VGC');
if (k mod 3 = 2) then writeln('CVG');
if (k mod 3 = 0) then writeln('GCV');
end; end.


Завдання 5.  Cтворити та реалізувати мовою програмування Pascal.
Степан влітку відпочиває у бабусі в селі. Особливо йому подобається
купатись на сільському озері. Посередині озера плаває пліт, який має форму прямокутника. Сторони плота спрямовані уздовж паралелей і меридіанів. Введемо систему координат, в якій вісь ОХ направлена на схід, а вісь ОY – на північ. Нехай південно-західний кут плоту має координати (x1, y1), північно-східний кут - координати (x2, y2).

Cтепан знаходиться в точці з координатами (x, y). Визначте, до якої сторони плоту (північної, південої, західної чи східної) або до будь-якого кута плоту (північно-західному, північно-східному, південно-західному,
південно-східному) Степану потрібно плисти, щоб якомога швидше дістатися до плоту.

Формат вхідних даних:

Дано шість чисел в наступному порядку: x1, y1 (координати південно-
західного кута плоту), x2, y2 (координати північно-східного кута плоту), x,

y (координати Степана). Всі числа цілі і по модулю не перевершують 100.
Гарантується, що x1 < x2, y1 < y2, x ≠ x1, x ≠ x2, y ≠ y1, y ≠ y2, координати Степана
знаходяться поза плотом.
Формат вихідних даних:
Якщо Степану слід пливти до північної сторони плоту, програма повинна
вивести символ «N», до південної - символ «S», до західної - символ «W», до
східної - символ «E». Якщо Степану слід пливти до кута плоту, потрібно
вивести один з наступних рядків: «NW», «NE», «SW», «SE».


Пліт умовно розбиває площину на 8 частин. (див.мал.)
Очевидно, якщо точка з координатами (x, y) знаходиться у 2, 4, 6 або 8
частині площини, то найкоротшою відстанню до плоту буде перпендикуляр, проведений відповідно до північної, східної, південної або західної сторони.
Якщо точка з координатами (x, y) знаходиться у 1, 3, 5, 7 частинах
площини, то найкоротшою відстанню буде відповідний кут плота.
Розв’язання:
var x1,x2,x,y1,y2,y:integer;
begin
read(x1,y1,x2,y2,x,y);
if (x<x1) and (y>y1) and (y<y2) then write('W');
if (y>y2) and (x>x1) and (x<x2) then write('N');
if (x>x2) and (y>y1) and (y<y2) then write('E');
if (y<y1) and (x>x1) and (x<x2) then write('S');
if (x<x1) and (y>y2) then write('NW');
if (x>x2) and (y>y2) then write('NE');
if (x<x1) and (y<y1) then write('SW');
if (x>x2) and (y<y1) then write('SE');
end.



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

Сортування чисел методом вставки


Практична робота 26.   Сортування  чисел  методом вставки
Завдання 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 inserting(n: integer; var m: vector); {Метод вставки, де порівнянь до n*log2(n) }
var i,a,b,c:integer;     k: real;
begin      for i:=2 to n do begin  { У відсортованій частині  шукаємо місце черг-ого елемента}
  a:=1; b:=i;   k:=m[i];        while a<b do begin  c:=(a+b)div 2;
      if less(k,m[c]) then           while b>c do begin         m[b]:=m[b-1];  b:=b-1;       end
      else a:=c+1    end;     m[a]:=k; swpcnt:=swpcnt+i-a;
    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;
   inserting(n,m); {виклик процедури сортування  методом вставки }
  writeln('Всього виконано ', cmpcnt, ' порівнянь та ', swpcnt, ' перестановок');
  writeln(' Відсортований масив в порядку зростання:');    writevector(n,m);   end.

Сортування чисел методом Хоора мовою Pascal


Практична робота 25.   Сортування  чисел  методом Хоора мовою Pascal
Завдання 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 hoor(a,b: integer; var m: vector); { Рекурсивний алгоритм швидкого сортування Хоора}
var   i,j,c: integer;     k: real;
begin  if a<b then begin  c:=(a+b) div 2; k:=m[c];{Обираємо ключовий елемент}
        { ділимо масив на дві групи, порівнюючи з ключовим елементом }
    i:=a; j:=b; repeat  if (i=c) and (i<j) then begin swap(m[i],m[j]); c:=j end;
      if   not less(k,m[i])   then   i:=i+1    else  begin  swap(m[i],m[j]);       j:=j-1;
         if j=c then c:=i         end       until i>j;
    { Якщо друга група порожня – перносимо в неї ключовий елемент }
    if   i>b   then   i:=b;        if   trace   then   writevector(b,m);
  {виконуємо сортування кожної частини, викликаючи саму себе процедури}
    hoor(a,i-1,m);        hoor(i,b,m);     end;   end;
{Основний алгоритм, який використовує допоміжні алгоритми}
var    n,i: integer;   m: vector;  ans: char;   {назва змінних величин}
begin    repeat       {цикл з післяумовою  для введення довжини масиву   }
 write('Введено розмір масиву(від 1 до ', maxcnt, '): '); n:=2+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;
   hoor(1,n,m);    {виклик процедури сортування  методом Хоора  чисел}
  writeln('Всього виконано ', cmpcnt, ' порівнянь та ', swpcnt, ' перестановок');
  writeln(' Відсортований масив в порядку зростання:');    writevector(n,m);   end.