Then begin

Begin

Begin

End.

Begin

Then

Repeat

Begin

End.

Begin

Begin

End.

Begin

Begin

End.

Begin

Begin

Begin

End.

Begin

Begin

Begin

Begin

Begin

End.

Begin

Begin

End.

Begin

Begin

End.

Begin

Begin

End.

Begin

Begin

Begin

Begin

End.

Begin

Begin

Begin

Begin

Begin

Var

End.

Begin

Begin

Begin

Begin

End.

Begin

Begin

Begin

End.

Begin

Begin

Begin

End.

Begin

Begin

End.

Begin

Begin

Begin

Begin

Туре

Var

Туре

Var

Var

End.

Repeat

Begin

End.

Repeat

Begin

End.

Repeat

Begin

Else

Begin

End.

Repeat

Begin

Else

Begin

End.

Repeat

Begin

End.

Begin

Begin

End.

Begin

End.

Begin

End.

Begin

Begin

End.

Begin

Begin

Clrscr;

Write(‘Введіть початкову кількість скринь з золотом: ‘);

Readln(n);

Write (‘ Введіть щорічний прибуток Чахлика: ‘);

Readln(m);

Write(‘Введіть «потреби» Василини Премудрої: ‘);

Readln(k);

Sum:=п;{Початковий «капітал» Чахлика}

Years:=18;{Початковий вік Василини}

While Sum<=k do

Sum:=Sum+m;

Years:=Years+1;

End;

Writeln(‘Василиях вже виповнилося ‘,Years,’ років.’);

Readkey;

ЗАДАЧА № 197

Умова: Дано натуральне число п. Визначити суму цифр у числі. Для розв’язку цієї задачі використаємо такий штучний прийом: щоб знайти суму цифр, ми повинні «брати» цифри по одній і додавати їх однадо одної, а потім використану цифру «відкидати». Це нам дозволять зробитиоперації ділення націло та знаходження залишку від цілочисельногоділення. Так, при діленні числа націло на 10 остання цифра числа буде«відкидатися», а при знаходженні залишку від ділення націло ми виділяємоостанню цифру числа. Тобто: 123 div 10 = 12 3928 mod 10 = 8.

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

Program Example_197_2;

Uses crt;

Var n:longint; {N - дане число}

Sum:byte; {Sum - сума цифр числа}

Clrscr;

Sum:=0; {Сума цифр числа спочатку дорівнює 0}

Write(‘Введіть ціле число: ‘);

Readln(N);

N:=abs(N);

While N>0 do

Sum:=Sum+N mod 10; {Знаходження суми цифр}

N:=N div 10; {«Відкидання» останньої цифри числа}

End;

Writeln(‘Sum= ‘,Sum);

Readkey;

ЗАДАЧА №204

Умова: Дано ціле число т > 1. Знайти найбільше число к, при якому виконується умова 4к < т.

Program Example_204;

Uses crt;

Var m,k,Rez:longint; {Rez - обчислення степеню 4}

Clrscr;

Write(‘Введіть значення m (m>1): ‘);

Readln(m);

Rez:=1;

k:=0;

While Rez<m do

Begin k:=k+l; Rez:=Rez*4; End;

Writeln(‘k= ‘,k);

Readkey;

ЗАДАЧА № 208

Умова: Під час обчислення результатів деяких експериментів виникає необхідність отримання результату із заданою похибкою. Нехай результатом є нескінченна сума, що задається певною формулою, і відома похибка e (e > 0) для знаходження наближеного значення результату. Будемо вважати, що необхідна точність досягнута, коли додавання наступного доданку змінює суму на величину, меншу за e. Обчислити:

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

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

Program Example_208_1;

Uses crt;

Var і:word;

Rez,Epsilon:real; {Rez - результат обчислень, Epsilon - похибка}

Clrscr;

Rez:=0; {Початкове значення дорівнює 0, тому що результат є накопиченням суми}

Write(‘Введіть значення похибки (Е>0): ‘);

Readln(Epsilon); і:=1;

While 1/sqr(i)>Epsilon do

Begin Rez:=Rez+1/sqr(i) i:=i+1; End;

Writeln(‘Rez= ‘,Rez:8:2); Readkey;

ЗАДАЧА №212

Умова: Обчислити значення числа тс, використовуючи формулу

Знайти, кількість доданків що дає значення числа тс з точністю до 3 знаків.

Розв’язання: Для організації циклу з передумовою в цій задачі необхідно мати еталон числа тс для порівняння з нескінченною сумою. Візьмемо за цей еталон значення вбудованої функції Рі. Крім того, за умовою задачі нам необхідно отримати результат із точністю до третьої цифри після коми. Пропоную для цього стандартне число π і отриману нескінченну суму помножити на число 1000 та округлити результат за допомогою функції round (отриману суму, крім того, необхідно ще помножити на 4, оскільки сама сума є чвертю числа π). Зверніть увагу також на те, що в нескінченній сумі доданки, що стоять на парних місцях, додаються зі знаком «+», а доданки на непарних місцях—віднімаються від суми. Тобто, залежно від номера доданку (парний чи непарний) ми організовуємо знакочергування у нескінченній сумі. Програма для обчислення числа тс за допомогою нескінченної суми наведена нижче:

Program Exarople_212;

Uses crt;

Var і,n:word;

{і - параметр циклу, п - кількість доданків}

Rez_Pi:real; {Rez_Pi - обчислене значення числа Рі}

Clrscr;

Rez_Pi:=0;

і: =1; {і — значення знаменника першого доданkа}

п:=0; {п - доданків ще нема}

while round(pi*1000)=round(Rez_Pi*4000) do

If n mod 2=0 Then Rez_Pi:=Rez_Pi+1/i

Else Rez_Pi:=Rez_Pi-1/i;

i:=i+2;

n:=n+1;

End;

Writeln(vКількість необхідних доданків - ‘,n);

Writeln(“Порівняйте значення Рі: ‘);

Writeln(‘Результат обчислень програми: ‘,Rez_Pi:8:3);

Writeln(‘Вбудована функція: ‘,Рі:8:3);

Readkey; {Затримка зображення на екрані}

Домашнє завдання

• Виконати задачі № 185, № 198 (3), № 200 (1), № 203 (3), № 205, № 208 (2).

ЗАНЯТТЯ 21. Цикли з післяумовою

Мета заняття: навчити використовувати цикл з післяумовою для розв’язування типових задач.

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

ЗАДАЧА №179

