XIV. Допоміжні алгоритми

ЗАДАЧА № 69

Постановка задачі:

Баба–Яга записалася на курси водіїв літальних апаратів. Але справи в неї були кепські, бо вона ніяк не могла запам’ятати, яким чином визначається тривалість польоту, якщо відомі швидкість і відстань. Довелося їй звернутися по допомогу до Хлопчика–Мізинчика, який швиденько написав їй шпаргалку, куди Бабі–Язі треба було лише підставити свої значення. Як виглядала послідовність дій у цій шпаргалці і як нею користувалася Баба–Яга?

Аналіз алгоритму:

Очевидно, що «шпаргалку» Хлопчика–Мізинчика можна оформити як допоміжний алгоритм. Параметрами, що передаються у цей алгоритм, будуть швидкість літального апарату та відстань, яку необхідно подолати, а вихідним параметром – шукана тривалість польоту. Вхідні параметри процедури повинні бути параметрами–значеннями, а вихідний параметр – параметром–змінною. Позначимо у підпрограмі формальні параметри наступним чином: V – швидкість літального апарату; S –відстань, що необхідно подолати; Т – тривалість польоту.

В основній програмі ті самі змінні будуть мати відповідно імена: X, Y та М (імена змінних у основній програмі бажано, щоб не збігалися з іменами локальних параметрів підпрограми, тому їх вибір є випадковим).

Текст програми:

Program Task_69;

Uses crt;

Var X, Y, M:real;

 

Procedure Solution (V, S: real; var T: time);

Begin T:=S/V; End;

 

Begin

Clrscr;

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

Readln(X);

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

Readln(Y);

If (X<=0) or (Y<0)>

else

begin

Solution(X, Y, M); {Виклик процедури}

Writeln(‘Тривалість польоту –> ‘, М:6:2);

end;

Readkey;

End.

ЗАДАЧА № 70

Постановка задачі:

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

Аналіз алгоритму:

Очевидно, що підпрограма, яка виконує дану задачу, повинна мати три формальних параметри. Позначимо їх наступним чином: S – заданий текст (змінна рядкового типу string); x – символ, що підлягає вилученню (змінна символьного типу char); count – кількість вилучень (числова змінна цілого типу, наприклад byte).

Параметр х повинен бути параметром-значенням (вхідний параметр), а параметри S та count - параметрами-змінними (вихідні параметри). Рядок S фактично є і вхідним, і вихідним, тому що за умовою задачі саме в ньому необхідно здійснити вилучення заданих символів.

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

Оформлення основної програми, на наш погляд, не повинно викликати сумнівів. Зазначимо лише, що відповідні фактичні параметри у запропонованій програмі будуть називатися A (заданий текст), Ch (символ, що підлягає вилученню), N (кількість вилучень).

Текст програми:

Program Task_70;

Uses crt;

Var A:string; ch:char; N:byte;

 

Procedure Solution (x:char; var S:string; var count:byte);

var і:byte; {локальна змінна для організації циклу}

Begin

count:=0; і:=1;

while i<=length(S) do

begin

if S[i]=x then

begin

count:=count+1;

delete(S, i, 1);

end

else i:=i+1;

end;

End;

 

Begin

clrscr;

writeln(‘Введіть текст: ‘);

readln(A);

write(‘Введіть шуканий символ: ‘);

readln(ch);

Solution(ch, A, N);

writeln(‘Результуючий текст: ‘, A);

writeln(‘Кількість виконаних вилучень: ‘, N);

readkey;

End.

XII. Побудова графічних зображень

ЗАДАЧА № 64

Постановка задачі:

Скласти програму, яка при натисканні клавіші Д (день) малює сонце, а при натисканні клавіші Н (ніч) малює місяць.

Аналіз алгоритму:

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

Текст програми:

Program Task_64;

Uses graph, crt; {Підключення бібліотек}

Var GraphDriver, GraphMode:integer;

Ch:char;

Begin

Clrscr;

Writeln(‘Введіть Ваш вибір: Д – день, Н – ніч. ‘);

Readln(ch);

GraphDriver:=VGA; {Ініціалізація графічного режиму)

