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.