ВІДПОВІДІ ТА ВКАЗІВКИ ДО ЗАДАЧ

Розділ 1

1.1. Формат!

Розділ 2

2.1. Усюди визначено тільки odd і порівняння, інші частково визначено.

2.2. xor для бульових - це те ж саме, що нерівність <>.

2.3. а) true; б) true; в) false; г) false.

2.4. а) 2; б) false; в) true; г) false; д) 6; е) 3.

2.5. а) ні; б) ні; в) ні; г) так, true.

2.6. а) ord(a<b)*b+ord(a>=b)*a; б) a mod 10; в) a mod 10 + a div 10;

г) a mod 10 + a mod 100 div 10 + a div 100.

2.7. а) (a=b) and (a=c);

б) (a+b>c) and (a+c>b) and (b+c>a);

в) (a*a=b*b+c*c) or (b*b=c*c+a*a) or (c*c=a *a+b*b);

г) (a*a<b*b+c*c) and (b*b<c*c+a*a) and (c*c<a*a+b*b);

д) (a+b>c) and (a+c>b) and (b+c>a) and (( a=b) or (b=c) or (a=c));

е) (a+b>c) and (a+c>b) and (b+c>a) and (a<>b) and (a<>c) and (b<>c);

ж) (a=b) and (c=d) or ( a=c) and (b=d) or (a=d) and (b=c);

з) (a1=a2)and(b1=b2)and(c1=c2) or (a1=a2)and(b1=c2)and(c1=b2)

or (a1=b2)and(b1=a2)and(c1=c2) or (a1=b2)and(b1=c2)and(c1=a2)

or (a1=c2)and(b1=a2)and(c1=b2) or (a1=c2)and(b1=b2)and(c1=a2).

2.8. а) (a1*b2=a2*b1) and ( (a1*c2<>a2*c1) or (b1*c2<>b2*c1) ).

2.9. Вказівка. Якщо обидва розміри кімнати непарні, то неможливо. Нехай один із розмірів парний. Можна "пофарбувати" підлогу як шахову дошку. Очевидно, кожна дощечка накриває клітини різного кольору. Тому покриття неможливе, коли клітини із стовпами мають той самий колір, і можливе, коли їх кольори різні.

2.10. а) t:=a; a:=b; b:=t; б) a:=a+b; b:=a-b; a:=a-b.

2.12. а) x2:=x*x; x4:=x2*x2; x10:=x2*x4*x4;

б) x2:=x*x; x4:=x2*x2; x12:=x4*x4*x4; в) x3:=x*x*x; x6:=x3*x3; x15:=x6*x6*x3

(можливі й інші варіанти).

2.14. а) Оператори тіла програми: readln(x,y); writeln(x+y).

Розділ 3

3.1. а) 9. 9999E4; б) 1. 0E-5.

3.2. а) exp(b*ln(a));

б) exp(ln(x)/y);

в) ord(x>=0)*arctan(x/sqrt(1-x*x)) + ord(x<0)*arctan(-x/sqrt(1-x*x));

г) Pi/2-arctan(x) (див. п. (е));

е) 2/3*4*arctan(1).

3.3. б) Нехай x, y – координати точки, x0, y0, r – координати центру й радіус кола. z:=sqrt(sqr(x-x0)+sqr(y-y0)); d:=ord(z>r)*z.

3.4. Усюди визначено порівняння, abs, sin, cos, а також frac і int.

3.7. в)

Що виконується

x

y

readln(x)

3

?

обчислення x=1: false

3

?

обчислення x=2: false

3

?

обчислення x=3: true

3

?

y:=4096

3

4096

3.9. Оператори тіла програми:

readln(a,b,c);

if a=0 then

if b=0 then

if c=0 then n:=3 {нескінченна множина коренів}

else {c<>0} n:=0

else {b<>0} n:=1

else {a<>0}

begin d:=b*b-4*a*c;

if d>0 then n:=2 else

if d=0 then n:=1 else

n:=0

end;

if n<3 then writeln(n) else writeln(' нескінченна множина коренів ')

3.12. а) Обчислимо кількість різних серед довжин сторін a, b, c:

if (a=b)and(b=c) then n:=1 else

if (a=b)or(b=c)or(a=c) then n:=2

else n:=3

3.13. Єдиний оператор у тілі функції: even := not odd(x). Або even := x mod 2 = 0.

3.14. б) "Математиці відповідає", наприклад, функція з операторами в тілі:

z:=round(x); if z>=x then ceil:=z else ceil:=z+1

або

z:=round(x); ceil:=z+ord(z<x).

3.18. Процедура readln має параметри-змінніів, writeln – параметри-значення.

3.19. 1. Спочатку опишемо обчислення коефіцієнтів a, b, c нормалізованого рівняння за координатами x1, y1, x2, y2 двох точок. Якщо x1=x2, тобто пряма вертикальна, то рівняння має вигляд x+c=0, де c=-x1. Якщо x1¹ x2, то рівняння можна подати у вигляді y=kx+d, де k=(y2-y1)/(x2-x1), d=y(0). Очевидно, у нормалізованому рівнянні b=1, a=-k, c=-d. Оскільки (y(0)-y1)/(0-x1)=k, маємо: d=y1-kx1=y1+ax1, c=-y1-ax1. Оформимо ці обчислення у вигляді:

procedure normcoef(x1, y1, x2, y2: real; var a, b, c: real);

begin

if x1=x2 then

begin b:=0; a:=1; c:=-x1 end

else

begin

b:=1; a:=(y1-y2)/(x2-x1); c:=-y1-a*x1

end

end

2. Дві точки лежать по один бік прямої, якщо при підстановка їх координат у ліву частину рівняння цієї прямої дає значення того самого знака, тобто d=(ax1+by1+c)(ax2+by2+c)>0. Якщо хоча б одна з точок на прямій, то d=0 (вважаємо, що точки не по один бік). Тому бульовозначна функція очевидна:

function oneside(x1, y1, x2, y2, a, b, c:real):boolean;

begin oneside:=(a*x1+b*y1+c)*(a*x2+b*y2+c)>0 end

3. Точка лежить усередині трикутника, якщо вона та кожна вершина трикутника лежать по один бік прямої, утвореної двома іншими вершинами. Тому після обчислення коефіцієнтів рівнянь прямих, що містять сторони, достатньо тричі викликати функцію oneside:

program intriang(input, output);

var x, y, {точка}

xt1, yt1, xt2, yt2, xt3, yt3, {вершини}

a1, b1, c1,

a2, b2, c2,

a3, b3, c3 : real; {коефіцієнти прямих}

procedure normcoef(x1, y1, x2, y2: real; var a, b, c: real);

begin ... end;

function oneside(x1, y1, x2, y2, a, b, c:real):boolean;

begin ... end;

begin

writeln('задайте пару координат точок:');

readln(x, y);

writeln('задайте 3 пари координат вершин трикутника:');

readln(xt1, yt1, xt2, yt2, xt3, yt3);

normcoef(xt3, yt3, xt2, yt2, a1, b1, c1);

normcoef(xt3, yt3, xt1, yt1, a2, b2, c2);

normcoef(xt1, yt1, xt2, yt2, a3, b3, c3);

if oneside(x, y, xt1, yt1, a1, b1, c1) and

