3. Перевірка впорядкованості

Іноді початківця може поставити у скрутну ситуацію така проста задача:

Задача 15. Дано дійсні аг, а2, ..., а50. Перевірити, чи утворюють вони зростаючу послідовність.

Справді, задача має особливість: щоб дати ствердну відповідь, не­обхідно пересвідчитись, що для кожної пари сусідів виконано аi-1 < ai, a для отримання негативної відповіді достатньо, щоб ця умова порушилась хоча б один раз. Тому цикл з перевірками можна завершувати, коли у чергової пари сусідів порушено умову впорядкованості, або коли перебрали всю послідовність. Тоді відповідь на запитання задачі легко отримати, перевіривши, чи досягнуто кінець послідовності:

program growth;

const n=50;

var a : array [1. .n] of real; i:byte;

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

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

i:=2;

while (a [ i-1] <a [i] ) and ( i<=n) do inc(i);

if i>n then writeln('Послідовність зростаюча')

else writeln('Умову впорядкованості порушено після а',і)

end.

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

Очевидно, що перевірити впорядкованість заданої послідовності за спаданням можна за допомогою такого ж алгоритму. Досить лише замінити умову аг_і < аг- на а,_і > аг.

3.4. Пошук місця елемента послідовності

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

Задача 16. Дано впорядкований за незростанням масив цілих або

дійсних чисел a1≤a2≤ ..≤ ап і деяке число b (відповідно ціле

або дійсне), для якого необхідно знайти таке місце серед

чисел а1, а2, ..., ап, щоб після вставлення числа b на це місце

впорядкованість не порушилася.

Цю задачу називають задачею пошуку місця елемента. Для b є

n+1 можливість: b < а1, а1< b < а2, ..., аn-1 < b < аn, аn< b, і розв'язком

задачі пошуку місця елемента b буде відповідно одне з чисел 1, 2, ..., n,

n+1, яке вказує індекс для розташування доданого елемента. Для

розв'язування цієї задачі використовують різні алгоритми.

Лінійний пошук. Переглянемо масив а, починаючи з його першого елемента, і перевіримо, чи аі < b. Перше значення і, для якого вона не виконується, і є номером елемента масиву, в який необхідно записати b. Для b потрібно «звільнити» місце, перемістивши значення аi, ...,аn на один елемент далі. Такі переміщення зручно починати з кінця масиву. Якщо ж умову виконано для усіх елементів масиву, то b необхідно дописати після останнього елемента масиву:

program forwardlnsert ;

const n=10;

type vector=array[1..n]of integer;

var a:vector; b:integer; i,j:byte;

begin write('Введіть послідовність з ',n-1,' чисел: ');

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

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

і : =1; {шукаємо місце для b}

while (а [і] <b) and (i<n) do inc(i);

for j :=n-l downto і do atj+1] :=a[j] ; {посуваємо «хвіст»}

а [і] ;=b; {вставляємо Ь в масив}

for i:=l to n do write (а [і] : 5) ; writeln

end.

Якщо перевірку умови аi < b почати з останнього елемента масиву, то пошук і звільнення місця можна об'єднати в одному циклі:

program simplelnsert;

const n=10;

type vector=array[1..n]of integer;

var a: vector,- b: integer; і : byte;

begin write{'Введіть послідовність з ',n-1,' чисел: ');

for і:-і to n-1 do readia [i]) ;

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

i:=n-l; {шукаємо і звільняємо місце}

while !а[і]>b)and і і^ = і; do

begin a[i +1]:=a[i]; dec (і )

end;{while}

a[i + l] :=b; {вставляємо b в масив)

for і : =1 to n do write (a [i] : 5) ; writel

end .

Бінарний пошук. Для відшукання місця кожен з описаних вище алгоритмів виконає п порівнянь. Для пришвидшення пошуку можна використати метод поділу масиву навпіл. За цим методом спочатку задають межі пошуку місця для b рівними 1 і n+1, далі ці межі крок за кроком стискують так: порівнюють b з as, де s - ціла частина середнього ірифметичного меж пошуку; якщо as < b, то замінити нижню межу на s+1, у протилежному випадку замінити на s верхню межу; коли межі збігаються, то їхнє значення і буде результатом пошуку місця. Число порівнянь, яких потребує цей алгоритм, не перевищує [log2(n+l)]+l:

program binarylnsert;

const n=10;

type vector=array[1..n]of integer;

var a:vector,- b: integer; і, p, q, s : byte;

begin write('Введіть послідовність з ',n-1,' чисел: ');

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

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

p:=l; q:=n; {початкові межі пошуку}

while (p<>q) do

begin s:=(p+q) div 2; {шукаємо середній елемент}

if a[s]<b then p:=s+l else q:=s {і порівнюємо з ним}

end; {while}

for i:=n-l downto p do a[i+l] :=a[i] ; {посуваємо «хвіст»} a [p] :=b; {вставляємо елемент}

for i:=l to r. do write (a [i] :5) ; writeln end.