Умова задачі: На дверях ліфта висіло загрозливе попередження про те, що двері самі зачиняються в той самий момент, коли зайвий за вагою пасажир переступить поріг ліфта. Котрий пасажир постраждає, якщо ліфт витримує вагу не більше S кг, а вага пасажирів, що стоять у черзі до ліфта, дорівнює відповідно a1, а2, а3,... ап?

Розв’язання: У цій задачі зручніше використовувати цикл з післяумовою, тому що спочатку необхідно дати можливість «увійти» пасажиру в ліфт, а потім перевіряти, чи витримає його ліфт. Умовою виходу з циклу буде перевищення сумарної ваги пасажирів, що увійшли в ліфт, деякого заданого критичного значення. Для зберігання ваги чергового пасажира в цій задачі ми будемо використовувати одну й ту саму змінну (А), оскільки після перевірки вага пасажира нас уже не цікавить. Програма має вигляд:

Program Ехаmрlе_179;

Uses crt;

Var N:word; {I - номер пасажира, що увійшов у ліфт}

Sum,A,S:real; {Sum - сумарна вага пасажирів, що знаходяться в ліфті, А - вага чергового пасажира, що увійшов до ліфта, S - критична вага, що може бути піднята ліфтом}

Clrscr;

Sum:=0;

N:=0; {На початху роботи програми в ліфті немає пасажирів}

Write(‘Введіть критичну вагу, що піднімає ліфт: ‘);

Readln(S);

Write(‘Введіть вагу чергового пасажира: ‘);

Readln(A);

Sum:=Sum+A;

N:=N+1;

Until Sun>S;

Writeln(‘Постраждає ‘,N,’-й пасажир.’);

Readkey;

ЗАДАЧА №181

Умова: Капосний папуга навчився висмикувати у дідуся Василя волосся, яке ще залишилося у того на голові. Почавши з однієї волосини, він щодня збільшував порцію вдвічі. Через скільки днів дідусеві не знадобиться гребінець, якщо спочатку в нього на голові було аж N волосин?

Розв ‘язання: Аналогічно до попередньої задачі, аналізувати наявність волосся на голові слід після того, як папуга вже висмикнув чергову порцію волосся. А «знущання» над дідусем скінчиться тоді, коли гребінець йому стане непотрібним, тобто кількість волосся на голові дорівнюватиме нулю. Зверніть увагу, що в цій задачі змінна S використовується для підрахунку чергової порції волосся, що підлягає висмикуванню капосним папугою.

Program Example_181;

Uses crt;

Var S,N,Sum:longint; {S - кількість волосся, що буде висмикнутим, Sum - кількість волосся, що залишилося в дідуся на голові, N - початкова кількість волосся}

Day:word;

{Day — номер дня, який папуга знущається над дідусем}

Clrscr;

Write(‘Початкова кількість волосся в дідуся на голові: ‘);

Readln(N);

If N=0

Then writeln(‘Дідусь уже лисий, папузі нічого робити!’)

Day:=0;

Sum: =N;

S:=1;

{Початкова кількість волосся, що буде висмикнуте папуго»}

Sum:=Sum-S; {Зменшення дідусевого волосся}

S:=S*2;

Day:=Day+1; {Підрахунок номеру дня}

Until Sun<=0;

Writeln(‘Папуга знущався над дідусем ‘,Day,’ днів.’);

End;

Readkey;

ЗАДАЧА №209

Умова: На скільки років необхідно покласти в банк суму X грошових одиниць, щоб одержати суму N грошових одиниць (N > X), якщо банк нараховує 200 % річних?

Розв’язання.Очевидно, що умовою виходу з цього циклу буде отримання заданої суми грошей. Якщо за умовою задачі N > X, то кожну перевірку ми будемо виконувати після того, як до вкладеної суми додамо щорічний банківський процент. Отже, програма має вигляд:

Program Example_209;

Uses crt;

Var X,N:real; {X - початковий внесок, N - бажана сума} Rezrreal; {Rez - результуюча сума на рахунку} Years:longint; {Years - термін, протягом якого сума перебувала в банку}

Clrscr;

Write(‘Введіть початкову суму внеску: ‘);

Readln(X);

Write(‘Введіть бажану суму внеску: ‘);

Readln(N);

If N<=X

Then writeln(‘Bn вже маєте бажану суму!’)

Rez:=X;

Years:=0;

Rez:=3*Rez;

{200% річних збільшують за рік внесок втричі}

Years:=Years+l;

Until Rez>=N;

Writeln(‘Ви отримаєте бажану суму через ‘,years,’ років’);

End;

Readkey;

ЗАДАЧА №231

Умова: Скласти програму, яка б допомогла працівникам ДАІ визначати кількість порушників перевищення швидкості на трасі, якщо відомо, що на даному проміжку траси встановлено обмеження на швидкість Vmax, a прилад фіксує швидкість автомобілів V1 V2,..., Vn.

Розв ‘язання: В даній задачі ніяким чином не обумовлена умова виходу з циклу, тому є пропозиція: процес підрахування порушників необхідно закінчити тоді, коли чергове введене число буде недодатнім (дійсно, з від’ємною або нульовою швидкістю автомобіль рухатися не може). Для тимчасового зберігання значення швидкості чергового автомобіля ми будемо знову використовувати одну змінну. Програма, що виконує задані обчислення, має наступний вигляд:

Program Example_231;

Uses crt;

Var V,Vmax:real; {V - швидкість автомобіля, Vmax - максимально дозволена швидкість}

Count:longint; {Count - кількість порушників}

Clrscr;

Count:=0; {На початку роботи порушники відсутні}

Write(‘Значення максимально дозволеної, швидкості: ‘);

Readln(Vmax);

Vmax:=abs (Vmax); {Знаходження модуля для виключення помилки введення від’ємної максимальної швидкості}

Write(‘Значення швидкості чергового автомобіля: ‘);

Readln(V);

If V>Vmax then Count:=Count+1;

Until V<=0;

Writeln(‘Кількість порушників ‘,Count);

Readkey;

ЗАДАЧА №251

Умова: Дано натуральне число п і дійсні числа а1 а2,.... ап. Відомо, що в заданій послідовності є хоча б одне нульове значення. Розглядаючи члени послідовності, що розташовані до першого нульового члена, визначити середнє арифметичне членів.

Розв ‘язання: Для розв’язку цієї задачі значення п є зайвим, якщо серед членів послідовності буде хоча б один нульовий елемент, тому ми враховувати цю змінну не будемо (хоча дітям можна пояснити, що у випадку відсутності нульового члена послідовності змінна n може використовуватись як додаткова для виходу з циклу, щоб виключити зациклення програми).

