Aлгоритми мовою Pascal(практ. роботи)

Практична робота 1.
 Лінійні алгоритми мовою Pascal

Завдання 1.  На конференцію приїхали рівно по k представників від m(не менше ніж 2) фірм-конкурентів по виробництву гри "Саmрf", при цьому, усі представники різних фірм є конкурентами. Відомо, що у кожного учасника конференції рівно  n конкурентів серед усіх інших учасників.  Скласти алгоритм, який знаходить найбільшу кількість учасників  та найменшу кількість фірм-конкурентів в конференції?

 Розв’язання.  Кількість учасників конференції дорівнює km осіб. З іншого боку, кількість конкурентів у одного представника дорівнює k(m-1)= n, звідси маємо рівність km =  n + k, права частина якого є лінійний вираз відносно двох змінних. Лінійний вираз р(k)= n + k досягає свого найбільшого і найменшого значення на межах числового проміжка від 1 до n. Якщо   k = n, то маємо найбільше значення р(n)= n + n =2n, тому  nm = 2n, звідси  m = 2. Відповідь: 2n осіб, 2 фірми.

Алгоритм мовою Pascal

program МіnConkurent;    var k,m,n:integer;    begin

writeln('введіть число конкурентів  в особи 2<n<10⁹  n='); readln(n);

write('найбільше:', 2*n, ' осіб');  {вивід найбільшого числа учасників}

write('найменше: 2 фірми'); {вивід найменшого числа учасників}

end.                              {оголошення кінця алгоритму}

Завдання 2.  На конференцію приїхали рівно по k представників від m(не менше ніж 2) фірм-конкурентів по виробництву гри "Саmрf", при цьому, усі представники різних фірм є конкурентами. Відомо, що у кожного учасника конференції рівно  n конкурентів серед усіх інших учасників.  Скласти алгоритм, який знаходить найбільшу кількість фірм-конкурентів і найменшу кількість представників в конференції?

 Розв’язання.  Кількість учасників конференції дорівнює km осіб. З іншого боку, кількість конкурентів у одного представника дорівнює k(m-1)= n, звідси маємо рівність km =  n + k, права частина якого є лінійний вираз відносно двох змінних. Лінійний вираз р(k)= n + k досягає свого найбільшого і найменшого значення на межах числового проміжка від 1 до n. Якщо   у формулі р(k)= n + k,  підставимо k = 1, то отримаємо найменше значення р(1)= n + 1 , тому найбільше значення m = n+1, звідси  n = m-1. Відповідь: n+1 фірм, 1 особа.

Алгоритм мовою Pascal

program МахConkurent;    var n:integer;    begin

writeln('введіть число конкурентів  в особи 2<n<10⁹  n='); readln(n);

write('найбільше:' n+1, 'фірм');  {вивід найбільшого числа фірм}

write('найменше: 1 представник від фірми'); {вивід найменшого числа представників }   end.   {оголошення кінця алгоритму}

Завдання 3. Відомо, що книжкова полиця вміщає k однакових товстих книг, але k+1-а книга вже не влазить. Так само на неї можна поставити m однакових тонких книг, а m+1 -а вже не влізе. Скласти алгоритм, який знаходить можливість, щоб на полиці помістилися одночасно: n товстих та p тонких книг.

Розв’язання.  Якщо числовий вираз  n/k + p/m <=1, то можна, якщо  числовий  n/k + p/m > 1, то не можна помістити одночасно книги на полицю.

Алгоритм мовою Pascal (використовує повне розгалуження, «якщо-то, інакше»)

program BIBLIO;    var k,m,n,p,h:real;    begin

writeln('введіть число товстих книг 2<k<10⁹  k='); readln(k);

writeln('введіть число тонких книг 2<m<10⁹  m='); readln(m);

writeln('введіть даних товстих книг 2<n<10⁹  n='); readln(n);

writeln('введіть даних тонких книг 2<p<10⁹  p='); readln(p);  h:=(n/k)+(p/m);

 if  (h<1) or (h=1) then write(' кнгиги можна помістити') {розгалуження для виводу результату}

else  write('не можна помістити книги');  {інакше то вивід результату не можна}

