Нелінійні алгоритми різних типів

Практична робота 1. 

Нелінійні алгоритми різних типів

Завдання 1. Створити та реалізувати алгоритм мовою програмування Pascal, що містить двовимірний масив array [1 .. n, 1 .. 10] , вкладені цикли  for i:=1   to n do  з лічильниками  по двом індексам і цикл  while  …  do з передумовою для обчислення похибок обчислень в масиві.

program proced1;

const n=5; m=10;     type     mas = array [1 .. n, 1 .. m] of real;     var a: mas;   e, eps: real;    j,i: integer;

begin

for i:=1   to n do  begin  for j:=1    to m do  a[i,j]:=random(10);  end;    eps:=0.001;

for i:=1 to n do begin  for j:=1 to m do begin  e:= 0.987*a[i,j]-(1-0.123*eps)*a[i,j];

while   e > 0.0001  do    e:=e/10;  end; end;

writeln('Це похибка обчислень', e);  end.

Завдання  2. Створити та реалізувати алгоритм мовою програмування Pascal, що містить двовимірний масив array [1 .. n, 1 .. 10] , вкладені цикли  for i:=1   to n do  з лічильниками  по двом індексам і цикл  repeat      …..   until   …  з післядумовою для обчислення похибок обчислень в масиві.

program proced2;

const n=3; m=4;     type     mas = array [1 .. n, 1 .. 10] of real;     var b: mas; e, eps: real;   j,i: integer;

begin

for i:=1   to n do  begin  for j:=1    to m do  b[i,j]:=random(10);  end;

eps:=0.001;

for i:=1 to n do begin  for j:=1   to  n  do  begin  

repeat      e:= a[i,j]-(1-eps)*a[i,j];  e:=e/10;   until   e > 0.01;  end; end;

writeln('Це похибка обчислень', e);  end.

Завдання  3.  Створити та реалізувати алгоритм мовою програмування Pascal, що містить процедуру, яка знаходить найбільше значення двох цілих чисел.

program proced3;

var x,y,m,n: integer;

     procedure maxnumber(a,b: integer;  var max: integer);

     begin      if a>b  then  max:=a  else max:=b;  end;

begin

 x:=random(100);    writeln(' x=', x);   y:=random(100);        writeln(' y= ', y);       

   maxnumber(x,y,m);       maxnumber(2, x+y, n);

   writeln(' max=', m, '  summa  n=', n);  end.

Завдання 4. Створити та реалізувати алгоритм, що містить функцію, яка знаходить найбільше значення двох цілих чисел.

program proced4;

var x,y,m,n: integer;

function MaxNumber(a,b: integer): integer;

   var max: integer;

begin

   if a>b then max:=a else max:=b;

   MaxNumber := max;  end;

begin

   x:=40-random(100);    writeln(' x=', x);   y:=50-random(100);        writeln(' y= ', y);       

   m := MaxNumber(x,y);       n := MaxNumber(2,x+y);

   writeln('max=', m, '  summa=', n);  end.

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

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

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

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

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

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

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.