Отже, оскільки ми не знаємо, коли зустрінеться нульовий елемент, у програмі знаходиться сума всіх чисел послідовності (змінна sum ) та кількість введених чисел (змінна count ), а після виходу з циклу вже знаходиться безпосередньо середнє арифметичне членів послідовності як результат ділення суми на кількість чисел, зменшену на одиницю. Зменшення на одиницю відбувається тому, що фактично в тілі циклу буде підраховано один зайвий нульовий елемент (останній).

Програма має вигляд

Program Example_251_5;

Uses crt;

Var count:word; {count - кількість членів послідовності до першого нульового елемента}

a,Sum:real; {a - черговий член послідовності. Sum - сума членів послідовності до першого «0»}

SA:real; {SA - середнє арифметичне}

Clrscr;

Sum:=0;

count:=0; {Початкові значення дорівнюють «0»}

write(‘Введіть черговий член послідовності: ‘);

readln(a);

Sum:=Sum+a;

count:=count+1;

until a=0;

SA:=Sum/(count-1);

Writeln(‘Середнє арифметичне = ‘,SA:8:2);

Readkey;

Домашнє завдання:

• Повторити теоретичний матеріал із роботи циклу з післяумовою;

• Виконати задачі №185, №187, №208(5), №234(4), №239(4), №251(4).

ЗАНЯТТЯ 22. Табличні величини

Мета заняття: дати поняття табличних величин та їх опису мовою програмування. Поняття лінійних таблиць, введення елементів таблиць та виведення їх на екран.

Теоретичний матеріал

Поняття таблиці було введене програмістами для запам’ятовування та обробки великих наборів однотипних даних. Наприклад, якщо ми хочемо знайти середній бал кожного учня класу з інформатики за чверть, нам слід знайти суму дуже великої кількості оцінок. Як зберігати всі ці оцінки? Зарезервувати для цього 40 (а може і більше змінних)? Це дуже незручно. Ось тут і знадобиться такий структурований тип даних, як таблиця, або інакше — масив.

Масив — це структура даних, що являє собою однорідну (за типом), фіксовану (за розміром і конфігурацією) сукупність елементів, упорядкованих за номерами.

Таблиця визначається ім’ям (ідентифікатором) і кількістю індексів (номерів), що потрібні для визначення місцезнаходження необхідного елементу масиву. Ім’я масиву є єдиним для всіх його елементів.

У програмуванні кількість індексів таблиці називають розмірністю, кількість дозволених значень кожного індексу — діапазоном, а сукупність розмірності та діапазону — формою масиву.

Оскільки конфігурація елементів масиву фіксована, то до окремого елементу можна звертатися за допомогою одного або кількох індексів. У якості індексів можуть використовуватися константи або змінні порядкових типів. Елементами можуть бути як прості змінні будь-яких типів, так і змінні складених типів (масивів, рядків і т.д.), тобто може існувати масив масивів, масив рядків тощо. Глибина вкладеності цих типів — довільна, тому кількість індексів не обмежена, але сумарна довжина структури не повинна перевищувати дозволені мовою Паскаль 64 Кбайти. В пам’яті ПК всі елементи масиву зберігаються послідовно, тому при переході від молодших до старших адрес першим змінюється самий правий індекс. Порядок роботи з масивом:

1) оголосити масив у розділі описів, вказавши його розмір і тип елементів, що в нього входять (тобто приготувати місце в пам’яті, де будуть зберігатися значення елементів);

2) заповнити необхідними значеннями масив для розв’язування задачі;

3) вивести масив на екран для контролю правильності роботи з ним;

4) робота з даним масивом;

5) виведення результатів роботи.

У розв’язуванні задач використовуються одновимірні та двовимірні масиви. Масиви більшої розмірності на практиці майже не зустрічаються.

Одновимірний масив. Одновимірний масив інакше ще називають лінійним масивом або вектором. Кожному його елементу ставиться у відповідність один індекс. Для початку роботи з масивом готуємо місце в пам’яті, для чого описуємо його в розділі оголошень.

Масив А

Формат опису (1 варіант):

<ім’я>: array [<розмірність>] of <базовий тип елементів>;

Для опису масиву можна використовувати попередньо визначену константу:

Const Gl=40;

<ім’я>: array[1..G1] of <6азовий тип елемеятів>;

Приклади описів:

Const n = 100;

Var A:array[1..n] of real; В:array[1..100] of integer;

Першим описаний масив, до складу якого входять 100 дійсних чисел, а другим — масив із 100 цілих чисел. Крім того, масив можна описати за допомогою опису відповідного типу.

Формат опису (2 варіант):

<ім’я типу> = array [<розмірність>] of <базовий тип елементів>;

<ім’я масиву>: <ім’я типу>;

Приклад:

Massiv = array [1..20] of longint;

Var M: Massiv;

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

[<ім’я масиву> <йоію_індекс>]

наприклад:

М[6] — шостий елемент масиву М;

А[10] — десятий елемент масиву А;

В[і] — і-тий елемент масиву В.

Для роботи з масивом необхідно використовувати будь-який оператор повторення, тому що кожна дія з його елементами виконується однаково. Мова Паскаль не має засобів введення-виведення усіх елементів масиву водночас, тому введення і виведення значень робиться послідовно.

Методи заповнення одновимірного масиву:

1) за формулою:

for i:=1 to n do M[i]:=і*і-10 {або будь-яка інша формула};

2) з клавіатури:

for i:=1 to n do

write (‘ Введіть М[‘і,’]: ‘); readln(M[i]); end;

3) випадково (генератором випадкових чисел) із проміжку [А, В]:

for i:=1 to n do M[i]:=random(B-A)+A;

Методи виведення елементів одновимірного масиву на екран

1) виведення у стовпчик:

for i:=1 to n do writeln(M[i]);

2) виведення у рядок:

for i:=1 to n do write(M[i]:5);

При виведенні елементів масиву у рядок бажано зазначити формат виведення, наприклад, write(М[і]: 10:3) — для дійсних чисел або write(М[і]: 5) —для цілих.

Можна об’єднувати в одному циклі кілька етапів розв’язування задачі. Наприклад, заповнення масиву та виведення елементів масиву для контролю на екран.

Розглянемо типові завдання з одновимірними таблиць.

ЗАДАЧА № 293 (1)

