Posibnik_Pascal

{Процедура створення запису з полями: прізвище студента, ім‘я студента, рік народження}

Procedure st_el(var s:inform); Begin

with s do begin

write ( 'Прізвище студента '); readln(fam); write ( 'Ім‘я студента '); readln(nam); write ( 'Рік народження '); readln(god); end;

{Процедура створення типізованого файлу записів}

Procedure st_file(var f:f_t);

Begin

{Процедура друкування вмісту файлу на екрані}

Procedure druk_file(var f:f_t);

Begin

reset(f);

while not eof(f) do begin

read(f,inf); druk_el(inf); end;

close(f);

End;

81

{Процедура сортування даних поля “рік народження” методом вставки}

Procedure InsertionSort(var f:f_t); var

i,j:integer; inf1,inf2:inform;

Begin

reset(f);

for i := 1 to filesize(f)-1 do begin

j:=i-1;

seek(f,j); read(f,inf1); read(f,inf2); {читання елементів на позиціях j-1, j} while (inf1.god>inf2.god) and (j>=0) do

begin

seek(f,j); write(f,inf2); write(f,inf1);

елементів}

reset(f);

for i:=1 to filesize(f)-1 do begin

seek(f,i-1); read(f,inf3); k:=i; inf1:=inf3; for j:=i+ 1 to filesize(f) do

begin

read(f,inf2);

if inf3.fam>inf2.fam then begin

inf3:=inf2; k:=j; end;

end;

seek(f,k-1); write(f,inf1); seek(f,i-1); write(f,inf3); {перестановка елементів} end; close(f);

End;

82

{Процедура сортування даних поля “ім‘я студента” методом обміну (методом “бульбашок”)}

Procedure BubbleSort(var f:f_t); Var

Begin

reset(f);

for i:=1 to filesize(f)-1 do begin

for j:=filesize(f)-1 downto i do begin

seek(f,j-1); read(f,inf1); read(f,inf2); if inf1.nam>inf2.nam then

begin

seek(f,j-1); write(f,inf2); write(f,inf1); end;

repeat

clrscr;

writeln ( 'Введіть ім'я файлу ‘ ); readln(name); assign(f,name); write ( 'Створити файл Y/N '); readln(ch);

if (ch='Y') or (ch='y') then st_file(f);

writeln ( 'Друкування створеного файлу ',name); druk_file(f); repeat

writeln ( 'Сортування ');