GraphMode:=VGAHi;

InitGraph(GraphDriver, GraphMode, ‘‘);

if (Сh=‘Д’) or (Ch=‘д’) then

begin

setfillstyle(l, yellow);

setcolor(yellow);

fillellipse(100, 80, 50, 50); {Малювання сонця)

{Малювання променів)

line(100, 80, 250, 80); line{100, 80, 240, 30);

lіnе(100, 80, 200, 250); line(100, 80, 230, 180) ;

line(100, 80, 150, 250); line(100, 80, 100, 300);

line(100, 80, 50, 380); line(100, 80, 20, 280);

line(100, 80, 0, 150); line(100, 80, 0, 80) ;

line(100, 80, 0, 30); line(100, 80, 10, 0) ;

line(100, 80, 50, 0); line(100, 80, 100, 0) ;

line(100, 80, 150, 0);

end

else

if (Ch=‘H’) or (Ch=‘H’) then

begin

setfillstyle(l, yellow); setcolor(yellow);

fillellipse(100, 80, 50, 50); setfillstyle(1, black) ;

setcolor(black); fillellipse(130, 80, 50, 50) ;

end

else writeln(‘Ви помилилися!’);

Readkey; Closegraph; {Закриття графічного режиму}

End.

ЗАДАЧА № 65

Постановка задачі:

«Зоряне небо». Заповнити екран монітора різнокольоровими точками, кількість яких, колір та координати визначаються випадково.

Аналіз алгоритму:

Для вибору випадковим чином вказаних величин скористуємось функцією Random, що вибирає числа із заданого діапазону, причому врахуємо, що, якщо в дужках після функції вказане ціле число, то будуть генеруватися цілі числа в діапазоні від 0 до вказаного числа. Зверніть увагу на те, що всього можливих кольорів 16 (від 0 до 15), але на чорному тлі чорний колір (з нульовим номером) не видимий, тому можна скористатися такою формулою для отримання ненульових цілих чисел в діапазоні від 1 до 15: random (14) + 1

Аналогічно можна вибрати координати та кількість «зірок» (точок) на екрані, причому відслідкувати, щоб кількість ніколи не була нульовою. Сама «зірка» (точка) на екрані може бути отримана процедурою Putpixel, що задає колір та координати точки виведення.

Текст програми:

Program Task_65;

Uses graph;

Var GraphDriver, GraphMode:integer;

x, y, color, N:integer; {x, y – координати точки – ‘Зірки’,

color – колір точки, N – кількість точок}

і:integer; {і – змінна циклу}

Begin

Randomize;

GraphDriver:=VGA; GraphMode:=VGAHi;

InitGraph(GraphDriver, GraphMode, ‘‘);

{Генерується кількість точок в діапазоні від 200 до 1200}

N:=random(1000)+200;

for i:=1 to N do

begin

x:=random(640); у:=random(480); color:=random(14)+l;

putpixel (x, y, color) ; {Виведення піксела заданого кольору color у задані координати екрану х та у}

end;

Readkey;

Closegraph;

End.

XI. Рядкові величини

ЗАДАЧА № 58

Постановка задачі:

Нехай дано деякий текст. Обчислити, скільки разів повторюється наперед заданий символ а.

Аналіз алгоритму:

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

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

Текст програми:

Program Task_58;

Uses crt;

Var і, count:word;

{і – змінна циклу, count – кількість знайдених символів}

a:char; {a – шуканий символ}

St:string; {St – даний текст}

Begin

Clrscr;

Write(‘Введіть текст: ‘);

Readln(St);

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

Readln(a);

Count:=0; (Початкове значення лічильника}

For i:=1 to length(St) do

If St[i] = a Then count:=count+l;

Writeln(‘Шуканих символів в тексті: ‘, count);

Readkey;

End.

ЗАДАЧА № 59

Постановка задачі:

У даному тексті замінити всі символи «:» на символи «–» і навпаки.

Аналіз алгоритму:

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

У результаті текст після закінчення роботи програми відтвориться у початковому вигляді.

Текст програми:

Program Task_59;

Uses crt;

Var і:word; {і – змінна циклу}

St:string; {St – даний текст}

