Головна Реєстрація Вхід RSS

http://hozki-school.ucoz.ua/index/31-166-0-1-2

« попередня

ЗМIСТ

наступна »

Урок 37

Тема уроку: "Створення та реалізація програм на застосування методів впорядкування табличних величин."

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

На початку уроку бажано зробити опитування у письмовому чи усному вигляді за попереднім матеріалом. Потім можна розглянути кілька задач на застосування методів впорядкування табличних величин. Якщо клас досить сильний, можна запропонувати учням самостійний розв'язок цих задач.
Задача №339 (1).
Умова: Дано натуральне число n та послідовність дійсних чисел a1, a2, … an. Після впорядкування цієї послідовності за спаданням визначити, скільки членів послідовності залишилося стояти на своїх місцях.
Для того, щоб визначити, скільки чисел залишилось на своїх місцях, нам необхідно зберігати як вихідний масив, так і відсортований, тому перш за все зарезервуємо два однакових одновимірних масиви: А - вихідний масив та В - відсортований. Метод сортування масиву в даному випадку можна використовувати будь-який, наприклад, метол прямої вставки. Після виконання впорядкування проходом по обох масивах порівнюємо відповідні елементи вихідного та відсортованого масивів і, якщо вони співпадають, виконуємо підрахунок. Програма, що виконує описаний алгоритм, має наступний вигляд.

Program Example_339_1 ; 
Uses crt; 
Const N = 100; 
Type Masiv = array[1..N] of real; 
Var A,B: Masiv; {A - масив для зберігання початкової послідовності, В - відсортований масив} 
 i,j,count: byte; {і,j - змінні циклу, count - кількість елементів, що залишились на своїх місцях} 
 Max: real; {Max - максимальний елемент підмасиву} 
 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]:=B[i]; 
 B[i]:=Max; 
 End; 
 count:=0; 
 For i:=1 to N do 
 Begin 
 If A[i]=B[i] 
 then count:=count+1; 
 End; 
 Writeln; 
 Writeln('Кількість елементів, що не змінили свого місця ',count); 
 Readkey; {Затримка зображення на екрані} 
End. 

Задача №342(1).
Умова: Дано натуральне число n та послідовність дійсних чисел a1, a2, … an. Визначити усі числа, що входять у послідовність по одному разу.
Пошук чисел, що входять у послідовність по одному разу, виконати важко, тому що для цього необхідно порівняти кожне число з кожним. Набагато простіше зробити це у відсортованому масиві, так як однакові числа в ньому будуть розташовані поруч. Тобто пропонуємо в даній задачі спочатку відсортувати масив (метод сортування будь-який, наприклад, "бульбашка"), а потім зробити по ньому прохід, порівнюючи сусідні елементи. Якщо вони не рівні, виконуємо підрахунок. Загальна кількість чисел, що входять у послідовність по одному разу, буде на одиницю більша, ніж отримане число в лічильнику.

Program Example_342_1; 
Uses crt; 
Const N = 100; 
Type Masiv = array[1..N] of real; 
Var A: Masiv; {A - масив для зберігання вихідної послідовності} 
 i,j,count: byte; {і,j - змінні циклу, count - кількість елементів, що входять в послідовність один раз} 
 k: integer; {k - змінна, що коригує праву границю сортування} 
 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]>A[i+1] then 
 Begin 
 {Обмін елементів масиву через третю змінну} 
 Rez:=A[i]; 
 A[i]:=A[i+1]; 
 A[i+1]:=Rez; 
 Flag:=true; 
 End;
 End; 
 k:=k-1; 
 Until Flag = false; 
 count:=0; 
 For i:=1 to N-1 do 
 Begin 
 If A[i]<>A[i+1] 
 then count:=count+1; 
 End; 
 count:=count+1; 
 Writeln; 
 Writeln('Кількість елементів, що входять у послідовність один раз ',count); 
 Readkey; {Затримка зображення на екрані} 
End. 