oneside(x, y, xt2, yt2, a2, b2, c2) and

oneside(x, y, xt3, yt3, a3, b3, c3)

then writeln('Так! ')

else writeln('Ні! ')

end.

Розділ 4

4.1. б) Зазначимо тільки те, що буде надруковано, "забувши на хвилинку" про існування maxint:

2 2 4

3 6 8

4 24 16 (підкреслене закінчення відповіді на задачу (а))

5 120 32

6 720 64

7 5040 128

8 40320 256

9 362880 512

10 3628800 1024

4.3. function nfact(n:integer):integer;

var i, nf: integer;

begin nf:=1; i:=0;

while i<n do

begin i:=i+1; nf:=nf*i end;

{i=n; nf=n! }

nfact:=nf

end

4.4. Вказівка. Зауважимо, що при діленні на 10 із остачею кількість цифр у десятковому записі числа n зменшується на 1. Тому цифр стільки, скільки разів можна поділити число на 10, поки не одержимо 0. Тому фактично потрібно обчислити члени послідовності v0=n, v1= v0 div 10, v2= v1 div 10, … , vx+1=vx div 10, де vx<>0, vx+1=0. Випадок n=0 розглядається окремо.

4.5. function GCD(a,b:integer):integer;

{GCD – скорочення від Greatest Common Divisor,}

{тобто Найбільший Спільний Дільник}

var p1, p2, p3: integer;

begin

if a>b then begin p1:=a; p2:=b end

else begin p1:=b; p2:=a end;

while p2<>0 do

begin p3:= p1 mod p2;

p1:=p2; p2:=p3

end;

{p2=0; p1<>0, значення p1 і є GCD}

GCD:=p1

end

4.12. Вказівка. Потрібно перебрати пари чисел вигляду 6k-1 і 6k+1 для k=1, 2, … , поки 6k+1£ maxint. Якщо написати цикл із цією умовою продовження, то зрештою при обчисленні 6k+1 повинно утворитися значення, більше maxint, а це призводить до аварійного завершення програми. Дрібниця, але неприємно. Проте з цієї умови "витягається" умова k<=(maxint-1)/6, або k<=(maxint-1) div 6. У тілі циклу природно скористатися викликами функції issimple із прикладу 4.6.

Розділ 5

5.1 б)виконувані дії та їх результати:

a:=1

a:=a+2

writeln(a)

обчислення a=4

a:=a+2

writeln(a)

обчислення a=4

a:=a+2

writeln(a)

обчислення a=4

тощо

a=1

a=3

друкування 3

false

a=5

друкування 5

false

a=7

друкування 7

false

тощо

Все це неподобство закінчиться аварійно, коли зрештою при обчисленні a+2 утвориться значення, непредставне в типі integer.

5.2. procedure read0100(var a:integer);

begin a:=-1;

repeat

writeln('задайте ціле від 0 до 100:');

readln(a)

until (a>=0)and(a<=100)

end

5.3. а) if B then repeat S until not B;

б) S; while not B do S.

5.4. Будемо зберігати поточні межі інтервалу та його середину в змінних l, h і m, а значення функції в цих точках – у змінних vl, vh і vm. Нехай eps означає точність, із якою обчислюється корінь. У найпростішому варіанті оператори, що безпосередньо описують обчислення, можуть виглядати так:

l:=a; h:=b;

vl:=ff(l); vh:=ff(h);

repeat

m:=0.5*(l+h); vm:=ff(m);

if vm*vh>0 then {корінь зліва від m}

begin h:=m; vh:=vm end

else {корінь справа від m}

begin l:=m; vl:=vm end

until l-h<eps

5.5. 2 3

3 4

4 5

Alles!

Вирази в заголовку циклу обчислюються тільки один раз спочатку! Німецьке "Alles" означає "усе".

5.7. а) Очевидно, що m£ (b-a)/h, m+1>(b-a)/h, тобто m=[(b-a)/h]:

m:=trunc((b-a)/h));

for i:=0 to m do writeln(a+i*h, f(a+i*h)).

5.8. program Christmas_tree;

var k, m : integer;

begin

for k:=1 to 25 do writeln;

for k:=1 to 39 do write(' '); writeln('*');

for m:=1 to 2 do

begin

for k:=1 to 38 do write(' '); writeln('***');

for k:=1 to 37 do write(' '); writeln('*****')

end;

for k:=1 to 36 do write(' '); writeln('*******');

for k:=1 to 39 do write(' '); writeln('|');

for k:=1 to 9 do writeln;

end.

5.9. Спочатку з'ясуємо, скільки позицій займатиме найбільше з чисел. Очевидно, ним є Отже, для кожного числа достатньо 4 позиції (3 для цифр і 1 для відокремлення від попереднього числа). Кожне число будемо записувати в поле шириною 4 символи. Тоді перед одноцифровим числом з'явиться 3 пропускання, перед двоцифровим – 2 тощо. Щоб записати найпершу 1 у позиції 40, треба її поле почати з позиції 37. Поле першого числа другого рядка треба почати з позиції 35, третього – 37 тощо. Таким чином, у першому рядку перед полем із числом треба вивести 36 пропусків, у другому – 34 тощо.

Функцію C(m, n) обчислення біноміального коефіцієнта візьмемо з прикладу 5.1. Отже,

program bincoefs;

var m, k, ls:integer;

function c(m, n:integer):integer;

end;

begin

ls:=36;

for m:=0 to 12 do

begin

for k:=0 to ls do write( ' ' );

for k:=0 to m do write( c(m, k):4 );

writeln;

ls:=ls-2;

end;

end.

5.13. Вказівка. Доречно використання exit.

5.14. Вказівка. У подібних ситуаціях корисно скористатися бульовими змінними. Своїми значеннями вони відображають, що з'явилася ознака закінчення вхідної послідовності або виникли умови, за яких продовжувати виконання програми немає сенсу. Ці змінні додаються до умов продовження або завершення циклів (див. приклад 4.6, де використовувалася змінна simp).

Розділ 6

6.2. а)'9'; б)'B'; в)'Z'; г) ' '; д) false; е) 9.

6.4. а) ord(ch)-ord('0'); б) chr(ord('0')+dg).

6.5. а) if ('0'<=ch) and (ch<='9') then dg:=ord(ch)-ord('0')

else if ('A'<=ch) and (ch<='F') then dg:=ord(ch)-ord('A')+10;

б) if (0<=dg) and (dg<=9) then ch:= chr(ord('0')+dg)

else if (10<=dg) and (dg<=15) then ch:= chr(ord('A')+dg-10).

6.10. program simplecalculator2 (input, output);

var first, second : real;

signop : char;

begin

writeln('знаки операцій: +,-,*,/')

writeln('задайте дійсне число:'); readln(first);

while not eof do

begin

writeln('задайте знак операції:'); readln(signop);

if (signop<>'+') and (signop<>'-') and

(signop<>'*') and (signop<>'/')

then begin writeln('хибний знак операції'); continue end;

writeln('задайте дійсне число:'); readln(second);

case signop of

1: first:=first+second

2: first:=first-second

3: first:=first*second

4: if second<>0 then first:=first/second

else

begin

writeln('спроба ділення на 0: ігнорована');

continue

end;

end; {case}

writeln('результат:', first)

end

end.