Begin

Clrscr;

Write(‘Введіть текст: ‘);

Readln(St);

For i:=1 to length(St) do

If St[i] = ‘:’ Then

Begin Delete (St, i, 1) ; Insert (‘–’St, 1) ; End

Else

If St[i]=‘–’ Then

Begin Delete(St, i, 1); Insert(‘:’, St, 1); End;

Writeln(‘Результуючий рядок: ‘, St);

Readkey;

End.

ЗАДАЧА № 60

Постановка задачі:

У даному тексті замінити всі символи « . » на послідовність символів « … ». Якщо у тексті зустрічаються підряд три крапки, то залишати їх без змін.

Аналіз алгоритму:

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

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

Текст програми:

Program Task_60;

Uses crt;

Var i:word; {i – змінна циклу}

St: string; {St – даний текст}

Begin

Clrscr;

Write(‘Введіть текст: ‘);

Readln(St); i:=1;

While i

Begin

If (St[i]=‘.‘) and (St[i+1]<>‘.‘) Then

Begin Insert(‘..‘, St, i+l); i:=i+2; End;

i:=i+1;

End;

If St[length(St)]=‘.‘ Then St:=St+’..‘;

Writeln(‘Результуючий рядок: ‘, St);

Readkey;

End.

ЗАДАЧА № 61

Постановка задачі:

Перевірити, чи однаково читається дане слово зліва направо і навпаки.

Аналіз алгоритму:

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

Текст програми:

Program Task_61;

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

St, Rez:string;

{St – даний текст, Rez – результуючий (перегорнутий) рядок}

Begin

Clrscr;

Write(‘Введіть текст: ‘);

Readln(St);

Rez:= ‘‘; {Очищення рядка}

For і:– length(St) downto 1 do

Rez := Rez+St[i]; {Перегортання рядка}

If Rez = St Then Writeln(‘Слово є паліндромом. ‘)

Else Writeln("Слово не є паліндромом. ‘);

Readkey;

End.

ЗАДАЧА № 62

Постановка задачі:

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

Аналіз алгоритму:

Організовуємо прохід по рядку за допомогою циклу з параметром, причому враховуємо, що слід перевірити три послідовно розташованих символи (зверніть увагу на можливість виходу за межі рядка!). Один з методів вибору кількох послідовних символів уже розглядався раніше (і–ий, і+1–ий та і+2–ий елементи), тому розглянемо інший метод, що полягає у використанні функції копіювання Copy. Нагадуємо, що ця функція містить у якості параметрів вихідний рядок, номер початку копіювання (виділення) та кількість вибраних символів, тобто для вибору трьох символів з будь–якого місця рядка ця функція буде мати вигляд:

Cоpy(St, i, 3)

Порівнюючи виділені (скопійовані) символи з еталоном, нарощуємо лічильник при виконанні поставлених умов.

Текст програми:

Program Task_62;

Uses crt;

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

St:string; {St – даний текст}

Count:byte; {Count – лічильник послідовностей}

Begin

Clrscr;

Write(‘Введіть текст: ‘);

Readln(St);

Count:=0; {Початкове значення лічильника}

For i:=1 to length(St)– 2 do

If Copy(St, i, 3) = ‘абв’ Then count:=count+1;

Writeln(‘Кількість шуканих послідовностей: ‘, count);

Readkey;

End.

ЗАДАЧА № 63

Постановка задачі:

Нехай дано формулу. Визначити коректність формули щодо кількості відкритих та закритих дужок. Вважається, що закриті дужки не стоять перед відкритими. Якщо дужки у формулі відсутні – повідомити про це.

Аналіз алгоритму:

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

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

Щоб визначити, чи є в формулі дужки взагалі, достатньо перевірити на нуль кількість одних чи других дужок. Визначимо змінні count–left та count–right як кількість відповідно лівих (відкритих) та правих (закритих) дужок.

Текст програми:

Program Task_63;

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

St:string; {St – даний текст}

count_left, count_right:byte;

{count_left – лічильник лівих дужок,

 count_right – лічильник правих дужок}

Begin

Clrscr;

Write(‘Введіть формулу: ‘);

Readln(St);

Count_left:=0; {Початкове значення лічильника)

Count_right:=0;

і:= 1;

While (i<=length(St)) and (Count_left>=Count_right)) do