Задача №360(3).
Умова: Дано квадратну матрицю розмірності n. Надрукувати елементи бічної діагоналі у порядку зростання.
Для того, щоб надрукувати елементи в порядку зростання, пропонуємо їх занести у одновимірний масив і відсортувати будь-яким методом сортування, наприклад, методом прямої вставки.

Program Example_360_3; 
Uses crt; 
Const N = 10; 
Var A: array[1..N,1..N] of real; {A - вихідний масив} 
 Mas: array[1..N] of real; {Mas - масив для зберігання діагональних елементів вихідного масиву} 
 i,j: byte; {і,j - змінні циклу} 
 Rez: real; {Rez - змінна для взаємообміну між двома елементами масиву} 
Begin 
 Randomize; 
 Clrscr; 
 For i:=1 to n do 
 Begin 
 For j:=1 to n do 
 begin 
 A[i,j]:=random(120)/3-random*20; 
 Write(A[i,j]:8:2); 
 end; 
 writeln; 
 End; 
 {Формування масиву з елементів бічної діагоналі вихідного масиву} 
 For i:=1 to N do 
 Mas[i]:=A[i,N+1-i]; 
 For i:=2 to N do 
 Begin 
 j:=i; 
 while (j>1) and (Mas[j] <Mas[j-1]) do 
 Begin 
 Rez:=Mas[j]; 
 Mas[j]:=Mas[j-1]; 
 Mas[j-1]:=Rez; 
 j:=j-1; 
 End; 
 End; 
 Writeln('Елементи бічної діагоналі:'); 
 For i:=1 to n do 
 begin 
 Write(Mas[i]:8:2); 
 end; 
 Readkey; {Затримка зображення на екрані} 
End. 

Задача №368.
Умова: Вважатимемо рядок квадратної матриці порядку n позначеним, якщо перший елемент цього рядка - нульовий. Вивести елементи матриці в такому вигляді: в кожному позначеному рядку - впорядковані за зростанням, а в інших - за спаданням.
Перевіривши перший елемент заданої квадратної таблиці на нуль, виконаємо впорядкування за зростанням або за спаданням одним з відомих способів сортування, наприклад, "бульбашкою".

Program Example_368; 
Uses crt; 
Const N = 9; 
Var A: array[1..N,1..N] of real; {A - вихідний масив} 
 i,j,k: byte; {і,j,k - змінні циклу} 
 Rez: real; {Rez - змінна для взаємообміну між двома елементами} 
Begin 
 Randomize; 
 Clrscr; 
 {Заповнення та виведення масиву на екран} 
 For i:=1 to n do 
 Begin 
 For j:=1 to n do 
 begin 
 A[i,j]:=random(120)/3-random*20; 
 Write(A[i,j]:8:2); 
 end; 
 writeln; 
 End; 
 {Цикл по рядках для перевірки першого елемента} 
 For k:=1 to n do 
 Begin 
 If A[k,1]=0 
 Then 
 Begin 
 {Сортування "бульбашкою" за зростанням} 
 For i:=1 to N do 
 For j:=1 to N-i do 
 If A[k,j]>A[k,j+1] 
 then 
 Begin 
 Rez:=A[k,j]; 
 A[k,j]:=A[k,j+1]; 
 A[k,j+1]:=Rez; 
 End; 
 End 
 Else 
 Begin 
 {Сортування "бульбашкою" за спаданням} 
 For i:=1 to N do 
 For j:=1 to N-i do 
 If A[k,j]>A[k,j+1] then 
 Begin 
 Rez:=A[k,j]; 
 A[k,j]:=A[k,j+1]; 
 A[k,j+1]:=Rez; 
 End; 
 End; 
 End; 
 {Виведення перетвореного масиву} 
 For i:=1 to n do 
 Begin 
 For j:=1 to n do 
 begin 
 Write(A[i,j]:8:2); 
 end; 
 writeln; 
 End; 
 Readkey; {Затримка зображення на екрані} 
End. 

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


• Задача №339(2), №342(3,5), №367
  

« попередня

ЗМIСТ

наступна »

Наверх