writeln('1:за прізвищем - метод вибору '); writeln('2:за іменем - метод “бульбашок”‘); writeln('3:за роком народження - метод вставки '); writeln('4:закінчити роботу ');

write ( 'Оберіть метод сортування '); readln(ch); case ch of

'1 ':SebebionSort(f);

'2 ':BubbleSort(f); '3 ':InsertionSort(f); end;

writeln ( 'Друкування файлу ',name); druk_file(f); until (ch<>='1') and (ch<>’2’) and (ch<>’3’);

writeln ( 'Кінець-[e],продовження - інша '); readln(ch); until (ch='e') or (ch=’E’); readln;

End.

83

☺ Завдання для виконання

Основний рівень

1. Перетворити масив Х за наступним правилом : усі від’ємні елементи масиву Х перенести на початок, а всі інші - у кінець. Усі від’ємні елементи відсортувати за неспаданням.

2. Дано дійсні числа а1, а2, ..., аn. Серед цих чисел усі від’ємні числа збільшити на 0,25, а всі невід’ємні замінити на 0,2. Потім отримані від’ємні числа відсортувати за незростанням.

3. Дано два масиви чисел А та В по N елементів у кожному. Упорядкувати масив Z за спаданням елементів, за умови, що елементи масиву Z утворюються за формулою zi = ai -

bi sin(i).

4. Обчислити координати вектора Z ={z1, z2, ..., zN} i впорядкувати їх за зростанням, якщо zk =xk + myk , де xk, yk - координати заданих векторів Х та Y, а m визначається умовою:

k при | sin k |≤ 0.3 m = >

k при | sin k | 0.3

5.Дано двовимірний масив розмірності NxM. Елементами масиву є цілі числа. Упорядкувати рядки за неспаданням елементів першого стовпця.

6.Дано двовимірний масив розмірності NxM. Елементами масиву є дійсні числа. Упорядкувати рядки за незростанням елементів другого стовпчика.

7.Дано двовимірний масив розмірності NxM. Елементами масиву є цілі числа. Упорядкувати стовпці за незростанням елементів першого рядка.

8.Дано двовимірний масив розмірності NxM. Елементами масиву є дійсні числа. Упорядкувати рядки за неспаданням сум елементів рядків.

9.Дано цілі числа x1, ..., xn. Отримати в порядку зростання всі різні числа, що входять до x1,

..., xn. При сортуванні необхідно відкинути елементи, що вже зустрічалися раніше. Якщо при пошуку місця для хі в упорядкованій послідовності x1, ..., xк (к<i) виявиться, що серед x1, ..., xк є елемент, рівний хі, то слід перейти до розгляду хі+1 без зміни x1, ..., xк.

10.Дано дійсні числа с1, ..., сn , d1, ..., dk ( c1 ≤ c2 ≤ ... ≤ cn , d1 ≤ d2 ≤ ... ≤ dk ). Із цих чисел утворити нову послідовність f1, f2, ..., fn+k так, щоб f1 ≤ f2 ≤ ... ≤ fn+k .

11.Дано цілі числа x1, ..., xn . Упорядкувати дану послідовність за зростанням та знайти найбільше значення, що отримається в послідовності після вилучення з неї всіх членів зі значенням max(x1, . . . , xn ).

12.Дана матриця дійсних чисел (хij) порядку m ×n . Упорядкувати рядки матриці за неспаданням мінімальних елементів рядків.

13.Дана матриця дійсних чисел (хij) порядку m ×n . Упорядкувати рядки матриці за незростанням максимальних елементів рядків.

14.Дана матриця дійсних чисел (хij) порядку m ×n . Упорядкувати стовпці матриці за неспаданням максимальних елементів стовпців.

15.Дана матриця дійсних чисел (хij) порядку m ×n . Упорядкувати стовпці матриці за незростанням мінімальних елементів стовпців.

84

Підвищений рівень

1.Багаж пасажира характеризується кількістю та загальною вагою речей. Дано файл bagaj, який містить відомості про багаж декількох пасажирів. Відомості про багаж - це записи із двома полями: одне поле цілого типу (кількість речей) і друге – дійсного типу (вага в кілограмах). Упорядкувати відомості про багаж, що записані в файлі bagaj, за незростанням ваги багажу, а при однаковій вазі впорядкувати за незростанням кількості речей.

2.Створити файл записів із полями: назва міста, кількість жителів, площа міста. Упорядкувати цей файл за незростанням кількості жителів, а при однаковій кількості, упорядкувати за неспаданням площі.

3.Дано текстовий файл. Словом вважають групу символів між двома пробілами. Упорядкувати слова файлу за алфавітом (лексикографічно).

4.Упорядкувати список студентів за незростанням середнього балу оцінок останньої сесії, а прізвища студентів, що мають однаковий середній бал, за алфавітом. Вивести результати на екран.

5.Створити файл записів із полями: прізвище, номер дому, заборгованість за квартиру. Упорядкувати цей файл за зростанням номеру дому, а в межах одного дому – за зростанням заборгованості.

6.Створити файл записів із полями: найменування товару, країна, що імпортує товар, та обсяг поставленої партії в штуках. Відсортувати файл за полем “обсяг поставленої партії в штуках” за зростанням. Визначити назву країни, яка імпортує найбільше товару.

7.Упорядкувати список студентів за місяцем народження, а прізвища студентів, що народилися в одному місяці, за алфавітом. Вивести результати на екран.

8.Створити файл записів із полями: прізвище, вік, зріст. За один перегляд файлу створити список, який складається з найвищих людей. Упорядкувати отриманий список за зростанням віку.

9.Створити файл записів із полями: прізвище, номер дому, заборгованість за квартиру. Визначити номер дому, жителі якого мають найбільшу сумарну заборгованість за квартиру. Упорядкувати дані про жителів цього дому за алфавітом прізвищ.

10.Дано файл бібліотека , який містить відомості про книги: прізвище автора, назва та рік видання. Упорядкувати даний файл за роком видання книг, а в межах одного року, за алфавітом прізвищ авторів.

11.Дано файл асортимент, який містить відомості про іграшки: назва іграшки ( лялька, конструктор і т. д. ), її вартість та вікові межі (наприклад, іграшка може бути призначена для дітей від 2 до 5 років). Упорядкувати даний файл за зростанням вікової межі та визначити, для якого віку є найбільше іграшок.

12.Дано файл, що містить номери телефонів співробітників закладу: прізвище співробітника, його ініціали та номер телефону. Упорядкувати даний файл за прізвищами співробітників (в алфавітному порядку). Вивести інформацію про співробітників, які користуються однаковими телефонами.

13.Створити файл записів із полями: назва міста, кількість жителів, площа міста. За один перегляд файлу створити список міст, які мають найбільшу площу. Упорядкувати цей список за неспаданням кількості жителів.

14.Створити файл записів із полями : прізвище, номер дому, заборгованість за квартиру. За один перегляд файлу створити список жителів, що проживають в домі №24. Упорядкувати отриманий список за спаданням заборгованості за квартиру.

15.Файл містить інформацію про студентів: прізвище, ім‘я та рік народження. Вивести на екран відомості про студентів з іменами, що починаються з літери “А”, упорядкувавши їх за роком народження.

85

Питання для самоконтролю

1.Що таке сортування даних?

2.У яких структурах даних можна проводити сортування?

3.Сформулюйте постановку задачі сортування.

4.Які методи сортування вам відомі?

5.Наведіть приклади алгоритмів сортування та оцінки їх ефективності.

6.Суть алгоритму сортування вставкою та його ефективність. У яких випадках доцільно його використовувати?

7.Суть алгоритму сортування вибором та його ефективність. У яких випадках доцільно його використовувати?

8.Суть алгоритму сортування обміном (бульбашкове сортування) та його ефективність. У яких випадках доцільно його використовувати?

9.Суть алгоритму швидкого сортування та його ефективність. У яких випадках доцільно його використовувати?

10.Суть алгоритму пірамідального сортування та його ефективність. У яких випадках доцільно його використовувати?

11.Суть алгоритму сортування методом злиття та його ефективність. У яких випадках доцільно його використовувати?

86

Лабораторна робота № 15

Тема: Пошук

Студент повинен знати: постановку задачі пошуку, області застосувань алгоритмів пошуку, алгоритми послідовного та бінарного пошуку та оцінки їх ефективності, застосування цих алгоритмів до розв’язування практичних задач.

Теоретичні відомості

Задача пошуку є фундаментальною в комбінаторних алгоритмах. У загальному її можна сформулювати так: «Дослідити множину Т з метою відшукання елемента, що задовольняє деяку умову С». Ефективність алгоритму пошуку суттєво залежить від структури множини Т.

Для отримання відповіді на питання «скільки існує способів…», «перерахуйте всі можливі…» та інше, зазвичай треба дослідити множини всіх можливих розв’язків, тобто виконати так званий вичерпний пошук. Існують загальні методи вичерпного пошуку – пошук із поверненням (бектрекінг) та метод решета. Пошук із поверненням використовується у широкому класі задач, що включають граматичний розбір, ігри та складання розкладів. На кожному кроці вичерпного пошуку робиться спроба розширити частковий розв’язок із метою отримання шуканого розв’язку. Метод решета є логічним доповненням вичерпного пошуку і полягає у виключенні тих об’єктів, що не є розв’язками. Цей метод корисний перш за все для теоретико-числових задач.

Важливим класом алгоритмів пошуку є алгоритми на графах, зокрема деревах. До них відносять алгоритми пошуку найкоротших шляхів між вершинами графа, пошуки в глибину і ширину, пошук максимального потоку в мережі, алгоритми обходу дерев.

Будемо розглядати структури даних, які є масивами або файлами. Для цих структур найпростішими алгоритмами пошуку є послідовний та бінарний (двійковий) пошук.

Послідовний пошук. Під послідовним пошуком розуміють дослідження елементів в тому порядку, у якому вони розташовані в послідовності (масиві, файлі). Нехай X[1], X[2],…, X[n] – масив із n елементів, і в цьому масиві треба знайти елемент Z, якщо він є. Алгоритм послідовного пошуку полягає у послідовному порівнянні елементів масиву X, починаючи з першого, із Z до тих пір, поки не знайдемо Z або не з’ясуємо, що Z у масиві немає. Доцільно доповнити масив елементом, який шукаємо, тобто присвоїти X[n+1]:=Z. Тоді алгоритм послідовного пошуку матиме вигляд:

X[n+1]:=Z;

i:=1;

while Z<>X[i] do i:=i+1;

if i<=n then {елемент X[i] співпадає із Z} else {Z не міститься в масиві}

До основних алгоритмів для послідовностей елементів відносять алгоритми пошуку мінімального чи максимального елемента. Такі алгоритми легко реалізувати через послідовний пошук, вибравши за початковий мінімальний (максимального) елемент перший елемент послідовності. Для прикладу, алгоритм пошуку мінімального елемента масиву Х має вигляд.

K:=1; {K – індекс мінімального елемента} Min:=X[1];

for i:=1 to n do if Min>X[i] then

begin Min:=X[i]; K:=i end;

Даний алгоритм знаходить мінімальний елемент та його індекс.

87

Ефективність алгоритму послідовного пошуку в гіршому випадку рівна O(n), бо треба переглядати всі елементи масиву, якщо шуканого елемента немає.

Бінарний пошук. Цей вид пошуку використовується до упорядкованих послідовностей. Нехай дано упорядкований масив X[1]≤X[2]≤ … ≤X[n], у якому треба знайти елемент Z. Спочатку Z порівнюється із середнім елементом масиву, тобто з елементом

X[(n+1) div 2]. Якщо Z = X[(n+1) div 2], то пошук завершується. Якщо Z < X[(n+1) div 2], то розглядаємо ліву частину масиву, тобто X[1], X[2],…, X[(n+1) div 2 -1], а якщо Z > X[(n+1) div 2], то розглядаємо праву частину масиву, тобто X[(n+1) div 2 +1], X[(n+1) div 2 +2],…, X[n]. У вибраній частині шукаємо Z. Для цього Z знову порівнюємо із середнім елементом вибраної чистини масиву, і якщо знову Z не співпадає із середнім елементом, то визначаємо нову частину масиву, у якій будемо шукати Z. На кожному кроці алгоритму вибрана частина масиву для пошуку Z ділиться навпіл. Тому алгоритм припинить свою роботу, якщо буде знайдено Z або розмір частини масиву стане рівним 1. Фрагмент алгоритму бінарного

end;

if J>0 then {елемент Z співпадає з X[J]}

else {елемент Z не міститься в масиві}

Якщо початковий масив упорядкований за спаданням, то в цьому фрагменті алгоритму треба поміняти вибір лівого та правого країв масиву, у якому здійснюється пошук. Алгоритм бінарного пошуку дуже ефективний, і його часова складність O(log2 n).

Приклад

Дано масив. Знайти в масиві елемент x=13 і вивести його номер.

l:=1; r:=n;

While (l<=r) and Not found do begin

m:=(l+r) div 2;

if x>a[m] then l:=m+1

else if x<a[m] then r:=m-1 else found :=true

end;

if found then Writeln(‘Номер шуканого елемента:’,m) else Writeln(‘Заданого елемента немає’);

end.

88

☺ Завдання для виконання

Основний рівень

1.Дано упорядкований масив із N цілих чисел. Скласти програму пошуку в цьому масиві елементів, квадрат яких більший за 100. Вивести кількість цих елементів.

2.Скласти програму пошуку в упорядкованому масиві з N цілих чисел елемента, який у сумі з останнім елементом дорівнював би 65. Вивести відповідні повідомлення при наявності такого елемента в масиві або при його відсутності.

3.Дано файл цілих чисел a1 ,..., an , які упорядковані за спаданням. Знайти серед цих чисел ті, що більші за середнє арифметичне суми всіх елементів. Вивести ці числа на екран.

4.Дано файл цілих чисел a1 ,..., an , які упорядковані за неспаданням. Знайти серед цих чисел номер першого нуля.

5.Дано файл цілих чисел a1 ,..., an , які упорядковані за незростанням. Знайти перший елемент цієї послідовності, який стоїть після двох поруч розташованих нулів. Вивести на екран цей елемент і його номер. Якщо ж такого елемента немає, то вивести відповідне повідомлення.

6.Дано файл дійсних чисел a1 ,..., an , що упорядковані за спаданням. Знайти заданий елемент x. Якщо елемента х немає, то вставити його у файл так, щоб файл залишився упорядкованим за спаданням.

7.Дано файл дійсних чисел a1 ,..., an , що упорядковані за зростанням. Знайти серед цих чисел елемент, рівний x2 (x попередньо задати).

8.Дано файл дійсних чисел a1 ,..., an , упорядкованих за зростанням. Знайти серед цих чисел перший елемент, синус якого більший за –0.89.

9.Дано цілі числа a1 ,..., an , упорядковані за спаданням. Знайти номер першого елемента, який більший за даний елемент. Вивести знайдений елемент і його номер на екран.

10.Дано файл натуральних чисел a1 ,..., an , упорядкованих за неспаданням. Підрахувати найбільшу кількість однакових елементів x (x попередньо задати).

11.Дано послідовність додатніх дійсних чисел a1 ,..., an , упорядкованих за спаданням. Знайти серед елементів цієї послідовності ті, корінь квадратний із яких більший за середнє арифметичне першого і останнього елементів послідовності.

12.Дано файл дійсних чисел a1 ,..., an (n ввести з клавіатури), упорядкованих за зростанням. Вивести елементи, які більші за даний елемент x.

13.Дано файл дійсних чисел a1 ,..., an (n ввести з клавіатури), упорядкованих за неспаданням. Вивести на екран номер першого елемента, що безпосередньо розташований за двома однаковими елементами.

14.Дано файл дійсних чисел a1 ,..., an (n ввести з клавіатури), упорядкованих за спаданням. Знайти серед цих чисел елемент, рівний середньому арифметичному всіх елементів даного файлу.

15.Дано масив дійсних чисел a1 ,..., an , упорядкованих за зростанням. Знайти номер першого

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

89

Підвищений рівень

1.Нехай у бухгалтерії створено файл записів із полями: прізвище співробітника, рік народження, заробітна плата. Вивести прізвища тих співробітників, у яких заробітна плата більше 650 грн.

2.Дано файл записів, полями якого є відомості про врожай у колгоспі: назва посівної культури, рік посіву, урожайність (у відсотках).Вивести на екран відомості про врожай за 1998 рік.

3.Дано файл записів телефонної станції. Полями запису є прізвище абонента, його номер телефону. Знайти всі номери абонентів, прізвища яких починаються з приголосного.

4.Дано файл записів, полями якого є ідентифікаційний номер студента, розмір стипендії, курс, на якому він навчається. Вивести на екран відомості про стипендію студентів, які навчаються на 5-му курсі.

5.Дано файл записів, полями яких є номер випускного року, кількість випускників із золотими медалями, кількість випускників зі срібними медалями. Вивести на екран рік, у якому було випущено учнів із найбільшою кількістю золотих медалей.

6.Створити файл записів про відомості овочевої бази. Полями запису є назва овочу (буряк, морква, капуста, картопля), дата його надходження, кількість у тонах. Вивести на екран відомості про надходження і кількість моркви. Обчислити загальну кількість моркви.

7.Створити файл записів Укрпошти з полями: індекс, вид видання (журнал або газета) назва видання, вартість, прізвище замовника. Вивести відомості про прізвища замовників, які підписалися на газету "Голос України".

8.Створити файл записів із полями: назва вулиці, кількість будівель на цій вулиці, рік виникнення назви вулиці. Вивести на екран назви вулиць, які виникли після N-го року.

9.Створити файл записів про студентів деякої групи, куди занести прізвище і оцінки за останню зимову сесію. Знайти середній бал успішності студентів даної групи. Вивести прізвища студентів, успішність яких вище середньої.

10.Створити файл записів із полями: назва вулиці, кількість будівель на цій вулиці, рік виникнення назви вулиці. Підрахувати і вивести на екран кількість будівель, які були побудовані за роки від N до M.

11.Створити файл записів про табір "Червоні вітрила" з полями: прізвище, вік дитини, стать, назва загону, номер зміни. Вивести на екран відомості про хлопчиків 2-ої зміни.

12.Створити файл записів із полями: прізвище, номер квартири, дата заселення. Вивести на екран відомості про мешканців, прізвища яких починаються з голосного.

13.Створити файл записів із полями: прізвище хворого, дата, з якої він потрапив у лікарню, дата одужання. Вивести прізвища хворих, які потрапили у лікарню пізніше певної дати.

14.Створити файл записів із полями: прізвище мешканця, номер квартири, дата заселення, кількість мешканців у квартирі. Знайти всі дані по мешканців, які заселилися першими.

15.Створити файл записів із полями: назва товару, ціна, кількість, дата постачання. Для комп’ютерної фірми повідомте, який товар користується найбільшим попитом (постачається найчастіше).

90