6.11. Вказівка. Використати оператор вибору варіантів, значеннями селектора в якому є остачі від ділення N на 5.

Розділ 7

7.3. Вказівка. У правій частині виразу з операцією and або or записати виклик функції з побічним ефектом.

7.4. Імена b і c не обов'язково позначають змінні! Див. указівку до 7.3.

7.8. в) Вказівка. Перший спосіб. Точка B лежить усередині багатокутника A1A2A3AnA1, якщо його площа (за модулем) дорівнює сумі площ D BA1A2, D BA2A3, … , D BAn-1An, D BAnA1. Другий спосіб. Точка лежить усередині трикутника, якщо належить непарній кількості D A1A2A3, D A1A3A4, … , D A1An-1An. Тут є "підводні камені" у випадку, коли точка належить відрізку A1Ai. Перевірте!

Розділ 8

8.1. а) ні; б) так; в) так.

Розділ 9

9.1. а) S(n)=n mod 10 + S(n div 10) за n>9, інакше n.

9.2. Доведемо, що

F(n)=n-10 при n>100, інакше F(n)=91.

Перша частина очевидна. Розглянемо значення n від 1 до 100. F(100)= F(F(111))=F(101)=91. За n>90 маємо F(n)=F(F(n+11))=F(n+1). Звідси F(91)=F(92)= … =F(100)=91. За n<91 доведення індуктивне, але не за зростанням, а за спаданням n. База: F(90)=F(F(101))=91. Припущення індукції: за всіх n, 100>n>k, F(n)=91. За означенням та за припущенням індукції маємо F(k)=F(F(k+11))=F(91), тобто 91.

9.3. Вказівка. Зручно скористатися функцією q(m, k), що задає кількість розбиттів числа m, у яких кожний доданок не більший k. Переконатися, що:

q(1, k)=1 за всіх k, q(m, 1)=1 за всіх m,

q(m, k)=q(m, m) за всіх m<k, q(m, m)=q(m, m-1)+1,

q(m, k)=q(m, k-1)+q(m-k, k) за m>k.

Очевидно, що Q(n)=q(n, n).

9.4. Див. задачу 9.1(а).

9.5. а) procedure digits(n : integer);

begin

if n<10 then write(n : 1)

else

begin

write(n mod 10:1); digits(n div p, p)

end

end.

б) достатньо в складеному операторі після else поміняти місцями виклики

write(n mod 10:1) і digits(n div p, p).

9.7. function C(m, n : integer) : integer;

begin

if (m=1) or (n=0) or (n=m) then C:=1

else

if n <= m div 2 then C:= C ( m, n-1 ) * ( m-n+1 ) div n

else C:= C ( m, n+1 ) * ( n+1 ) div ( m-n )

end;

9.10. Такими числами є два послідовні числа Фібоначчі fn та fn+1. Доведення випливає з того, що остачею від ділення більшого з них на менше є fn-1.

Розділ 10

10.1. 5 виразів без знаків операцій, 25 із знаком "+", і стільки ж із знаком "-"; усього 55. Кожний оператор має одне з трьох імен ліворуч і довільний вираз праворуч, тому операторів 165.

10.2. '0'|'1'{'0'|'1'}.

10.3. <дійсне> ::= ('+'|'-')<п-ть цифр>( <порядок> | '.'<п-ть цифр>[<порядок>] )

<п-ть цифр> ::= <цифра>{<цифра>}

<порядок> ::= ('E' | 'e')['+' | '-']<цифра>[<цифра>]

10.4. а) <A>::='c'{'b'}; б) <A>::={'b'}'c'.

10.6. е) <параметри>::=<секція>{';'<секція>}

<секція>::=['var ']<ім'я>{','<ім'я>}:<ім'я типу>

10.7. Немає. Неважко переконатися, що вивідні вирази мають вигляд bncdn, n>0, і мова нескінченна. Оскільки в шуканої БНФ не може бути нетермінала праворуч від ::=, вона повинна містити {, } (інакше мова не буде нескінченною). Символ c не може знаходитися усередині {}, як і символи b і d разом. Тоді в БНФ повинні бути ітераційні дужки з символами b і d окремо. Але тоді разом із виразами, наприклад, bcd і bbcdd будуть вивідні й вирази bcdd і bbcd. Суперечність.

Розділ 11

11.3. а) 0.1, 0.(1), 0.(2), 0.4, 0.8, 0.A.

11.4. а) 0.0625, 0.9375, 255/256=0.99609375; б) 1/27=0.(037), 2/3+2/9=0.(8), 1/3+1/9=0.(4).

11.9. а) 00000000, 00110000, 00111001, 00001101, 00001010, 01000001, 01100001.

11.11. -1 : 1111111111111111;

-8 : 1111111111111000;

-9 : 1111111111110111;

-32767: 1000000000000001;

-32768: 1000000000000000.

11.12. а) minint; б) maxint.

11.13. а) 2-128 » 2.938736× 10-39 та 2126(2-2-23) » 1.701412× 1038.

Розділ 12

12.1. а) За дії означень type ind = 1..20; arr = array[ind] of integer читання масиву та повернення його разом із кількістю прочитаних значень задається такою процедурою:

procedure readarr(var a : arr; var n : ind);

var i : ind;

begin

write('задайте кількість елементів (1..20):'); readln(n);

for i:=1 to n do

begin

write('задайте ', i, '-й елемент:'); readln(a[i]);

end;

end;

Параметри у заголовку мають бути саме параметрами-змінними, оскільки інакше результати читання зникають після закінчення виклику процедури.

12.2. б) Кількість чисел необмежена, тому запам'ятати їх у масиві не можна. Але можна запам'ятати кількості K1, K2, … , K100 кожного з чисел 1, 2, ... , 100 та їх загальну кількість N. Тоді середнє арифметичне M і дисперсію D можна обчислити за формулами:

M=, D=.

Для зберігання кількостей чисел 1, ... , 100 означимо масив K:array [1..100] of integer. Нехай процедура getint задає присвоювання цілого значення з діапазону 1..100 своєму параметрові. Умову завершення читання не уточнюємо:

program MiDi(input, output);

var M, D : real; i, v, N : integer; K : array [1..100] of integer;

procedure getint … end ;

begin

N:=0; for i:=1 to 100 do K[i]:=0;

repeat

getint(v); N:=N+1; K[v]:=K[v]+1;

until умова завершення;

M:=0;

for i:=1 to 100 do M:=M+i*K[i];

D:=0;

for i:=1 to 100 do D:=D+sqr(i-M)*K[i];

writeln(M/N, D/N)

end.

12.4. Нехай навесні поточного року у водоймищі x0 новонароджених риб, x1 риб віком 1 рік, x9 риб віком 9 років. Тоді за умовою наступної весни буде x8/D риб віком 9 років, x7/D – віком 8 років, … , x0/D – віком 1 рік. Новонароджених риб буде (x0/D + x1/D + … + x8/D)× B. Отже, для обчислень необхідно означити масив із десяти компонентів, які зберігають кількості риб відповідного віку. У програмі цей масив ініціюється (x0=M, решта 0), а потім задається повторення обчислень його компонентів Y разів.

12.8. Найпростіший спосіб одержати всі множини з сумою М

перебрати всі можливі підмножини множини {a1, a2, ¼ , an}.