Begin

If St[i] = ‘(‘ Then count_left:=count_left+1;

If St[i] = ‘)’ Then count_right:=count right+1;

і: =i+l ;

End;

If (count_left=0) and (count_right=0)

Then wrіteln(‘Формула не має дужок. ‘)

Else

If count_left=count_right Then Writeln( ‘Формула коректна’)

else writeln(‘Формула не коректна. ‘);

Readkey;

End.

X. Впорядкування масивів

ЗАДАЧА № 56

Постановка задачі:

Дано натуральне число п та послідовність дійсних чисел а₁, а₂, …, а_п. Після впорядкування цієї послідовності за спаданням визначити, скільки членів послідовності залишилося стояти на своїх місцях.

Аналіз алгоритму:

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

Текст програми:

Program Task_56;

Uses crt;

Const N = 100;

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

Var A, B:Masiv; {A – масив для зберігання початкової послідовності,

В – відсортований масив}

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

count – кількість елементів, що залишились на своїх місцях}

Max:real; {Мах – максимальний елемент підмасиву}

N_max:byte; {N_max – номер максимального елементу}

Begin

Randomize;

Clrscr;

For i:=1 to N do

Begin

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

Write(A[i]:8:2);

End;

B:=A; {Копіювання елементів масиву А в масив В}

For i:=1 to N–1 do

Begin

Max:=B[i]; {Зберігання еталону максимуму}

N_Max:=i; {Зберігання номера максимуму}

For j:=i+1 to N do

If B[j]>Max Then

Begin

Max:=B[j]; {Перевизначення еталону}

N_Max:=j; {Зберігання номеру еталону}

End;

{Обмін місцями мінімуму та першого елементу підмасиву}

B[N_Max]:=В[і]; В[і]:=Мах;

End;

count:=0;

For і:=1 to N do

Begin

If A[i]=B[i] Then count:=count+1;

End;

Writeln;

Writeln(‘Кількість елементів, що не змінили місця = ‘ , count) ;

Readkey;

End.

ЗАДАЧА № 57

Постановка задачі:

Дано натуральне число п та послідовність дійсних чисел а₁, а₂, …, а_п. Визначити усі числа, що входять у послідовність по одному разу.

Аналіз алгоритму:

Пошук чисел, що входять у послідовність по одному разу, виконати важко, тому що для цього необхідно порівняти кожне число з кожним. Набагато простіше зробити це у відсортованому масиві, оскільки однакові числа в ньому будуть розташовані поруч. Тобто пропонуємо в даній задачі спочатку відсортувати масив (метод сортування будь-який, наприклад, «бульбашка»), а потім зробити по ньому прохід, порівнюючи сусідні елементи. Якщо вони не рівні, виконуємо підрахунок. Загальна кількість чисел, що входять у послідовність по одному разу, буде на одиницю більша, ніж отримане число в лічильнику.

Текст програми:

Program Task_57;

Uses crt;

Const N = 100;

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

Var A:Masiv; {A – масив для вихідної послідовності}

і, j, count:byte; {і, j – змінні циклу,

count – кількість елементів, що входять у послідовність один раз}

k: integer; {к – змінна, що коригує праву границю сортування}

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

Begin

Randomize; Clrscr;

For i:=1 to N do

Begin

A[i]:=random(300)/11–random*15;

Write(A[i]:8:2);

End;

k:=1;

Repeat

Flag:=false;

For i:=1 to N–k do

Begin

If A[i]

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

Rez:=A[i]; А[і]:=А[і+1]; A[i+1]:=Rez;

Flag:=true;

End;

k:=k–1;

End;

Until Flag = false;

count:=0;

For i:=1 to N–1 do

Begin If A[i]OA[i+l] then count: =count+1; End;

count:=count+l;

Writeln;

Write (‘Кількість елементів, що входять у послідовність 1 paз = ‘);

Writeln(count);

Readkey;

End.

X. Впорядкування масивів (вступна частина)

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

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

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

Текст програми:

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