writeln('h=', h); end. 

Практична робота 2.  
Програмування циклів мовою 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. 

Практична робота 3. 
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. 

Практична робота 4.  
Програмування циклів мовою 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-класників.  Кількість способів, обчислюємо як сума комбінацій: С¹_k/2+1  +С²_k/2+1 +С³_k/2+1+…+ +С^k/2_k/2+1. Аналогічно знаходимо кількість способів для 9-класників: С¹_m/2+1  +С²_{m/2 +1}+С³_m/2+1+…+ +С^m/2_m/2+1. Аналогічно знаходимо кількість способів для 10-класників: С¹_n/2+1  +С²_n/2+1 +С³_n/2+1+…+ +С^n/2_n/2+1. А кількість вибору того, що у парламенті мають бути представники від трьох паралелей:

     р=(С¹_k/2+1  +С²_k/2+1 +С³_k/2+1+…+ С^k/2_k/2+1)( С¹_k/2+1  +С²_k/2+1 +С³_k/2+1+…+ С^k/2_k/2+1)(С¹_k/2+1  +С²_k/2+1 +С³_k/2+1+…+ С^k/2_k/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  ліцеїсток.  Кількість способів обрати тільки ліцеїсток обчислюємо як  комбінації: С¹_m =m(1 місце в раді парламенту); С²_m =m(m-1)/2( для двох осіб) ; С³_m  ;…  С^m_m.  (буває варіант Сⁿ_n =1, якщо n=m і в Раді парламенту лише ліцеїстки і немає ліцеїстів).  Аналогічно знаходимо кількість способів для ліцеїстів:

С¹ _k =k;  С²_k =k(k-1)/2; ….., С^k-1_k=k-1 (для k-1 ліцеїстів);С^k_k=1 (для k ліцеїстів); С⁰_k (для n-1 ліцеїсток і 1 ліцеїстa);

Таким чином, вибір усіх осіб у Раду парламенту за цих умов можна здійснити сумою добутків:

р= С¹_kС^n-1_m + С²_kС^n-2_m +  … + С^n-2_mС²_k + С^n-1_mС¹_k

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}

Практична робота 5.
Лінійні алгоритми на мові Pascal

Завдання 1. Скласти і реалізувати алгоритм  для знаходження кількості днів, за яку виконають сумісну роботу два програміста, якщо такий об’єм роботи перший програміст самостійно виконує за k днів, а другий програміст самостійно виконує за m днів.

program  Pobota_1;                     {назва    алгоритму}

var  k,m: real;                             {оголошення  змінних величин: k,m – це дійсні числа}

begin                                                                                      { початок   виконання алгоритму}

  writeln( 'k='); readln(k); writeln( 'm='); readln(m);    { введення двох чисел}

   k:=(k*m)/(k+m);                                                            { обчислення за формулою}

writeln('Разом виконають за ', k, ' днів');                   { виведення результату}

end.                                                                                     {закінчення алгоритму}

Протестуйте алгоритм для  таких значень  k i m: а)12 i 8; б)3,2 i  2,4; в)6,5 i 2,6; г)42 і36; д)40,30 і 40,45;  е)20 і 16; є)80 і 84.

Завдання 2. Скласти і реалізувати алгоритм  для знаходження справжньої маси монети, якщо її зважували на бракованих терезах з нерівними плечами, і при викладенні гирьок на першій чашечці, то маса монети на протилежній чашечці становила k грам, а при викладанні гирьок на другій чашечці терезів маса монети на протилежній чашечці становила  m грам.

program  Pobota_2;                     {назва    алгоритму}

var  k,m: real;                             {оголошення  змінних величин: k, m – це дійсні числа}

begin                                                                                      { початок  виконання  алгоритму}

  writeln( 'k='); readln(k); writeln( 'm='); readln(m);    { введення двох чисел}

   k:=sqrt(k*m);                                                                 { обчислення за функцією квадратного кореня}

writeln('Cправжня маса монети: ', k, '  грам);                   { виведення результату}

end.                                                                                     {закінчення алгоритму}

Протестуйте алгоритм для  таких значень  k i m: а)12 i 8; б)3,2 i  2,4; в)6,5 i 2,6; г)42 і36; д)40,30 і 40,45;  е)20 і 16; є)80 і 84.