Опишемо цей перебір рекурсивно. Кожна підмножина або містить a1, або ні. Усі множини, що містять a1, одержуються перебиранням підмножин множини {a2, ¼ , an} із додаванням a1 до кожної. Усі інші – перебиранням підмножин із a2, ¼ , an. Узагалі, за довільної зафіксованої підмножини AÍ {a1, ¼ , ai-1} перебирання підмножин множини {ai, ¼ , an} зводиться до перебирання всіх підмножин {ai+1, ¼ , an} із додаванням ai та повторного перебирання без додавання. Нехай множина подається масивом A типу array[1..mn] of integer, де n£ mn, mn=100. Нехай глобальні змінні M і S зберігають задане число й суму елементів поточної підмножини C елементів масиву A. Вона подається масивом B типу array[1..mn] of boolean, в якому B[i]=trueтоді й тільки тоді, коли A[i] належить C. Нехай процедура writset задає друкування поточної підмножини. Отже, пошук потрібних підмножин уточнюється процедурою subsets:

procedure subsets ( i : integer );

begin

S := S + A[i]; B[i] := true;

if S = M then writset;

if i < n then subsets ( i+1 );

S := S - A[i]; B[i] := false;

if i < n then subsets ( i+1 )

end

Дописати програму з необхідними означеннями, ініціалізаціями та викликом subsets(1) залишаємо читачеві.

12.10. а) 00 б) 0

1001 010

210012 0102010

12.11. 1) Рядки рівні, якщо мають ту саму довжину та однакові символи у відповідніх позиціях. Нехай str – ім'я типу, що задає рядки:

function eq(s1, s2 : str) : boolean;

var eqsym : boolean; L1, L2, i : integer;

begin

L1:=length(s1); L2:=length(s2);

if L1=L2 then

begin

eqsym:=true;

for i:= 1 to L1 do eqsym := ( eqsym and (s1[i]=s2[i]) );

eq:=eqsym

end

else eq:=false

end;

Рядок s1 довжини L1 менший лексикографично від рядка s2 довжини L2, якщо

існує i£ min{L1, L2} таке, що s1[i]<s2[i] та s1[j]=s2[j] за всіх j=1, 2, ..., i-1,

або s1 збігається з початком рядка s2, і L1<L2.

Обчислення цих умов подамо функцією lt:

function lt(s1, s2 : str) : boolean;

var eqsym : boolean; L1, L2, Lm, i : integer;

begin

L1 := length(s1); L2 := length(s2);

if L1 < L2 then Lm := L1 else Lm := L2;

if Lm = 0 then lt := (L1 < L2)

else

begin

eqsym := true; i := 0;

while eqsym and (i < Lm) do

begin i := i+1; eqsym := (s1[i] = s2[i]) end

{ (s1[i]<>s2[i]) or (i=Lm) }

lt := (s1[i] < s2[i]) or (s1[i] = s2[i]) and (i < L2)

end;

end;

Зазначимо, що коли один із рядків порожній, його компоненти відсутні, і їх не можна вказувати виразами s1[i] або s2[i] при жодному значенні i. Тому випадок порожнього рядка описується окремо.

3) Якщо заданої позиції в рядку немає, то він залишається без змін.

procedure delsym(var s : str; k : integer);

var ll, i : integer;

begin

ll:=length(s);

if k<= ll then

begin

for i:=k to ll-1 do s[i] := s[i+1]; s[0]:=pred(s[0])

end

end;

4) Нехай із рядка s довжини l=length(s) треба добути підрядок довжини m від його k-го символу. Якщо m+k-1>l, то можна повернути символи від m-го до l-го. Якщо k<1 або k>l, то повернемо порожній рядок.

function substr(s : str; k, m : integer) : str;

var t : str; ll, i, n : integer;

begin

ll := length(s); t := '';

if not ((k<0) or (k>m)) then

begin

if m+k-1>ll then n:=l else n:=m+k-1;

for i:=k to n do t:=t+s[i];

end;

substr:=t

end;

12.17. Нехай s : string подає рядок. У ньому шукаються цифрові послідовності, перетворюються за допомогою процедури val та по одній записуються в масив цілих. У процесі пошуків знищуються пропуски між числами. Підраховується кількість чисел у рядку, і коли вона перевищить 3, рядок має помилкові дані. Пропуски та числа рядка знищуються, і обробка рядка закінчується, коли рядок стане порожнім. Після цього для трьох чисел перевіряються нерівності трикутника, а за іншої їх кількості дані є помилковими. Запишемо лише необхідне:

var s, snum : string ;

p, k, err : integer; blanks : boolean;

a : array[1..3] of longint;

begin

k:=0;

while (s<>'') do

begin

blanks:=true;

while blanks do

if s[1]=' ' then delete(s,1,1)

else blanks:=false;

if s<>'' then

begin

p:=pos(' ', s); {позиція першого пропуска в рядку}

if p=0 then begin snum:=s; s:='' end

else

begin snum:=copy(s, 1, p-1); delete(s, 1, p-1); end;

k:=k+1; if k>3 then break;

val(snum, a[k], err);

if err<>0 then

begin s:=''; k:=-1 end;

end

end;

if k=3 then {перевірка нерівностей трикутника}

if (a[1]+a[2]>a[3]) and (a[1]+a[3]>a[2]) and (a[3]+a[2]>a[1])

then begin writeln('трикутник'); nutri:=nutri+1 end

else writeln('не трикутник');

else writeln('помилкові дані');

12.20. 1. array[0..100] of integer. 2. string[100]. Можливі й інші варіанти.

12.22. Нехай число подається масивом типу bign=array[0..mx]of integer, де mx – ціла стала, наприклад, 100. Компоненти масиву подають значення десяткових цифр числа (цілі від 0 до 9). Молодша цифра подається компонентом масиву з індексом 0. Читання й запис зручно реалізувати за допомогою рядка, довжина якого не більше довжини масиву. При читанні перевіряється, чи всі символи рядка є цифрами, і якщо так, то за рядком обчислюється масив, а якщо ні, то друкується повідомлення.

procedure rdbig(var v : bign);{читання невід'ємного числа}

var s : string[mx+1]; ll, k : integer; ok : boolean;

begin

for k := 0 to mx do v[k] := 0; {ініціалізація масиву}

readln(s); ll := length(s);

{перевірка, чи всі символи рядка є цифрами}

ok := true;

for k := 1 to ll do ok := ok and (s[k]>='0') and (s[k]<='9');

if ok then {заповнення значущими цифрами}

for k := 1 to ll do v[ll-k] := ord(s[k])-ord('0')

else writeln('помилкові вхідні дані')

end;

procedure wrbig(v : bign);{виведення невід'ємного числа}

var s : string[mx+1]; ll, k : integer;

begin

s := '';

{пропускання незначущих нулів у числі}

k := mx;

while (k>0) and (v[k]=0) do k := k-1; {k=0 or v[k]<>0}

{перетворення цілих значень у цифри рядка}

for kk:=k downto 0 do s:=s+chr(v[kk]+ord('0'));

writeln(s)

end;

12.23. а) Тип bign для подання чисел означено у відповіді до задачі 12.22. Додавання в стовпчик відбувається від молодших розрядів до старших. Змінна d зберігає перенос від попереднього розряду. За наявності переносу зі старшого розряду результат додавання надто великий, про що повідомляється.

procedure plusbig(a, b : bign; var c : bign);

var k, d, s : integer;

begin

for k := 0 to mx do c[k] := 0;

d := 0;

for k := 0 to mx do

begin

s := a[k]+b[k]+d;

c[k] := s mod 10; d := s div 10

end;

if d=1 then writeln('bign overflow')

end;

12.25. а) Вказівка. Нехай числа подаються масивами a і b типу bign (відповідь до задачі 12.22), і молодша цифра подається компонентом із індексом 0. Спочатку в компонентах результатного масиву c можна накопичити суми добутків: c[k] є сумою всіх a[i]*b[m], таких, що i+m=k. Далі цифри обчислюються від молодшої, тобто за k=0, 1, ..., mx, з переносами d до старших розрядів:

s:=c[k]+d; c[k] := s mod 10; d := s div 10;

(перенос до нульового розряду d=0).

б) Вказівка. Природніше за все відтворити алгоритм ділення у стовпчик. Спочатку накопичуються старші цифри діленого, поки накопичене число не стане більшим або рівним дільнику. Потім шукається найбільше ціле від 1 до 9, добуток якого з дільником не більше накопиченого числа. Це і є чергова (спочатку – перша) цифра частки. Від накопиченого віднімається добуток її та дільника. Залишається остача. До неї додаються наступні цифри до накопичення числа, не меншого від дільника. Але тепер кожна нова цифра, крім останньої, дає 0 як чергову цифру частки. Знову від накопиченого віднімається добуток дільника з черговою цифрою частки тощо. Нарешті, після того, як використано останню цифру діленого, ми маємо цифри частки й остачу, меншу від дільника.

12.29. Вказівка. Нехай k/m=0.x1...xq(y1...yp) з невідомими цифрами xi, yj. За алгоритмом ділення k на m у стовпчик x1=(10*k) div m із остачею r1=(10*k) mod m. Далі x2=(10*r1) div m із остачею r2=(10*r1)modm тощо. Оскільки різних ненульових остач не більше m-1, то існують k та найменше j, такі, що k<j£ m, і rk=rj. Тоді xj+1=xk+1, xj+2=xk+2 тощо. За xj=xk періодом є xk...xj-1, за xj¹ xkxk+1...xj. Якщо буде обчислено rj=0, то xj+1=xj+2=...=0, тобто періодом є (0). Оскільки в кожному з можливих випадків j£ m, то потрібні два масиви цілих довжиною m для зберігання послідовностей часток і остач від ділення на m.

12.31. а) Нехай матриця подається масивом A типу array[1..M, 1..N], де M, N – цілі сталі. Нехай i, k задають номери двох рядків (1£ i£ M, 1£ k£ M). Тоді обмін місцями рядків описується так:

for j := 1 to N do

begin t := A[i, j]; A[i, j] := A[k, j]; A[k, j] := t end.

12.32. Нехай діють означення

const mn = 50; type matr = array[1..mn, 1..mn] of real.

Напишемо процедуру з параметром-змінною a:matr та цілим параметром n, що задає розмір матриці в межах від 1 до mn. Транспонування – це обмін значень елементів, симетричних відносно головної діагоналі матриці, утвореної елементами A[k,k]. Отже, достатньо перебрати всі піддіагональні елементи та обміняти їх із відповідними наддіагональними:

procedure transpon(var A : matr; n : integer);

var i, k : integer; t : real;

begin

for i := 2 to n do

for k := 1 to i-1 do

begin t := A[i, k]; A[i, k] := A[k, i]; A[k, i] := t end

end;

Ні в якому разі не можна обмін значень елементів задавати операторами

for i := 1 to n do

for k := 1 to n do

begin t := A[i, k]; A[i, k] := A[k, i]; A[k, i] := t end,

оскільки за ними значення A[i, k] і A[k, i] обмінюються двічі, за i>k і за i<k. Внаслідок цього матриця залишається без змін.

12.33. а) Вказівка. При повороті матриці A розміру n´ n на 90° за годинниковою стрілкою відбувається циклічне переміщення значень елементів A[j,k], A[k,n-j+1], A[n-j+1,n-k+1], A[n-k+1,j]. Значеннями j та k треба перебрати одну четверту частину матриці, наприклад: j від 1 до n div 2, а k від 1 до (n div 2 + n mod 2).

12.36. Добутком матриць A і B розмірами m´ n та n´ k є матриця C розмірами m´ k, в якій C[i,j]=A[i,p]*B[p,j]. Опишемо множення процедурою з параметрами, що задають матриці та їхні розміри. Матриці-множники подаються параметрами-змінними, щоб за виконання процедури не створювалися копії матриць-аргументів у локальній пам'яті процедури. Нехай розміри m, n, k належать діапазону 1..50 і матриці подаються масивами типу matr (відповідь до задачі 12.25).

procedure multmt(var A, B : matr; var C : matr; m,n,k:integer);

var i, j, p : integer; s : real;

begin

for i := 1 to m do

for j := 1 to k do

begin

s := 0;

for p := 1 to n do s := s+A[i,p]*B[p,j];

C[i,j] := s

end

end;

Розділ 13

13.1. Процедура readel задає читання з клавіатури значень полів свого параметра-змінної, що є структурою. Одержані значення-структури записуються в типізований файл. Процедура викликається в першому циклі програми доти, поки не прочитано порожній рядок як значення першого поля. Після цього файл читається з початку до кінця, і компоненти його значень-структур виводяться на екран.

13.2. Достатньо після першого reset(f) додати оператор if eof(f) then exit.

13.4. Указання. В умові задачі ніяк не уточнюється тип компонентів файла. Але тип не має жодного значення, тому що з будь-якими файлами можна зв язати файлові змінні типу file of char. Центральним у тілі процедури буде цикл побайтового читання першого файла до його закінчення та запису цих байтів у інший файл.

13.5. Нехай діють означення

f1, f2 : file of char ; ch : char ; ok, endf1, endf2 : boolean.

Напишемо лише головний цикл, після виконання якого з функції повертається значення ok:

reset(f1); reset(f2);

ok:=true;

endf1:=false; endf2:=false;

while ok and not endf1 and not endf2 do

begin

if not eof(f1) then read(f, ch1)

else endf1:=true;

if not eof(f2) then read(f, ch2)

else endf2:=true;

if not endf1 and not endf2 then ok:=ch1=ch2

else ok:=endf1=endf2

end;

13.6. Указання. а) Установити режим читання для обох вхідних файлів та режим запису для нового. Далі два майже однакові цикли читання вхідних файлів та запису в третій без його переустановлення.

б) Скористатися особливістю системи Турбо Паскаль і відкрити для читання обидва файли (!). Прочитати перший файл. Далі в циклі читати байти другого файла до його кінця та записувати їх у перший.

13.7. program outgroup;

uses Crt;

const nrp=5;

type Student = record

sname, name : string[20];

ball: real;

end;

var f : file of Student;

procedure openfile;

var filnam: string;

begin

writeln('Задайте ім''я файла'); readln(filnam);

assign(f, filnam); reset(f);

end;

procedure outfile;

var stud : Student;

i : integer; {лічильник кількості виведених записів}

ch : char;

begin

i:=0; clrscr;