Умова: Записати наведені нижче послідовності змінних з індексами у вигляді послідовностей елементів масивів: (сj), де (j =-3, -2,..., 3).

Очікувана відповідь: с[-3], с[-2], с[-1], с[0], с[1], с[2], с[3].

ЗАДАЧА №293 (4)

Умова: Записати наведені нижче послідовності змінних з індексами у вигляді послідовностей елементів масивів: (Qj), де (1 = n +1, n + 2,..., n + 5).

Очікувана відповідь: Q[n + 1], Q[n + 2], Q[n + 3], Q[n + 4], Q[n + 5].

ЗАДАЧА № 297

Умова: Нехай нижня та верхня межі індексів одновимірного масиву S дорівнюють відповідно -10 та 32. Визначити значення індексів елементів масиву S, порядковими номерами яких є:

№ варіанту	Завдання	Відповідь
		S[-10]
		S[-8]
		S[-1]
		S[1]
		S[21]

ЗАДАЧА № 299

Умова: Нехай елементи одновимірного масиву А[1..1О] набувають відповідно значень -5, -3, -1, 1, 3, 5, 7, 9, 11, 13. Які значення буде надруковано в результаті виконання таких операторів:

№ варіанта	Завдання	Відповідь	Примітка
	For i:=l to 5 do Writeln(A[i+5])		Друкується тільки п’ять останніх елементів масиву, тому що змінна циклу змінюється від 1 до 5, а індекс елементів масиву від 6 (1+5) до 10 (5+5)
	i:=l; While A[i]<0 do Begin i:=i+l; Writeln(A[i]) End;	-5 -3 -1	Друкуються тільки від’ємні елементи масиву, тому що умова виходу з циклу така, що коли А[і]<=0, він припинить свою роботу.
	i:=l; repeat i:=i+l; Writeln(A[i]) until A[i]>=0;	-3 -1	Елементи масиву друкуються до першого додатного значення зліва направо. 1-й елемент масиву не друкується тому, що в тілі циклу спочатку змінюється індекс, і виконується друк.

ЗАДАЧА № 311 (2)

Умова: Дано одновимірний масив цілих чисел А[і], де і = 1, 2,...n. Вивести елементи масиву з парними індексами.

Разв’язання: В даному випадку незручно користуватися для виведення на екран елементів з парними індексами циклом з параметром, тому що він дозволяє зміну індексу тільки на одиницю. Тому пропонуємо скористатися циклом з перед — або післяумовою.

Program Example_311_2;

Uses crt;

Var N,і:word; {N — кількість елементів масиву, і — змінна циклу)

A:array[1..100] of longint; {A — заданий масив}

Clrscr;

Write(‘Введіть кількість елементів масиву (<100):’);

Readln(N);

For i:=1 to N do

А[і]:=random(300); {Заповнення масиву випадковими числами}

{Виведення масиву на ехран для контролю правильності роботи програми}

Write(A[i]:5);

End;

Writeln; {Переведення курсору на наступний рядок}

і:=2;

while i<=N do

Write(A[i]:5);

i:=i+2; {Змінна циклу змінюється на 2, щоб вибрати тільки парні елементи}

End;

Readkey; {Затримка зображення на екрані}

Домашнє завдання

• Прочитати сторінки 117—119 запропонованого підручника.Задачі № 292, № 293 (останні), № 295 (останні), № 297, № 299 (останні), № 3 10, № 3 1 1(3).

ЗАНЯТТЯ 23. Обробка лінійних таблиць

Мета заняття: навчити розв’язувати типові задачі з обробки лінійних таблиць.

На початку заняття бажано зробити опитування за матеріалом попереднього заняття та повторити тему «Команда повторення», особливо різновид циклу — цикл з параметром. Далі рекомендується розглянути методирозв ‘язування типових задач з обробки лінійних таблиць. Зверніть увагу на те, що дуже велика кількість задач з обробки масивів потребує виконання однотипних дій з усіма елементами, тому зручно в цих випадках використовувати цикл із параметром для організації повторення.

ЗАДАЧА № 300

Умова: Барон Мюнхгаузен, вийшовши на екологічно чисте полювання, зарядив свою рушницю кісточками вишень. Після того, як він вдало влучив поміж роги оленям (в яких влучило відповідно k1, k2,-.;kN кісточок), у них на головах виросли чудові молоді вишеньки. Скільки саджанців зміг подарувати барон Мюнхгаузен садівникам-дослідникам?

Розв’язання: Для розв’язування цієї задачі пропонується використати масив для зберігання кількості кісточок, що влучили поміж роги оленям. Оскільки кількість кісточок є цілим числом, масив повинен мати розмірність N елементів цілого типу. Для спрощення відлагодження програми доречно використовувати автоматичне заповнення масиву за допомогою генератора випадкових чисел, а з метою перевірки правильності роботи програми після заповнення масив виводиться на екран. Програма, що реалізує розв’язання цієї задачі, має такий вигляд:

Program Ехашр1е_300;

Uses crt;

Var N:word;

К:array[1..100] of longint;

{K — зарезервований масив для зберігання кількості кісточок, що влучили в оленів}

і,Sum:longint; {і — змінна циклу, Sum — загальна кількість кісточок, що влучили в оленів}

Randomize;

{Ця процедура запускається з метою зробити числа генератора випадкових чисел ще більш «випадковими»}

Clrscr;

Sum:=0; {Спочатку Мюнхгаузен ще ні в кого не влучив}

Write(‘Олені, в яких влучив Мюнхгаузен (<=100): ‘);

Readln(N);

For і:=1 to N do

К[і]:=random(5 0)+2 0; {Заповнення масиву випадковими числами в діапазоні від 20 до 70}

Write(К[і]:5); {Виведення на екран для контролю}

Sum: =Sum+K [і]; {Знаходження кількості влучених кісточок}

End;

Writeln; {Переведення курсору на новий рядок}

Writeln(‘Кількість нових саджанців ‘,Sum);

Readkey; {Затримка зображення на екрані}

ЗАДАЧА № 309

Умова: Дано натуральне число А. Складіть програму, що представляє його у вигляді многочлена. Наприклад,

123 = 1 * 10² + 2* 10¹ + 3*10°.