Const N=20;

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

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

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

Begin

For i:=1 to N do

For j:=1 to N–1 do

If Mas[j]>Mas[j+1] Then

Begin

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

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

End;

End.

 

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

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

Текст програми:

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

Const N=20

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

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

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

Begin

For i:=1 to N do

For j:=1 to N–i do

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

Begin

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

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

End;

End.

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

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

Текст програми:

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

Const N=20;

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

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

k – змінна, що фіксує праву границю впорядкування}

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

Flag:Boolean; {Flag – змінна, що фіксує перестановку}

Begin

k:=1;

Repeat

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

For і:=1 to N–k do

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

Begin

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

Rez:=Mas[i];

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

Mas[i+1]:=Rez;

Flag:=true;

End;

k:=k–1;

Until Flag = false;

End.

 

Другим методом сортування є метод прямого вибору. Один з його різновидів полягає в тому, що вибирається мінімальний елемент масиву, а потім виконується його обмін з першим елементом таблиці. Після цього перший елемент вважається впорядкованим і процес повторюється для підмасиву, що містить на один елемент менше за початковий, тобто елементи з 2-го до останнього. Процес повторюється кожен раз для масиву, зменшеного на один елемент. Закінчується він тоді, коли невпорядкований підмасив стає довжиною в один елемент. Таким чином, загальна кількість повторень дорівнює, як і в попередньому випадку, N-1 (N – кількість елементів масиву).

Текст програми:

Program Selection;

Const N=20;

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

і, j, Min, N_Min:integer;

Begin

For i:=1 to N–1 do

Begin

Min:=Mas[x]; {Зберігання еталону мінімуму}

N_Min:=i; {Зберігання номера мінімуму}

For j:=i+1 to N do

If Mas[j]

Begin

Min:=Mas[j]; {Перевизначекня еталону}

N_Min:=j; {Зберігання номеру еталону}

End;

{Обмін місцями мінімуму та першого елементу підмасиву}

Mas[N_Min]:=Mas[i];

Mas[i]:=Min;

End;

End.

Зверніть увагу, що пошук мінімуму в програмі організований стандартно, тобто перший елемент береться за еталон, а потім порівнюється з усіма останніми і, якщо новий елемент виявляється меншим за еталон, то еталон переприсвоюється. Крім цього, в алгоритмі запам’ятовується місце знаходження цього мінімального елемента для того, щоб після виходу з циклу можна було обміняти місцями знайдений мінімум і перший елемент підмасиву. Але оскільки підмасив увесь час змінює свій розмір, за еталон береться перший елемент саме того підмасиву, який розглядається на наступному кроці, тобто i-ий елемент початкового масиву
(і – змінна зовнішнього циклу, що вказує на початок нового підмасиву на кожному кроці).

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

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

12 -8 0 30 5 100

Розбиваємо його на дві частини. До першої входить єдиний впорядкований елемент {12}, а до другої – всі останні {-8 0 30 5 100}. Запишемо тепер процес впорядкування по етапах:

І етап: елемент, що впорядковується = -8.

1) -8 <>

-8 12 0 30 5 100

На цьому цикл припиняє свою роботу, тому що досягнуто початку масиву (і=1).

II етап: елемент, що впорядковується = 0.

1) 0 <>

-8 0 12 30 5 100

2) 0 > -8, значить обмін не виконується, здійснюється вихід із циклу, масив залишається без змін.

III етап: елемент, що впорядковується = 30.

1) 30 > 12, вхід до циклу не відбувається, масив залишається без змін.

IV етап: елемент, що впорядковується = 5.

1) 5 <>

–8 0 12 5 30 100

2) 5 <>

–8 0 5 12 30 100

3) 5 > 0, цикл припиняє свою роботу, масив залишається без змін.

V етап: елемент, що впорядковується = 100.

1) 100 <>

Текст програми:

Program Insert;

Const N=20;

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

і, j, Rez:integer;

Begin

For i:=2 to N do

Begin

j:=i; {Цикл працює, доки лівий елемент більший за правий та доки не досягнуто початок масиву}

While (j>1) and (Mas[j] <>

Begin

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

End;

End;

End.