while not eof(f) do

begin

read(f, stud); inc(i);

writeln(stud.sname, ' ', stud.name, ' : ', stud.ball);

if i=nrp then

begin

i:=0;

if not eof(f) then

begin

writeln;

writeln('Продовжувати? "Y"/"N":'); readln(ch);

if (ch<>'n') and (ch<>'N') then clrscr;

end;

end;

end;

readln;

close(f);

end;

begin

openfile; { відкривання файла }

outfile; { виведення файла }

end.

Розділ 14

14.3. а) 1.0,-2.9,13.0,2000.0; б) 1.0,-2.9,2000.0,777.0; в) 1.0,2.9,2000.0,0.0.

14.4. Вказівка. Достатньо в циклі викликати readln(f) доти, поки текст не прочитано – кількість викликів і є числом рядків.

14.5. Ідею розв язання можна подати таким алгоритмом:

while not eof(f) do

begin

прочитати та обробити черговий результат;

відобразити поточні найкращі результати

end.

Нехай черговий результат читається в циклі в поля змінної tr типу

Res=record num, mn, sc: integer end

за викликом readln(f, tr.num, tr.mn, tr.sc). Найкращі результати зберігатимемо в масиві B типу array[0..10] of Res, додавши фіктивний елемент із індексом 0 та нульовими компонентами. Окрема змінна nb показує кількість кращих (від 1 до 10), спочатку nb=0. За nb<10 кожний новий результат має збільшувати значення nb. Перший результат записується в перший елемент масиву B.

Обробка кожного результату полягає в тім, що треба знайти місце для нього в масиві B, зсунути за необхідності гірші від нього в кінець масиву й записати його на потрібне місце. Новий результат не записується, коли nb=10 і він гірший від усіх результатів, наявних у масиві. Ось описання читання та обробки результатів:

nb:=0; B[0].num:=0; B[0].mn:=0; B[1].sc:=0;

while not eof(f) do

begin

readln(f, tr.num, tr.mn, tr.sc);

k:=nb;

while(k>0)and(60*tr.mn+tr.sc<60*B[k].mn+B[k].sc) do k:=k-1;

{k=0 або новий результат гірший k-го}

{ і записується на (k+1)-е місце}

if nb<10 then nb:=nb+1; {збільшення кількості результатів}

for j:=nb downto k+2 do {зсув гірших результатів}

B[j]:=B[j-1];

B[k+1]=tr;

for j:=1 to nb do

writeln(B[j].num, ' ', B[j].mn, ':', B[j].sc)

end;

14.7. Значення змінних: c=chr(13), тобто eol, i=1, r=2.1, s='', s1='', тобто два порожні рядки, s2='lesson', c1='x'. Доступним буде символ 'y'.

14.9. З означення бінарської мови випливає, що кожний початок її слова має літер A не менше, ніж літер B. Тому достатньо лише читати символи рядка по одному та збільшувати лічильник на 1 при читанні A і зменшувати при читанні B. Якщо за початкового значення 0 лічильник у процесі читання не стає від ємним, а в кінці читання має значення 0, то прочитано бінарське слово. В іншому разі прочитано не бінарське слово. Ось описання обробки рядка тексту:

cnt:=0; {лічильник}

ok:=true; {ознака того, що слово бінарської мови}

while not eoln(f) do

begin

read(f, c);

if c='A' then inc(cnt)

else dec(cnt);

if cnt<0 then

begin ok:=false; break end;

end;

readln(f);

ok:=ok and (cnt=0);

write(g, ord(ok)).

14.10. Ідентифікатор – це послідовність букв (літер) та цифр, що починається літерою (латинською). Звідси для його читання треба пропустити всі символи, що не є цими літерами. Прочитавши літеру, слід прочитати всі цифри або літери за нею. Поява іншого символу чи ознаки кінця тексту задає кінець ідентифікатора. Оформимо ці міркування процедурою, другий параметр якої, змінна-рядок, зберігає ідентифікатор. Якщо його немає, значенням цієї змінної залишається '' (порожній рядок). Текст читається посимвольно в змінну c, причому спочатку їй штучно присвоюється пропуск.

procedure getident(var f:text; var s:string));

const Letter:set of char=['a'..'z', 'A'..'Z'];

var LetDig:set of char;

c:char;

begin

c:=' '; s:=''; LetDig:=Letter+['0'..'9'];

while not (s in Letter) and not eof(f) do

read(f, c);

if not (c in Letter) then exit;

repeat

s:=s+c;

if eof(f) then exit;

read(f, c);

if not (c in LetDig) then exit;

until false;

end;

14.11. Нагадаємо, що десятковий запис числа – це "замаскований" многочлен:

= an× 10n + … + a1× 101 + a0

Отже, можна читати по одному символи, що задають число, тобто цифри, та додавати їх згідно схеми Горнера. Якщо v зберігає значення, утворене при читанні попередніх цифр, а значенням ch є нова цифра, то нове значення v обчислюється так: v:=10*v+(ord(ch)-ord('0')). Отже, читання цифр та обчислення цілого невід ємного значення можна задати циклом вигляду

{значенням ch є перша цифра}

v:=0;

while true do

begin

d:= ord(ch)-ord('0');

v:=10*v+d;

if eof(f) then break;

read(f, ch);

if not (ch in Digit) then break;

end;

Тут Digit має значення ['0'..'9']. Як упоратися зі знаком '+' чи '-' попереду цифр, читач поміркує сам.

Наведений цикл не враховує того, що записане в тексті число може не подаватися в діапазоні цілого типу integer чи longint. Розв яжемо це питання для додатних чисел. Найбільшим числом, представним у типі Longint, є 2147483647. Означимо сталу mxl=2147483647. Очевидно,

mxl=10*(mxl div 10)+(mxl mod 10).

Цей вираз дає ключ до розв язання проблеми. Дійсно, якщо в результаті читання попередніх цифр накопичено значення v<mxl div 10, то додавання нової цифри не виведе за межі типу Longint. Так само за v=mxl div 10 та значення нової цифри d<=mxl mod 10 маємо 10v+d£ mxl. Отже, за умови (v<mxl div 10) or (v=mxl div 10)and(d<=mxl mod 10) чергову цифру можна додавати. Порушення цієї умови означає непредставність числа з тексту в типі Longint.

Розглядаючи представність від ємних чисел, слід урахувати, що найбільшим за модулем від ємним числом типу Longint є -mxl-1.

14.12. За наявності коментарів і літералів текст може мати такі стани:

- зовні коментарів і літералів;

- початок коментаря –після дужки '(' у стані "зовні";

- коментар –після '(*' не всередині літерала чи коментаря;

- кінець коментаря – після '*' в коментарі;

- літерал – після апострофа в стані "зовні".

Переходи між станами залежно від останнього прочитаного символу задаються наступною таблицею. Стани позначено відповідно як out, bc, com, enc, lit. У клітинах таблиці ліворуч від знака ';' записано стан, до якого переходить текст після поточного символу; відсутність стану позначає його незмінність. Праворуч записано символ, який видається в текст-копію; відсутність означає, що символ не копіюється. Літерою a позначено будь-який символ, відмінний від круглих дужок, зірочки й апострофа.

 

(

*

)

'

a

out

bc;

; *

; )

lit; '

; a

bc