Розв ‘язання. Ця задача фактично зводиться до пошуку окремих цифр числа. Оскільки ми не знаємо на початку роботи, скільки цифр має число, для їх зберігання можна використати масив цілих чисел, причому розмірність цього масиву можна задати не більше 10 елементів, тому що навіть найбільше ціле число типу longint має в своєму складі не більше 10 цифр. Щоб вивести на екран отриманий многочлен, ми спочатку знаходимо кількість цифр у числі та виділяємо кожну цифру окремо, а потім організовуємо цикл від «найстаршої» значущої (ненульової) цифри числа до «наймолодшої» з виведенням на екран самої цифри, помноженої на 10 у степені номер розряду - 1 (тобто i-1).

Програма, що реалізує описаний алгоритм, має вигляд:

Program Example_309;

Uses crt;

Var N,і,Count:longint; {N — задане ціле число, і — змінна циклу. Count — кількість цифр в числі}

Cifra:array[1..10] of byte; {Cifra — масив для зберігання цифр числа}

Clrscr;

Count:=0;

Write(‘Введіть ціле число: ‘);

Readln(N);

While N>0 do

Count:=Count+l; Cifra[Count]:=N mod 10; N:=N div 10;

End;

Write(‘N = ‘);

For it«Count downto 1 do

Write(Cifra[i],’*10^’,i-l); {Якщо доданок не останній, то до нього дописується знак «+»}

If і>1 Then write(‘ + ‘);

End;

Readkey; {Затримка зображення на екрані}

ЗАДАЧА № 312

Умова: Дано дійсні числа а1951, а1952,..., а2000 —кількість опадів (у мм), що випали у місті за останні 50 років століття. Обчислити середню кількість опадів за цей період і щорічне відхилення від середнього значення.

Розв’язання: У цій задачі слід організовувати проходження по масиву двічі, оскільки першим проходженням ми знайдемо тільки суму всіх опадів, що випали за останні 50 років, а потім, поділивши отриманий результат на 50, знайдемо середню кількість опадів за вказаний період. Другим же проходженням можемо вже визначити щорічне відхилення від середнього значення, причому для того, щоб не втратити вхідні дані, зарезервуємо в програмі ще один масив на 50 дійсних чисел для зберігання цих результатів.

Program Example_312;

Uses crt;

Var N,i:longint; {N — кількість елементів масиву, і — змінна циклу}

А:аггау[1951..2000] of real; {A - масив для зберігання кількості опадів у відповідному році}

В:array[1951..2000] of real; {В — масив для зберігання відхилення від середнього значення}

Randomize;

Clrscr;

Sum:=0;

For і:=1951 to 2000 do

A[i]:=random(500) /7; {Заповнення масиву випадковими дійсними числами}

Write (А[і]:8:2); {Виведення масиву на екран для контролю}

Sum:=Sum+K[і];

End;

Sum:=Sum/50; {Середня кількість опадів за рік}

Writeln; WriteIn(‘Щорічні відхилення від середньої кількості опадів за період 1951 - 2000 p.p.’);

For і:=1951 to 2000 do

В[і]:=Sum — А[і]; {Знаходження щорічного відхилення}

Write(В[і]:8:2); {Виведення результатів на екран}

End;

Readkey;

ЗАДАЧА №318 (4)

Умова: Дано дійсні числа а₁ а₂,..., a₃₀ b₁ b₂,..., b₃₀. Обчислити

Розв ‘язання: Очевидно, що для обчислення результату цієї задачі спочатку необхідно знайти чисельник та знаменник дробу. Причому звернітьувагу на те, що кількість доданків і в одному, і в другому випадкахдорівнює 15, тільки в чисельнику вибираються елементи масивів з непарними індексами, а в знаменнику — із парними. Щоб організуватизміну індексів за заданим законом, можна скористатися таким штучнимприйомом: якщо в циклі з параметром індекс і змінюється від 1 до п, тодля отримання непарних чисел з проміжку [1..2п] використовуєтьсяформула: 2*і - 1.

Запропонуйте дітям подумати, яка формула дасть змогу отримати парні числа (2*і). Використовуючи ці співвідношення, програма для розв’язку цієї задачі має вигляд:

Program Example_318_4;

Uses crt;

Var A,B:array[l..30] of real;

{А,В — масиви для зберігання вхідних даних}

і:byte; {і — змінна циклу}

Rl,R2:real; {R1 — чисельник дробу, R2 - знаменних дробу}

Rez:real; {Rez - результат обчислень}

Randomize;

Clrscr;

Writeln(‘Масив А:’);

For i:=1 to 30 do

A[i]:=random(200)/7-random*15; Write(A[i]:8:2);

End;

Writeln;

Writeln(‘Масив В:’);

For i:=1 to 30 do

B[i]:=random*200-random*100; Write(B[i]:8:2);

End;

Writeln;

Rl:=0; R2:=0; {Початкові значення дорівнюють 0, тому що результат є накопиченням суми}

For і:«і to 15 do

R1:= R1+(A[2*i-1]+B[2*i-1]); R2:= R2+(A[2*i]+B[2*i]);

End;

Rez:=Rl/R2;

Writeln(‘Результат обчислень = ‘,Rez:8:2);

Readkey;

Домашнє завдання

• Задачі№ 301,303,313,315(2,3), 318(2,5).

ЗАНЯТТЯ 24. Двовимірні таблиці

Мета заняття: Дати поняття двовимірних таблиць. Навчити розв’язувати типові задачі з обробки двовимірних таблиць.

Двовимірний масив — це масив, де кожному елементу ставиться у відповідність два індекси.

Для початку роботи з масивом готуємо місце в пам’яті.

Для цього описуємо його в розділі оголошень, використовуючи зарезервоване слово Array, після якого в квадратних дужках вказуємо розмірність масиву, причому враховуємо, що на першому місці вказуються індекси рядків, а на другому - стовпчиків, і обов’язково — тип елементів.

Опис двовимірного масиву:

<Ім’я_масиву>: array[<поч_інд_рядкiв>..<кін_інд_рядків>,

<поч_інд_ставп>..<кін_інд_стовп>] of <базовий_тип_елементів>;

Приклад опису:

Const n:=100; m:=100; Var A:array[1..n,1..m] of real;

D:array[l..10,1.100] of integer;

Зверніть увагу на те, що значень у рядках або стовпчиках масиву не обов’язково буде стільки, скільки ми оголосили, але не більше!

Звертання до елементу двовимірного масиву: їм’я_масиву[<індекс_рядка>, <хнд_стовпчика>]

Заповнення масиву:

• з клавіатури:

for i:=1 to n do

for j:=1 to m do

write (‘введіть A[‘i,’,’,j,’]: ‘);

readln(A[i,j])

end;

• за формулою:

for і:=1 to n do