Завдання 3. Є три гаманці: татчин, мамчин, сина. У татовому гаманці: k грн, у маминому гаманці  m  грн. Бабуся запитала внучка, яку б ти хотів мати cуму грошей у своєму гаманці і запропонувала чотири можливі варіанти: 1) середнє арифметичне грошей у двох гаманцях, що мають  k+1000  грн і m-1000  грн відповідно; 2) середнє геометричне грошей, що у двох гаманцях, котрі мають  k-2000 грн і m+2000  грн відповідно; 3)середнє квадратичне грошей у двох гаманцях, котрі мають  k-3000 грн і m+3000  грн відповідно; 4) середнє гармонійне грошей у двох гаманцях, котрі мають  k+4000 грн і m-4000  грн відповідно. Для внучка бабусі скласти і реалізувати алгоритм  для впорядкування  від найбільшого до найменшого названих бабусею чотирьох грошових величин.

program  Pobota_3;                     {назва    алгоритму}

var  k,m,n: real;                             {оголошення  змінних величин: k, m, n – це дійсні числа}

begin                                                                                      { початок  виконання  алгоритму}

  writeln( 'k='); readln(k); writeln( 'm='); readln(m);    { введення двох чисел}

   n:=sqrt(((k-3000)*(k-3000)+(m+3000)*(m+3000))*0.5);   {обчислення за фор-лою серед-ого квадр-ного}

writeln('Cереднє квадратичне: ', n, '  грн ');                   { виведення результату}

   n:= ((k+1000)+(m-1000))*0.5;   {обчислення за фор-лою серед-ого арифметичного}

writeln('Cереднє арифметичне: ', n, '  грн ');                   { виведення результату}

   n:=sqrt((k-2000)*(m+2000));   {обчислення за фор-лою серед-ого геометр-ного}

writeln('Cереднє геометричне: ', n, '  грн ');                   { виведення результату}

   n:=2*((k+4000)*(m-4000))/ ((k+4000)+(m-4000))   ;   {обчислення за фор-лою серед-ого гарм-ного}

writeln('Cереднє гармонійне: ', n, '  грн ');                   { виведення результату}

end.                                                                                     {закінчення алгоритму}

Протестуйте алгоритм для  таких значень  k i m: а)10000 i 80000; б)300000 i  400000; в)600500 i 900600.

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

Завдання 1. Із потяга зійшли два пасажира і направились одночасно в один і той же пункт А. Перший пасажир половину часу йшов зі швидкістю v1 м/год, а другу половину часу йшов зі швидкістю v2 м/год. Другий пасажир йшов першу половину шляху зі швидкістю v1 м/год, а другу половину шляху зі швидкістю v2 м/год. Допоможіть слідчому, дізнатися, яку відстань долали пасажири від виходу із потяга до пункту призначення і хто першим прибуває в пункт А.  Скласти і реалізувати алгоритм  для вияснення, хто першим прибуває у пункт призначення і на скільки раніше, ніж інший, якщо відомо, що перший пасажир витрачає на весь свій шлях t хвилин?

program  Pobota_4;                     {назва    алгоритму}

var  v1,v2,t1,t2, s1 : real;       {оголошення  змінних величин: v1,v2,t1,t2, s1,s2 – це дійсні числа}

begin                                                                                      { початок  виконання  алгоритму}

  writeln( 'v1='); readln(v1); writeln( 'v2='); readln(v2);  writeln( 't1='); readln(t1);      

   s1:=(v1+v2)*t1*0.5; {обчислення за фор-лою відстані від потяга до пункту}

writeln('Довжина шляху пасажирів', s1, '  метрів ');                   { виведення результату}

t2:=(v1+v2)* (v1+v2)*t1*0.25/( v1*v2);   {обчислення за фор-лою  часу другого пасажира}

writeln('Час руху другого пасажира: ',t2, '  хвилин ');                   { виведення результату}

  if  t2 –t1=0 then writeln('У пункт  А  пасажири прибувають одночасно');    