; (

com;

out; ( )

lit; ( '

out; ( a

com

;

enc;

;

;

;

enc

com;

;

out;

com;

com;

lit

; (

; *

; )

out; '

; a

Написати програму згідно таблиці залишаємо читачу (див. приклад 14.9).

Розділ 15

15.1. program buftxcpy;

const bs=8192;

var buff, bufg: array [1..bs] of byte;

f, g: text;

fname, c:char;

begin

write('Задайте ім'я початкового файла>'); readln(fname);

assign(f, fname);

settextbuf(f, buff);

write(' Задайте ім'я файла-копії>'); readln(fname);

assign(g, fname);

settextbuf(g, bufg);

reset(f); rewrite(g);

writeln('Увага ! Натисніть на "Enter"');

readln;

while not eof(f) do

begin read(f, c);write(g, c) end;

writeln('копіювання закінчено');

readln;

close(f); close(g)

end.

Розділ 16

16.1. Процедура insel задає вставлення елементів із голови списку, тому після першого циклу послідовні елементи списку зберігатимуть значення 3, 2, 1. У такому порядку вони друкуються в другому циклі. При цьому після друкування кожного значення звільняється елемент, що його зберігав, і після циклу список є порожнім.

16.2. Вказівка. Скориставшися лише процедурою new, можна додавати до списка по одному елементу до аварійного завершення програми. Означити елементи розміром у 1000 байтів можна за допомогою масиву символів; після додавання кожного елемента слід друкувати їх кількість у списку.

Розділ 17

17.1. Вісім.

17.2. Нехай діють означення (17.1):

procedure Bubbles2 (var A: ArT; n: Indx);

var i, k: Indx; sw: Boolean;

begin

k:=n; sw:=true;

while (k>=2) and sw do

begin

sw:=false;

for i := 1 to k - 1 do

if A[i] > A[i+1] then

begin swap (A[i], A[i+1]); sw:=true end;

k:=k-1;

end;

end;

Зауважимо, що виконання процедури Bubbles2 будуть зовсім різними на масивах, один із яких уже відсортовано, а другий – “відсортовано навпаки”, наприклад, <4, 3, 2, 1>. У першому разі тіло циклу while виконується лише один раз, а в другому – n-1 раз, причому після кожного порівняння значень відбувається їх обмін.

17.5. Складність фактично оцінено в підрозділі 9.3 – це О(2n).

17.7. а) Наведемо неформальне описання розв'язання задачі. Будемо розглядати послідовні елементи заданого масиву A і запам'ятовувати поточні найменші елементи, що є останніми в підпослідовностях усіх довжин від 1 до деякої максимальної k. Для цього застосуємо допоміжний масив M довжини n. Спочатку M[1]:=A[1]. Далі нехай після обробки елементів A[1], … , A[i-1] створено елементи M[1], … , M[k]. Очевидно, що M[1]££ M[k]. Розглянемо елемент A[i]. Можливі три випадки.

(1) A[i]³ M[k]. A[i] продовжує підпослідовність довжини k, тобто є останнім у підпослідовності довжини k+1. У цьому випадку збільшуємо максимальну довжину k і запам'ятовуємо A[i]: k:=k+1; M[k]:=A[i].

(2) A[i]<M[1]. Він є новим найменшим елементом, яким може закінчуватися підпослідовність довжини 1. Тоді M[1]:=A[i].

(3) M[1]£ A[i]<M[k]. Це означає, що A[i] може продовжити підпослідовності довжини 1, 2, … до деякого j-1, такого, що M[j-1]£ A[i]<M[j], тобто A[i] стає новим найменшим елементом у підпослідовності довжини j. Отже, після пошуків відповідного значення j змінюємо M: M[j]:=A[i].

Оцінимо складність наведеного алгоритму. Обробка першого елемента потребує сталої кількості елементарних дій. Далі на кожному з n-1 кроків максимум дій вимагає випадок (3). Оскільки масив M весь час залишається впорядкованим, то пошук у ньому вимагає O(logn) дій. Таким чином, складність цього алгоритму має оцінку O(nlogn). Його уточнення залишаємо для удосконалення техніки програмування.

б) Аналогічно будемо розглядати послідовні елементи заданого масиву A, але для всіх можливих довжин j від 1 до k запам'ятовувати будемо поточні підпослідовності довжини j, що закінчуються найменшими елементами. Для цього потрібен масив S розмірами n´ n, у першому рядку якого зберігається підпослідовність довжини 1, в другому – довжини 2, … , в k-му – довжини k. Діагональні елементи масиву S зберігають останні елементи цих підпослідовностей. Спочатку S[1, 1]:=A[1]. Далі нехай після обробки елементів A[1], … , A[i-1] створено рядки S[1], … , S[k]. Очевидно, що S[1, 1]££ S[k, k]. Розглянемо елемент A[i]. Можливі три випадки.

(1) A[i]³ S[k, k]. A[i] продовжує підпослідовність довжини k, тобто є останнім у підпослідовності довжини k+1. У цьому випадку копіюємо рядок S[k] в S[k+1], запам'ятовуємо A[i] в S[k+1, k+1] та збільшуємо на 1 максимальну довжину k.

(2) A[i]<S[1, 1]. Він є новим найменшим елементом, яким може закінчуватися підпослідовність довжини 1. Тоді S[1, 1]:=A[i].

(3) S[1, 1]£ A[i]<S[k, k]. Це означає, що A[i] може продовжити підпослідовності довжини 1, 2, … до деякого j-1, такого, що S[j-1, j-1]£ A[i]<S[j, j], тобто A[i] стає новим найменшим елементом у підпослідовності довжини j. Отже, після пошуків відповідного значення j змінюємо S: копіюємо рядок S[j-1] в рядок S[j] та запам'ятовуємо A[i] в S[j, j].

Неважко зрозуміти, що в разі неспадаючої послідовності, утвореної елементами масиву A, доведеться заповнювати всі рядки у масиві S. Таким чином, доведеться виконати O(nlogn)+O(n2) дій, тобто складність буде мати оцінку O(n2). Негативною рисою цього алгоритму є використання допоміжного масиву розмірами n2.

Наведемо інше розв'язання цієї задачі. Оцінкою складності буде також O(n2), але допоміжні масиви матимуть розмір 2n. Обчислимо для кожного елемента A[i] максимальну довжину неспадаючої підпослідовності, яка ним починається, а також індекс її наступного елемента. Якщо ця довжина 1, то наступним буде вважатися сам елемент. Нехай довжини запам'ятовуються в масиві L, наступні елементи – в масиві X. Спочатку всі L[i]=1, X[i]=i. Очевидно, що для A[n] ці величини залишаються незмінними. Далі нехай обчислено всі всі L[i+1], L[i+2], … , L[n] та X[i+1], X[i+2], … , X[n] і розглядається A[i]. Переберемо всі A[i+1], A[i+2], … , A[n]. Можливі два випадки.

(1) Усі вони менші від A[i]. Тоді L[i] та X[i] залишаються без змін.

(2) Серед них є не менші від A[i]. Кілька з них мають найбільше відповідне значення в масиві L. З цих елементів виберемо останній A[k], оскільки очевидно, що саме він найменший серед них. Тоді кладемо L[i]=L[k]+1, X[i]=k.

Обчислення, описані в обох випадках, можна уточнити так:

fnd:=false; k:=i+1;

while not fnd and (k<=n) do

if A[i]<=A[k] then begin fnd:=true; beg:=k end

else k:=k+1;

if fnd then

begin

mxl:=L[i]; nx:=beg;

for k:=beg+1 to n do

if (L[k]>mxl ) and (A[k]>=A[i]) then

begin mxl:=L[k]; nx:=k end else

if L[k]=mxl then nx:=k;

L[i]:=L[nx]+1; X[i]:=nx

end

Як бачимо, обробка A[i] вимагає перегляду n-i наступних елементів, що вимагає O(n) елементарних дій. Таким чином, формування масивів L і X має складність O(n2).

Далі за один прохід масивом L відшукується останній серед максимальних L[k]. Саме з нього починається "найлегша" з найдовших послідовностей. Далі за допомогою масиву X вона друкується в остаточному вигляді. Усе це має складність O(n). Отже, оцінкою складності наведеного алгоритму є O(n2).

17.9. Нехай сортується масив A: array[1..n] of integer, процедура swap задає обмін значень її параметрів, знапченнями змінних i, j, k, f є індекси. Наведемо лише оператори тіла процедури сортування.

for i :=2 to n do

begin

j := i;

f := j div 2;

while (j>1) and (A[f]<A[j]) do

begin

swap(A[f], A[j]); j := f; f := j div 2

end;

end;

for k := n downto 2 do

begin

swap(A[1], A[k]);

i := 1;

repeat

f := i; j := f*2;

if (j<k) and (A[f] < A[j]) then i := j;

j := j+1;

if (j<k) and (A[i] < A[j]) then i := j;

if i <> f then swap(A[f], A[i]);

until f=i

end;

17.11. а) Нехай getreal – функція, з виклику якої повертається черговий елемент числової послідовності. Для зберігання найменших елементів означимо масив A:array [1..1000] of real. Числа в масиві зберігаються за зростанням, тобто A[1] має найменше значення, A[2]>A[1] тощо. Запишемо лише оператори:

A[1]:=get; tt:=1; {tt – кількість зайнятих елементів A}

while ознака продовження послідовности do

begin

v:=getreal;

{пошук місця для нового значення}

fnd:=false; k:=1;

while not fnd and (k<=tt) do

if v>A[k] then k:=k+1 else fnd:=true;

{fnd or k>tt}

if fnd then

if v<>A[k] then

begin

{зсунути елементи від k-го до кінця}

if tt<1000 then tt:=tt+1;

for j:=tt downto k+1 do A[j]:=A[j-1];

{саме в такому порядку!}

A[k]:=v

end

else

if tt<1000 then

begin tt:=tt+1; A[tt]:=v end

end.

17.13. Нехай списки подано вказівниками на їх голови. Якщо списки не порожні, то визначається, яке із значень у перших елементах менше. Воно стає черговим значенням у результатному списку, елемент у початковому списку пропускається, і задача зводиться до такої ж, тільки один із списків став на один елемент коротше. Якщо один із списків порожній, то беруться значення з другого. Нехай за дії означень типів str, Tple і Tle злиття відбувається без створення нового списку.

Варіант із використанням рекурсії оформимо функцією, з якої повертається вказівник на голову списку-результату злиття.

function mrgli(h1, h2 : Tple) : Tple;

begin

if (h1=nil) and (h2=nil) then mrgli:=nil else

if (h1=nil) then mrgli:=h2 else

if (h2=nil) then mrgli:=h1 else

if h1^.v<h2^.v then

begin h1^.next:=mrgli(h1^.next, h2); mrgli:=h1 end

else begin h2^.next:=mrgli(h1, h2^.next); mrgli:=h2 end

end;

Недоліком цієї функції є те, що за рахунок рекурсивних викликів і параметрів-значень створюється магазин вказівників, яких удвічі більше ніж елементів у обох списках, узятих разом. Запишемо варіант без рекурсії:

function mrgli(h1, h2 : Tple) : Tple;

var p, h: Tple;

begin

new(h); p:=h; {створено фіктивний елемент перед списком}

while (h1<>nil)and(h2<>nil) do

if h1^.v<h2^.v then

begin p^.next:=h1; p:=p^.next; h1:=h1^.next end

else begin p^.next:=h2; p:=p^.next; h2:=h2^.next end;

{(h1=nil) or (h2=nil)}

if h1=nil then p^.next:=h2

else p^.next:=h1;

{фіктивний елемент звільняється}

mrgli:=h^.next; dispose(h)

end;

Розділ 19

19.1. Вказівка. Достатньо в програмі побудови розміщень ферзів з функції test вилучити перевірку займання нової діагоналі.

19.3. Установимо зв'язок між кількістю t викликів test і кількістю d викликів deps за розміру шахіівниці n. У дереві розміщень кожна з вершин, окрім кореневої, перевіряється у виклику test, тому t+1 є кількістю вершин у дереві. Процедура deps виконується для кожної вершини, що не є листком. Але кожна з d проміжних вершин породжує n вершин, тому загальна кількість породжених вершин дорівнює d× n. Тоді t=d× n.

19.4. а) Кожне розміщення тур відповідає перестановці чисел 1, 2, ... , n, тому розміщень n! і складність задачі не менше O(n!). Більш точна оцінка вимагає серйозного аналізу і тут не наводиться.

Розділ 20

20.1. Наведемо ЗПЗ: а) a b cb * c / + ; б) a b c d * + –; в) a b + c d + – .