for j:=1 to m do

A[i,j]:=i*i-10 {або будь-яка інша формула};

• випадковим чином із проміжку [K,L]:

for і:=1 to n do

for j:=1 to m do

A[і,j]:=random(L-K)+K;

Виведення двовимірного масиву на екран

for і:=1 to n do

for j:=1 to m do write(A[i,j]:8); {виведення в рядок}

writeln; {перехід на новий рядок}

end;

Виведення в рядку необхідно обов’язково форматувати, щоб не трапилося «злипання» елементів (дивись приклад вище).

Як уже було зазначено, для роботи з масивом потрібен будь-який оператор повторення. Очевидно, що у двовимірному масиві необхідно використовувати два оператори повторення: один цикл, внутрішній, потрібен для переходу між елементами рядка (тобто, по стовпчиках), а другий, зовнішній, — для переміщення між рядками. Якщо в матриці кількість рядків і стовпчиків однакова, то таку матрицю називають квадратною (на відміну від звичайної прямокутної таблиці). Тільки в квадратних матрицях існують головна та бічна діагоналі (дивись малюнок):

Елементи, що стоять на головній діагоналі, мають індекси (1, 1), (2, 2), (З, 3),... (і, і)...., (п, n), тобто номер рядка дорівнює номеру стовпчика. Елементи, що стоять на бічній діагоналі, мають такі індекси (1, n), (2, п -1), (З, п - 2),..., (і, п + 1 - 0, (п, 1), тобто індекси елементів взаємозалежні за формулою j- п +1 - і.

Далі рекомендується розглянути методи розв’язання деяких типових задач з обробки двовимірних таблиць.

ЗАДАЧА №345(1)

Умова: Дано натуральні числа п, т. Обчислити значення елементів матриці Сij, (і = 1, 2,... п, j-1, 2,.... т), якщо:

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

Program Example_345_l;

Uses crt;

Const n = 20; m = 15;

Var C:array[1..n,1..m] of integer;

i,j:integer; {i,j - змінні циклу}

Clrscr;

For i:=1 to n do

For j:=1 to m do

if і < j then C[i,j]:=i + j

else C[i,j]:=i*i + j*j;

Write(C[i,j]:5);

end;

writeln;

End;

Readkey; {Затримка зображення на екрані)

ЗАДАЧА № 360

Умова: Дано квадратну матрицю розмірності п. Надрукувати суму елементів бічної діагоналі.

Розв ‘язання: Розв’язок задачі є тривіальним, якщо згадати, яку залежність мають індекси бічної діагоналі (і +j = п + 1). Перевіривши цю залежність у середині циклів, що організовують проходження по масиву, ми знайдемо бажану суму.

Program Example_360;

Uses crt;

Const n = 10;

Var A:array[1..n,1..n] of real;

і,j:integer; (і,j - змінні циклу}

Sum:real; {Sum - сума елементів бічної діагоналі}

Randomize;

Clrscr; {Заповнення масиву та виведення його на екран}

For і:=1 to n do

For j: =1 to n do

A[i,j]:=random*50-random(80)/3; Write(A[i,j]:8:3);

end;

writeIn;

End;

Sum:=0; {Початкове значення суми}

For і:=1 to n do

For j:=1 to n do

if і + j = n+1 then Sum:=Sum+A[і,j];

End;

Writeln(‘Сума елементів бічної діагоналі =’,Sum:8:2);

Readkey;

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

Sum:=0; {Початкове значення суми}

For i:=l to n do Sum:=Sum+A[i,n+1-i];

Домашнє завдання

• Задачі № 343(3,4), № 344(3), № 345(2), №347(3), №361.

ЗАНЯТТЯ 25. Пошук елементів у таблицях

Мета заняття: Навчити розробляти алгоритми пошуку в таблицях елементів із заданими властивостями.

Для організації пошуку в таблиці елементів із заданими властивостями слід організувати циклічний перегляд всіх елементів, кожний з яких командою розгалуження порівняти із заданим еталоном або перевірити на деяку властивість. Якщо масив одновимірний, цикл для організації перегляду всіх елементів буде один, якщо ж масив двовимірний—циклів буде два.

ЗАДАЧА № 302

Умова: Середню групу дитячого садочка вивели на прогулянку. Скільки дівчаток і скільки хлопчиків видно з-за паркану, якщо зріст хлопчиків задається у сантиметрах від’ємними числами, а дівчаток — додатними у вигляді цілих значень а1 а2.... аn? Крім того, у всіх дівчаток на голівках зав’язані бантики заввишки 10см, а висота паркану Н см.

Розв’язання: При розв’язанні цієї задачі, заповнюючи масив, необхідно генерувати як додатні, так від’ємні числа. Для пошуку в масиві елементів із заданою властивістю (в даному випадку чисел, що за модулем більші, ніж задане) використовується вже відома команда розгалуження.

Таким чином програма буде мати наступний вигляд:

Program Example_302;

Uses crt;

Var N,H:word;

{N — кількість дітей в дитсадочку, Н — висота паркану}

А:аггау[1..100] of longint;

{А — зарезервований масив для зберігання зросту дітей}

і,Count_girl,Count_boy:longint;

{і — змінна циклу, Count_girl — кількість дівчаток,

Countjboy — кількість хлопців}

Randomize;

Clrscr;

Count_girl:=0; Count_boy:=0;

Write(‘Введіть висоту паркану: ‘);

Readln(H);

Write(‘Введіть кількість дітей в дитсадочку: ‘);

Readln(N);

For i:=1 to N do

A[i]:=random(300)-150;

{Заповнення масиву випадковими числами від -150 до +150}

Write(А[і]:5);

{Виведення масиву на екран для контролю роботи програми}

if (A[i]<0) and (abs(A[i])>H) then Count_Boy: =Count_Boy+1;

if (A[i]>0) and (A[i]+10>H) then Count_Girl: =Count_Girl+1;

End;

Write(‘хлопчики, яких видно з-за паркану ‘,Count_Boy);

Write(‘дівчатка, яких видно з-за паркану ‘,Count_girl);

Readkey; {Затримка зображення на екрані}

ЗАДАЧА №314(2)

Умова: Дано натуральне число п та послідовність дійсних чисел а1 а2...ап. Визначити кількість сусідств двох чисел різного знаку.

Розв ‘язання: Перш за все запропонуємо в цій задачі інший метод опису масиву з використанням константи, що задає розмір масиву, та вказівки Туре. А, по-друге, зверніть увагу, що для визначення двох сусідніх елементів масиву використовується загальний опис індексів і та і + 1 (можна і — 1 та і), а це при організації циклу можне викликати ситуацію виходу за межі масиву. Дійсно, якщо організувати цикл з параметром для зміни індексу від 1 до N, де N — кількість елементів масиву, то при і = N значення і + 1 буде виходити за межі масиву. Це є помилкою, що призводить до неочі-куваних результатів, тому цикл треба організовувати для зміни індексу не від 1 до N, а для зміни від 1 до N - 1.

Program Example_314_2;

Uses crt;

Const N=100;

Type Masiv = array[1..N] of real;

Var A:Masiv; {A — масив для зберігання даних чисел}

і,count:byte; {і — змінна циклу, count — кількість сусідств}

Randomize;

Clrscr;

count:=0;

For і:=1 to N do

A[i]:=random*100-random*50;

{Заповнення масиву випадковими дійсними числами}

Write(А[і]:8:2);

End;

For i:=l to N-l do

If ((A[i]<0) and (A[i+1]>0)) or ((A[i]>0) and (A[i+1]<0))

then count:=count+l;

Writeln;

Writeln(‘Кількість заданих сусідств ‘,count);

Readkey; {Затримка зображення на екрані}

ЗАДАЧА № 321 (1,2)

Умова: Дано одновимірний масив цілих чисел A[i], де i = 1, 2,..., п. Визначити, скільки разів максимальний елемент зустрічається у даному масиві та порядковий номер першого найбільшого елементу.

Розв’язання: Для розв’язку цієї задачі спочатку необхідно пройти по всіх елементах масиву і знайти серед них максимальний, запам’ятавши його номер. Для цього користуються стандартним алгоритмом:

1) береться будь-який елемент масиву (як правило, перший) і його значення присвоюється змінній max, тобто він вважається за еталон найбільшого елементу;

