Мета уроку: Навчити розв’язувати задачі, що потребують для свого розв’язання впорядкування масивів.
На початку уроку бажано зробити опитування за попереднім матеріалом. Потім розглянути кілька задач на застосування методів впорядкування табличних величин,запропонувати учням самостійне розв ‘язування цих задач.
ЗАДАЧА №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<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.
ЗАДАЧА №342(1)
Умова: Дано натуральне число п та послідовність дійсних чисел а1, а2 ... ап. Визначити усі числа, що входять у послідовність по 1-му разу.
Розв ‘язання: Пошук чисел, що входять у послідовність по одному разу, виконати важко, тому що для цього необхідно порівняти кожне число з кожним. Набагато простіше зробити це у відсортованому масиві, оскільки однакові числа в ньому будуть розташовані поруч. Тобто пропонуємо в даній задачі спочатку відсортувати масив (метод сортування будь-який, наприклад, «бульбашка»), а потім зробити по ньому прохід, порівнюючи сусідні елементи. Якщо вони не рівні, виконуємо підрахунок. Загальна кількість чисел, що входять у послідовність по одному разу, буде на одиницю більша, ніж отримане число в лічильнику.
Program Example_342_l ;
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)/ll-random*15;
Write(A[i]:8:2);
End;
k:=1;
Repeat
Flag:=false;
For i:=1 to N-k do
Begin If A[i]<A[i+l] then
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.
Домашнє завдання:
• Задача №339(2), №342(3,5), №367