20.2. Наведемо результати обчислень: а) -10; б) 1; в) 0.

Розділ 21

21.1. б) 0+1(0+1)*;

в) (0+1)(0+1)*.(0+1)(0+1)*;

г) Нехай алфавіт складється з 0 і 1: ‘(0+1+’’)*’;

д) M*(e + (e + D)(C + CC + CCC) + (e + C)D + CM)(e + (e + L)(X + XX + XXX) + (e + X)L + XC)(e + (e + V)(I + II + III) + (e + I)V + IX).

21.2. б) Наведемо виведення слів aabb, ababab: SÞ aSbÞ aaSbbÞ aabb, SÞ SSÞ SSSÞ *ababab. Слово abbaab не виводиться, оскільки з вигляду продукцій випливає, що кількість символів a в кожному початковому відрізку вивідного слова не менше кількості символів b.

21.4. а) Означимо нетермінали C00, C01, C10, C11, індекси яких подають парність (0) або непарність (1) кількості символів a і b. Початковим є C00. Означимо праволінійні продукції C00® aC10, C00® bC01, C10® aC00, C10® bC11, C01® aC11, C01® bC00, C11® aC01, C11® bC10, C11® e . Неважко переконатися, що кількості обох символів у ланцюжку w непарні тоді й тільки тоді, коли C00Þ *wC11. Але wC11Þ w. Отже, ланцюжок є вивідним тоді й тільки тоді, коли C00Þ *w. Ліволінійна граматика означається аналогічно.

21.6. в) { S® aSa | bSb | e }; г) { S® aSb | bSa | SS | e }.

21.7. д) first(A)={a, 0}, first(B)={a}, follow(A)={b}, follow(B)={b}, first(S)={a, 0}. Оскільки A і B – праві частини продукцій із S ліворуч, то LA(1)-умови порушено.