2) по черзі з масиву вибираються всі останні елементи і, якщо серед них знайдеться більший за обраний еталон, то змінній max присвоюється нове значення, яке тепер буде новим еталоном. В іншій змінній, наприклад, Nmax запам’ятовується номер цього найбільшого елементу (початкове значення цієї змінної було 1, тому що спочатку ми вважали найбільшим 1 -ий елемент). Після закінчення перегляду всього масиву змінна max буде містити шуканий максимум, а змінна N_max — його номер. Щоб запам’ятати номер першого максимального елемента, необхідно шукати в матриці елемент, що точно більший еталону. Якщо ж ми будемо шукати елемент, що не менший за еталон, то в змінній Nmax залишиться номер останнього найбільшого елементу (подумайте чому).

Після знаходження максимуму другим проходом можна вже підрахувати кількість таких елементів в масиві. Для цього кожен елемент порівнюється з еталоном, що знаходиться в змінній max, та до лічильника count додається одиниця у випадку співпадання цих значень.

Програма, що реалізує описаний алгоритм, наведена нижче:

Program Example_321_1_2;

Uses crt;

Const n = 30;

Var A:array[1..n] of integer; {A — масив даних чисел}

і:byte; {і — змінна циклу}

count,N_max:byte; {count — кількість максимальних елементів в масиві, Н_тах — номер першого найбільшого елементу}

max:integer; {max — максимальний елемент масиву}

Clrscr;

Randomize;

For і:=1 to n do

A[i]:«random(150) - random(80); Write(A[i]:5);

end;

{Надання змінним початкових значень)

max:=A[l];

N_max:=1;

count:=0;

{Прохід по масиву для пошуку максимуму та його номера}

for і:=2 to n do

if A[i]> max

then begin max:=A[i]; N_max:=i; end;

{Другий прохід по масиву для підрахунку кількості максимальних елементів}

for i:=1 to n do

if A[i]= max then count:=count+1;

Writeln(Максимум = ‘,max);

Writeln(‘Номер першого максимума = ‘,N_max);

Writeln(‘Кількість максимумів = ‘,count);

Readkey;

ЗАДАЧА № 356

Умова: Дано цілочислову прямокутну таблицю порядку п х т. Усі елементи таблиці, менші за середнє арифметичне її значень, замінити на «-1», а більші — на «1».

Розв ‘язання: Щоб виконати задану заміну, необхідно спочатку обчислити середнє арифметичне елементів таблиці. Для цього знайдемо суму всіх елементів, а потім поділимо на їх кількість (елементів у таблиці всього п х т). Після виконання зазначених обчислень необхідно ще раз організувати прохід по масиву, в результаті якого командою розгалуження вибрати додатні та від’ємні елементи і замінити їх відповідно до умови.

Program Example_356;

Uses crt;

Const n = 9; m = 12;

Type Masiv = array[1..n,l..m] of integer;

Var A:Masiv; i,j:byte; {i,j — змінні циклу}

Sum,SA:real;

{Sum — сума елементів таблиці, SA — середнє арифметичне}

Randomize;

Clrscr; Sum:=0; {Початкове значення суми}

Writeln(‘Вихідний масив: ‘);

For і: =1 to n do

For j: =1 to m do

A[i,j]:=random(120)-random(65); Write(A[i,j]:5);

Sum:=Sum+A[і,j]; {Накопичення суми елементів масиву}

end;

writeln;

End;

SA:=Sum/(n*m);

Writeln(‘Середнє арифметичне - ‘,SA:8:2);

Writeln(‘Результуючий масив: ‘);

For i:=1 to n do

For j:=1 to m do

if A[i,j] < SA then A[i,j]:=-1;

if A[i,j] > SA then A[i,j]:=1;

Write<A[i,j]:5);

end;

writeln;

End;

Readkey;

ЗАДАЧА № 358

Умова: У даній дійсній матриці розмірністю 6x9 знайти суму елементів рядка, що містить найбільший елемент. Вважається, що такий елемент у матриці єдиний.

Розв’язання: Щоб знайти суму елементів заданого рядка, спочатку визначимо, в якому з рядків матриці знаходиться максимальний елемент. Після цього ми повинні запам’ятати номер рядка, в якому він знаходиться. Використаємо для цього додаткову змінну N_max. Після повного проходу по масиву з метою пошуку максимуму, організовуємо новий цикл, але вже не по всьому масиву, а тільки по рядку з номером Njnax для обчислення суми елементів цього рядка. Програма для реалізації описаного алгоритму має наступний вигляд:

Program Example_358;

Uses crt;

Type masiv = array[1..6,1..9] of real;

Var A: Masiv;