if  t2 –t1>0 then writeln('У пункт  А раніше прибуває перший пасажир на: ', t2 –t1, '  хвилин. ');    end.                                                                                    

Протестуйте алгоритм для  таких значень  {v1; v2; t1}: а)(90; 80; 30)=0,1 хв; б) (85; 85; 40)=0 хв; в)(60; 80; 20)=0,42 хвилини.

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

Завдання 1. Створити алгоритм повного розгалуження  if ….. then  … else

program pryklad_01;

var a,b,c,y: real;

begin

write(‘Vvedit a’); readln(a);

write(’Vvedit b’); readln(b);

write(‘Vvedit c’); readln(c);

if a>=15 then

  begin

    if a<=20 then begin writeln( ‘a v diapazoni  15-20 ‘); 

y:=10-(exp(abs(a-b)))*(exp(a*(ln(sqr(sin(c)/cos(c)+1)))); end

    else writeln begin ( ‘a >20 ‘ );

y:=20-(exp(abs(a-b)))*(exp(a*(ln(sqr(sin(c)/cos(c)+1)))); end;

  end

else writeln(‘a<15’);

y:=30-(exp(abs(a-b)))*(exp(a*(ln(sqr(sin(c)/cos(c)+1))));

writeln(‘y=’,y);

readln;

end.

Завдання 2. Створити алгоритм повного вибору  case N of …. else

Program zrazok_02;

var Num: integer;

begin

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

readln(Num);

case Num of

0: writeln('Нуль');

1: writeln('Один');

2: writeln('Два' );

3: writeln('Три ');

4: writeln('Чотири') ;

5:writeln('П’ять');

6:writeln('Шість');

7:writeln('Сім');

8:writeln('Вісім');

9:writeln('Дев’ять');  

else writeln('Число не є цифрою');  end;  readln;  end.

Завдання 3. Створити алгоритм повного розгалуження  if ….. then  … else

program Bilshe03;

var a,b:integer;

begin

writeln('Vvedit a:');  readln(a);

writeln('Vvedit b:');  readln(b);

if a>b then writeln('a=',a) else

if a<b then writeln('b=',b) else writeln('a=b');  end.

Практична робота 43. Лінійні алгоритми.

Завдання 1. Cтворити та реалізувати мовою програмування Pascal випадкове трицифрове число і розділити його на цифри. Оскільки ми користуємося позиційною десятковою системою, то поділ числа на цифри виконується цілочисельним діленням даного числа на 10. Для цього використовуємо операції DIV та MOD.

Program PROBA_01;

var a:integer;

begin   a:=1+random(999);

writeln(a div 100, '  ' , (a mod 100) div 10,'  ',a mod 10);  end.

Завдання 2. Cтворити та реалізувати мовою програмування Pascal, що знаходить найменшу кількість розрізів куба розміром АхВхС, де 1 ≤ А, B, C ≤ 200000.  на одиничні кубики розміром 1х1х1. Найменша кількість  розрізів не залежить від вибору порядку прорізання сторін і обчислюється за формулою. Виведемо її. Почнемо розрізати по стороні А і одразу проріжемо на максимальну кількість частин. Отримаємо А частин розміру 1*В*С і виконаємо А-1 розрізів. Далі ріжемо кожен з отриманих кусків по стороні В. Отримаємо А*В кусків розмірами 1*1*С, виконавши при цьому всього А*(В-1) розріз. Залишається виконати розрізання по стороні С. Буде виконано А*В*(С-1) розрізів. Усього маємо (А-1)+А*(В-1)+А*В*(С-1)=А-1+А*В-А+А*В*С-А*В=А*В*С-1 розрізів.

Program PROBA_02;

var a,b,c: integer;   begin      a:=abs(random(99999));

 b:=abs(random(999999));   c:=abs(random(99999));

writeln(abs((a*b*c)-1));  end.

Завдання 3.  Cтворити та реалізувати мовою програмування Pascal, що знаходить найбільшу кількість точок із цілочисельними координатами на аркуші в клітинку можна накрити квадратом зі стороною N клітинок(1 ≤ N ≤ 10000).  Накреслимо на папері в клітинку квадратики зі сторонами 1, 2, 3, ... клітинок. У першому випадку ми закриємо 4 точки, у другому – 9, у третьому – 16... Як бачимо, ми отримуємо числа, що є точними квадратами: 2^2, 3^2, 4^2... Тому для введеного числа А потрібно вивести квадрат наступного числа.

Program PROBA_03;

var a: integer;

begin   a:=abs(random(999999));   writeln((a+1)*(a+1)); end.  

Завдання 4.  N будинків вишикувані в ряд. Cтворити та реалізувати мовою програмування Pascal, що знаходить кількість способів поселити Віку та Юлю в різні будинки так, щоб ці будинки не були сусідніми.

Program PROBA_04;

var a: integer;

begin a:=abs(random(999999));  

writeln((a-2)*(a-1));  end.

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

Завдання 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 KLASS4;

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 частинах

площини, то найкоротшою відстанню буде відповідний кут плота.

Розв’язання:

Program PROBA_05;

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.

Завдання 6. Cтворити та реалізувати мовою програмування Pascal, що визначає

найбільшу кількість олівців k, які може купити Семен на S гривень  після подорожчання на Р відсотків.

Технічні умови. У першому рядку задано число N (1 ≤ N ≤ 10⁷) - вартість олівця до подорожчання. У другому рядку - Р (0 ≤ Р ≤ 100) - величина подорожчання олівця у відсотках. В третьому рядку - S (1 ≤ S ≤ 10⁷) - сума грошей, яка є у Семена.

Program PROBA_06;

var n,s,p,k,t:integer;

begin

read(n);  readln(p);  readln(s);

k:= s*100 div(n+n*p);   ;

write(k);

end.

Завдання 7. Cтворити та реалізувати мовою програмування Pascal, що визначає вагу запакованих речей рюкзака і валізи, якщо Семен збирає речі у похід. З собою в автобус він може взяти ручну поклажу і багаж. Для ручної поклажі у нього є рюкзак, а для багажу - здоровенна валіза.  За правилами перевезення маса ручної поклажі не повинна перевищувати S кг, а багаж може бути будь-якої маси (за наднормативний багаж Семен готовий доплатити). Зрозуміло, найбільш цінні речі - ноутбук, фотоапарат, документи і т. д. - Семен хоче покласти в ручну поклажу.

Семен розклав усі свої речі в порядку зменшення їх цінності і починає складати найбільш цінні речі в рюкзак. Він діє в такий спосіб - бере найцінніший предмет, і якщо його маса не перевищує S, то кладе його в рюкзак, інакше кладе його до валізи. Потім він бере наступний за цінністю предмет, якщо його можна покласти в рюкзак, тобто якщо його маса разом з масою вже покладених в рюкзак речей не перевищує S, то кладе його в рюкзак, інакше до валізи, і таким же чином процес триває для всіх предметів в порядку спадання їх цінності.

Визначте вагу рюкзака і валізи після того, як Семен складе всі речі.

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

Перший рядок вхідних даних містить число S (1 ≤ S ≤ 2 × 10⁹) – максимально дозволенa вага рюкзака. У другому рядку вхідних даних записано число N (1 ≤ N ≤ 10⁵) - кількість предметів.

У наступних N рядках дано маси предметів, самі предмети перераховані в порядку спадання цінності (спочатку вказана маса найціннішого предмета, потім маса другого по цінності предмета і т. Д.). Всі числа натуральні, сума ваги всіх предметів не перевищує 2 × 109.

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

Виведіть два числа - вагу рюкзака і вагу валізи (вага порожнього рюкзака і валізи не враховується).

Приклади Вхідні дані	Результат роботи
10 4 6 3 4 1	10 4

Нехай m1– вага рюкзака і m2 – вага валізи.

Беремо перший предмет з вагою а і перевіряємо, якщо m1+a не перевищує s, то збільшуємо m1 на а, інакше m2 збільшуємо на a.

Розв’язання: 1 спосіб

Program PROBA_07;

var s, n, a, m1, m2, i: integer;

begin

readln(s);   readln(n);

i:=1;   m1:=0;   m2:=0;

while i<=n do  begin   readln(a);

if (m1+a<=s) then m1:=m1+a else m2:=m2+a;

i:=i+1;  end;

write(m1,' ',m2);  end.

2 спосіб

var v,b,n,s,i:longint;    a:array [1..1000000] of longint;

begin

read(s,n);

for i:=1 to n do read(a[i]);

b:=0;   v:=0;

for i:=1 to n do

  if b+a[i]<=s then b:=b+a[i] else v:=v+a[i];

write(b,' ',v);

end.

Завдання 7.

Степан виписує на листочку усі цілі числа від 1 до N в кілька груп, при цьому якщо одне число ділиться на інше, то вони обов'язково будуть у різних групах.

Наприклад, якщо N = 9, то отримаємо 4 групи:

Перша група: 1.

Друга група: 2 3 7.

Третя група: 4 5 6.

Четверта група: 8 9.

Очевидно, що оскільки, будь-яке число ділиться на 1, то одна група завжди буде складатись тільки з числа 1, а от інші групи можуть бути створені різними способами.

Допоможіть Степану написати програму, яка визначає мінімальне число груп, на яке можна розбити усі числа від 1 до N у відповідності до наведеної вище умови.

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

Перший рядок вхідних даних містить єдине число N (1 ≤ N ≤ 109).

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

Виведіть одне число - знайдену мінімальну кількість груп.

Приклади Вхідні дані	Результат роботи
9	4

Наприклад, якщо визначати кількість груп для послідовних чисел від 1 до 20, то можна побачити, що вона (кількість) є степенем числа 2. Таким чином для будь-якого числа N можна розглянути нерівність 2k ≤ N < 2k+1, і шуканою відповіддю буде число k+1.

Program proba08;

var n,v,i,st: integer;

begin

read(n);

v:=1;  st:=2;  i:=2;

while i<=n do begin i:=st*2; st:=i; inc(v);  end;

if n<>1 then write(v) else write(1); end.

 Завдання для самостійного створення алгоритмів:

https://www.e-olymp.com/ru/contests/9646/problems/84668

1.Мінімальна сума цифр. Скільки натуральних чисел з проміжку [m, n] мають найменшу суму цифр? Створити алгоритм.
Вхідні дані
Містить два числа m і n (1 ≤ m ≤ n ≤ 106).
Вихідні дані
Вивести кількість натуральних чисел з проміжку [m, n] з найменшою сумою цифр.

2.Тризначні числа. На заданому проміжку [a, b] виведіть у зростаючому порядку всі тризначні числа, у яких всі цифри різні.
Вхідні дані
Два натуральних тризначних числа a і b (100 ≤ a ≤ b ≤ 999).
Вихідні дані
Вивести в порядку зростання всі тризначні числа з інтервалу [a, b] з різними цифрами. Кожне число слід виводити в окремому рядку.

3.Мінімум і максимум. Знайти мінімум і максимум двох натуральних чисел.
Вхідні дані
Два натуральних числа a і b (a, b ≤ 109).
Вихідні дані
В одному рядку вивести найменше а потім найбільше серед двох чисел a і b.

4. Сума цифр. Дано n чисел. Знайдіть серед них число з мінімальною сумою цифр (а з чисел з однаковою сумою - останнім).
Вхідні дані
У першому рядку знаходиться число n (1 ≤ n ≤ 105). У наступному рядку через пропуск перераховані всі числа. Всі числа натуральні, що не перевищують 109.
Вихідні дані
Виведіть одне число - шуканий мінімум.

5. Відгадай-но. Напишіть алгоритм-програму, яка вгадує задумане людиною число.Відомо, що воно натуральне і не перевищує деякого наперед заданого числа n. Вгадувати дозволено ставити тільки питання виду  •? A  що означають питання "Задумане число більше A?". На це питання можна отримати тільки один з двох відповідей: "Так" або "Ні".Кількість даних питань має бути мінімально можливим для будь-якого числа, що не перевищує n.
Вхідні дані
Одне натуральне число n (1 ≤ n ≤ 2 · 109).
Вихідні дані
Вивести мінімально можливу кількість питань для будь-якого числа, що не перевищує n.