І Скляр - Я готуюсь до курсу інформатики. Алгоритмізація та програмування

1) - 8 < 12, тому виконується обмін, тобто після першого кроку масив має вигляд:

-8 12 0 30 5 100

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

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

1) 0 < 12, значить виконується обмін, тобто після першого кроку масивмає вигляд:

-8 0 12 30 5 100

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

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

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

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

1) 5 < 30, виконується обмін, після перестановки масив має вигляд:

-8 0 12 5 30 100

2) 5 < 12, здійснюється обмін, масив набуває вигляду:

-8 0 5 12 30 100

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

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

1) 100 < 30, вхід до циклу не відбувається, тому що умова відразу хибна і масив залишається без змін. Програму наведено нижче:

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.

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

• Створити блок-схему запропонованих алгоритмів сортування («бульбашка» — 1-й та 2-й методи, метод прямого вибору, метод прямої вставки).

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

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

ЗАДАЧА №339(1)

Умова: Дано натуральне число п та послідовність дійсних чисел а1, а2 ... ап. Після впорядкування цієї послідовності за спаданням визначити, скільки членів послідовності залишилося стояти на своїх місцях.

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

Program Example_339_l;

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

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.

ЗАДАЧА №342(1)

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

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