i,j:byte; {i,j - змінні циклу}

Sum,max:real;

{Sum — сума елементів таблиці, max — махе. елемент таблиці}

N_max:byte; {Njnax — номер рядка, що містить махс. елемент}

Randomize;

Clrscr;

Writeln(‘Вихідний масив: ‘);

Fox i:=1 to 6 do

For j:=1 to 9 do

A[i,j]:=random*12-random(65)/ll; Write(A[i,j]:8:2);

end;

writeln;

End;

{Беремо у якості еталону перший елемент масиву}

mах:=А[1,1];

Nmax:=1; For i:=1 to 6 do

For j:=1 to 9 do

if A[i,j]>max then

Begin max:=A[i,j]; N_max:=i; End;

Writeln(‘Максимальний елемент масиву - ‘,max:8:2);

Sum:=0; {Початкове значення суми}

For j:=1 to n do

Sum: =Sum+A [ N_max, j ];

Writeln(*Отримана сума - ‘,Sum:8:2); Readkey;

Домашнє завдання:

• Задачі № 314, № 321, № 350(2), № 353(1), № 355(2), № 360(1), № 361.

ЗАНЯТТЯ 26. Впорядкування таблиць

Мета заняття: Дати поняття про методи впорядкування табличних величин. Навчити розв’язувати задачі, що потребують сортування.

Теоретичний матеріал

Дуже часто при розв’язуванні задач, пов’язаних з обробкою масивів, необхідно виконувати сортування його елементів за зростанням або спаданням. Такі задачі мають велике практичне значення. Розглянемо деякі з методів, що дають змогу впорядкувати елементи таблиць.

Всі існуючі методи сортування можна поділити на три групи:

• обмінні сортування — виконується обмін між двома (найчастішесусідніми) елементами масивів, якщо відповідні елементи розташовані увихідному масиві невпорядковано; процес повторюється або певну кількість разів, або доки елементи в масиві не стануть впорядкованими;

• методи прямого вибору — в масиві обирається елемент з певнимивластивостями (наприклад, мінімум або максимум), а потім вибранийелемент ставиться на своє місце;

• методи прямої вставки — послідовно вибираються елементи з масивуі після визначення їх місця у впорядкованому наборі даних вставляютьсябезпосередньо на своє місце.

Найбільш відомим обмінним сортуванням є метод «бульбашки».

В ньому при послідовному проході по масиву порівнюються два сусідніх елементи. Якщо їх розміщення є неправильним (наприклад, при впорядкуванні за зростанням лівий елемент більший за правий), виконується взаємообмін елементів. Процес повторюється щонайменше N- 1 разів, де N — кількість елементів у масиві.

Найпростіший алгоритм «бульбашки» має наступний вигляд:

Program Bubble; {Сортування за зростанням}

Const N=20;

Var Mas:array[1..N] of integer;

i,j:integer; {i,j — змінні циклу)

Rez: integer; {Rez — додаткова змінна для обміну елементів масиву між собою)

For i:=1 to N do

For j:=1 to N-l do

If Mas[j]>Mas[j+l] then

{Обмін елементів масиву через третю змінну)

Rez:=Mas[j]; Mas[j]:=Mas[j+1]; Mas[j+1]:=Rez;

End;

Метод можна модифікувати, зменшуючи діапазон сортування після кожного проходу, адже ясно, що після кожного проходу максимальний елемент масиву буде «спливати наверх», тобто займати спочатку останню позицію таблиці, потім передостанню і так далі:

Програма, що реалізує описаний алгоритм має наступний вигляд:

Program Bubble; {Сортування за зростанням)

Const N=20

Var Mas:агay[1..N] of integer;

і,j:integer; {i,j — змінні циклу)

Rez:integer; {Rez - додаткова змінна для обміну елементів масиву між собою)

For i:=1 to N do

For j:=1 to N-i do

If Mas[j]>Mas[j+l] then

{Обмін елементів масиву через третю змінну}

Rez:=Mas[j]; Mas[j]:=Mas[j+1]; Mas[j+1]:=Rez;

End;

Зверніть увагу, що в цьому алгоритмі у вкладеному циклі, що безпосередньо здійснює порівняння елементів, змінна циклу змінюється за іншим законом, ніж у попередньому випадку: від 1 до N-i, де і — змінна циклу зовнішньої команди повторення.

Другий метод модифікації алгоритму «бульбашки» полягає в тому, що ми вводимо додаткову змінну булівського типу (так званий прапорець), яка фіксуватиме при черговому проході була здійснена хоча б одна перестановка елементів чи ні. Адже очевидно, що якщо при черговому проході не відбулося жодної перестановки, то масив уже відсортований і процес перегляду можна припинити. Домовимось вважати прапорець «опущеним» (тобто рівним значенню false), якщо перестановки не відбулося, і «піднятим» (рівним true) — у протилежному випадку. Крім того, як і в попередньому випадку, після кожного проходу по масиву найбільший елемент «спливає» угору, тобто займає своє позицію. Тому вводимо додаткову змінну к, що фіксує праву границю впорядкованості, тобто при першому проході к = 1 і ми впорядковуємо всі елементи від 1 до N- 1, на другому проході к = 2 і будуть впорядковуватись усі елементи від 1 до N- 2 (останній елемент уже впорядкований) і так далі. Програма має вигляд:

Program Bubble; {Сортування за зростанням}

Const N=20;

Var Mas:array[1..N] of integer;

i,j,k:integer; {i,j — змінні циклу, k — змінна, що фіксує праву границю впорядкування}

Rez:integer; {Rez — додаткова змінна для обміну елементів масиву між собою}

Flag:Boolean; {Flag — змінна, що фіксує, відбулася перестановка чи ні}

k:=1;

Flag:=false; {Робимо припущення, що масив відсортований, а потім перевіряємо, чи правильним було це припущення, тобто чи немає серед елементів таких, що неправильно розташовані, якщо такі елементи будуть, то ми їх переставляємо і Flag присвоюємо значення true}

For і:=1 to N-k do

If Mas[i]>Mas[i+1]

{Обмін елементів масиву через третю змінну}

Rez:=Mas[i];

Mas[і]:=Mas[i+1];

Mas[i+1]:=Rez;

Flag:=true;

End;

k:=k-1;

Until Flag = false;

Другим методом сортування є метод прямого вибору. Один з його різновидів полягає в тому, що вибирається мінімальний елемент масиву, а потім виконується його обмін з першим елементом таблиці.

Дата добавления: 2014-10-22