Лабораторна робота №10 Тема: Множини. (2 години) Мета: Формувати вміння і навички обробки множин засобами мови програмування Pascal. Література: Архангельский А.Я. Язык Pascal и основы программирования в Delphi Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с. Культин Н.Б. Turbo Pascal в задачах и примерах М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0 Меженный О.А. Turbo Pascal Н.Вирт. Алгоритмы + структуры данных = программы. Москва, Мир, 1985 г. 406 с. Н.Вирт. Алгоритмы и структуры данных. Москва, Мир, 1989 г. 420 с. Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с. Павловская Т.А. Паскаль. Программирование на языке высокого уровня Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. – Учебное пособие. – М.: Издательство «ОМД Групп», 2003 г. -616 с. Фаронов В.В. Turbo Pascal 7.0. Практика программирования Фаронов В.В. Turbo Pascal 7.0. Учебный курс Короткі теоретичні відомості. Ще одним складним стандартним типом даних, що визначений у мові Pascal, є множинний тип. Значенням множинного типу даних є множина, що складається з однотипних елементів. Тип елемента множини називається базовим типом. Базовим типом може бути скалярний або обмежений тип. Таким чином, множина значень множинного типу – це множина всіх підмножин базового типу, враховуючи і порожню множину. Якщо базовий тип містить N елементів, відповідний множинний тип буде містити 2N елементів. Характерна відміна множинного типу – визначення на ньому найбільш поширених теоретико-множинних операцій і відношень. Це робить множинний тип схожим на прості типи даних. Множинні типи описуються в розділі типів наступним чином: Type < ім’я типу > = Set of < базовий тип >
Множини будуються з своїх елементів за допомогою конструктора множин. Конструктор являє собою перелік через кому елементів множини або відрізків базового типу, що береться у дужки [ , ]. Порожня множина позначається через [ ]. До операндів - однотипних множин А і В можна застосувати такі дії: А + В - об’єднання А U В А * В - перетин А ? В А - В - різниця А \ ВМіж А і В визначені також відношення порядку і рівності А = В, А <> В, А < В, А <= В, А > В, А >= В; Відношення порядку інтерпретуються як теоретико-множинні включення. Якщо А – множина і х – елемент базового типу, то визначено відношення належності х in A - x належить A ( x ? A ). Кожне з відношень, описаних вище, по суті, є операцією, результат якої має тип Boolean. Таким чином, якщо Init – змінна типу Boolean, можливе присвоювання Init := A < B. Можливі такі порівняння ( А = В ) = ( С = D ). Наявність операцій над множинами дозволяє застосовувати в програмах оператори присвоювання, в лівій частині яких стоїть змінна типу множини, а в правій – вираз того ж типу. При реалізації мови розміри множин завжди обмежені константою, що залежить від реалізації. Як правило, ця константа кратна довжині машинного слова. Це відбувається тому, що множини реалізовані у вигляді логічних (двійкових) векторів наступним чином: кожній координаті двійкового вектора однозначно відповідає один з елементів базового типу. Якщо елемент а належить множині А, що представляється, то значення координати вектора, що відповідає а, дорівнює 1. У протилежному випадку значення відповідної координати дорівнює 0. Наприклад, якщо множина А описана як Set of 0..15, то його представляє 16-ти вимірний двійковий вектор, координати якого перенумеровані від 0 до 15, і і-тій координаті відповідає елемент і базового типу. Базовий тип : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Двійковий вектор : 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 Представлена множина : A = [2, 3, 5, 7, 11, 13] Такий спосіб реалізації дозволяє швидко виконувати операції над множинами і перевіряти теоретико-множинні відношення. Нариклад, For X := 'A' to 'Z' do If (X ='A') or (X ='E') or (X ='I') or (X ='O') or (X='U') then Statement1 else Statement2 У Pascal максимальна кількість елементів у множині дорівнює 256. Таким чином, у якості базового типу можна вибирати, наприклад, Char або відрізок 0..255. На завершення розділу, наведемо приклад програми, що використовує множинні типи даних. Задачі для самостійного розв’язування Записати за допомогою конструктора множину Х, яка складена з латинських букв a, b, c, d, i, j, k, x, y, z. Записати за допомогою конструктора множину з трьох основних кольорів множинного типу Paint. Записати за допомогою конструктора множину цілих розв’язків квадратної нерівності x^2 +p*x + q < 0 у припущенні, що корені відповідного квадратного рівняння лежать в інтервалі [0; 255]. Записати за допомогою конструктора множину простих чисел-близнюків з інтервалу 1..30. Дано рядок. Скласти програму, яка б рахувала кількість різних цифр, що зустрічаються в рядку, використовуючи множини. Дано рядок з прописних латинських літер, сусідні слова в якому розділені пропуском. Скласти програму, яка б друкувала в алфавітному порядку приголосні літери, які входять до рядку, у разі якщо таких немає вивести NO. (Голосні літери – a, e, i, o, u, y, інші - приголосні). Дано два рядка. Скласти програму, яка б виводила всі символи (у порядку зростання ASCII кодів), що є в першому рядку та яких немає у другому, використовуючи множини. Дано число N. Скласти програму, яка б виводила на екран всі пості числа від 2 до N, використовуючи множини. Дано рядок. Скласти програму, яка б рахувала кількість різних розділових знаків, що зустрічаються в рядку, використовуючи множини. Дано рядок з прописних латинських літер, сусідні слова в якому розділені пропуском. Скласти програму, яка б друкувала в алфавітному порядку голосні літери, які входять одночасно до кожного слова, у разі якщо таких немає вивести NO. (Голосні літери – a, e, i, o, u, y, інші - приголосні). Тема: Комбінований тип даних. Записи. (2 години) Мета: Ознайомити з поняттям комбінованого типу даних. Формувати вміння і навички обробки записів засобами мови програмування Pascal. Література: Архангельский А.Я. Язык Pascal и основы программирования в Delphi Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с. Культин Н.Б. Turbo Pascal в задачах и примерах М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0 Меженный О.А. Turbo Pascal Н.Вирт. Алгоритмы + структуры данных = программы. Москва, Мир, 1985 г. 406 с. Н.Вирт. Алгоритмы и структуры данных. Москва, Мир, 1989 г. 420 с. Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с. Павловская Т.А. Паскаль. Программирование на языке высокого уровня Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. – Учебное пособие. – М.: Издательство «ОМД Групп», 2003 г. -616 с. Фаронов В.В. Turbo Pascal 7.0. Практика программирования Фаронов В.В. Turbo Pascal 7.0. Учебный курс Короткі теоретичні відомості. Крім регулярних типів, у мові визначені ще деякі складні типи. Кожне таке визначення задає свій, характерний механізм об’єднання даних у єдине ціле і механізм доступу до даних – компонент складеного даного. Значеннями так званого комбінованого типу даних є записи. Комбінований тип задає образ структури об’єкта – даного цього типу, кожна частина якого (поле) може мати зовсім різні характеристики. Таким чином, запис – це набір різнотипних даних, що об’єднані спільним іменем. Більш формально, запис містить визначене число компонент, що називаються полями. У визначенні типу запису задається ім’я і тип кожного поля запису: <комбінований тип >::= Record < список полів > End <список полів>::= <фіксов. част.> | <фіксов. част.>; <варіант. част.> | <варіант. част.> <фіксована частина >::= <секція запису > {,<секція запису >} < секція запису >::= <ім’я поля >{,<ім’я поля >}:< тип > < пусто > Синтаксис записів, які містять варіантну частину, – записів з варіантами – ми визначимо нижче. Відповідні синтаксичні діаграми записів з варіантами:
При позначенні компоненти запису в програмі слідом за іменем запису ставиться крапка, а потім ім’я відповідного поля. Таким чином здійснюється доступ до цієї компоненти. Наприклад: 1) z1.Re := 2; z1.Im := 3; M := sqrt(sqr(z1.Re) + sqr(z1.Im)); 2) S.F1 := Group[i].F1; S.Year := Group[i + 1].Year; writeln( Group[i].StudDoc); Запис може входити у склад даних більш складної структури. Можна говорити, наприклад, про масиви і файли, що складаються з записів. Запис може бути полем іншого запису. Синтаксис комбінованого типу містить і варіантну частину, що припускає можливість визначення типу, який містить визначення декількох варіантів структури. Наприклад, запис у комп’ютерному каталозі бібліотеки може мати наступну структуру:Фіксована частина Прізвище Ім’я по батькові {автора}
Назва {книги}
Видавництво {його атрибути}
Шифр {бібліотеки}
Стан (видана, у фонді, в архіві)
Варіантна частина Значення признака видана у фонді в архіві
Поля ВаріантноїЧасти Прізвище ім’я, по батьковіN% {чит.квитка}Дата {видачі} адрес {схову} ім’я {архіву}адрес {схову}дата {архівації)
Синтаксис варіантної частини: <варіантна частина >::= case <поле ознаки > <ім’я типа > of < варіант >{;<варіант >} < варіант >::=<список міток варіанта>:(<список полів>)|< пусто > <список міток варіанта >::=<мітка варіанта >{;<мітка варіанта >} <мітка варіанта >::=< константа > <поле ознаки >::=<ім’я >:< пусто > Відповідні синтаксичні діаграми:
Опис типу запису в розглянутому прикладі може мати вид: Book = record Author : FullName; {фіксована частина} BookName: String; BookCode: Code; Station : (Readed, inFile, inArchive); case Station of {поле ознаки}Readed: Reader : FullName; {варіантна частина}ReadCode : Integer;ReadDate : Date; inFile: FilAdress : Adress; inArc : ArcName : Srting; ArcAdress: Adress endend; Приведені вище позначення можна скоротити за допомогою оператора приєднання. Заголовок цього оператора відкриває область дії “внутрішніх” імен полів запису, які можуть бути використані як імена змінних. Оператор приєднання має вид: With <змінна-запис > {,<змінна-запис >} do < оператор > with A do begin F1 := ' Іванов '; F2 := ' Ілля '; F3 := ' Інокентійович '; Day := 14; Month := 9; Year := 1986; StudDoc := 123; end { оператора with } Задачі для самостійного розв’язування Опишіть тип запису – клітинки розкладу занять для своєї спеціальності і курсу. Сформуйте файл двотижневого розкладу для своєї підгрупи. Розробіть програму, яка визначає кількість лекційних, практичних і лабораторних занять у двотижневому циклі для своєї підгрупи за вказаною дисципліною. Опишіть тип запису – відомості про студента групи, що необхідні декану факультету. Сформуйте файл студентів своєї підгрупи. Розробіть програму, яка визначає стан успішності в підгрупі. Опишіть тип запису – відомості про батьків учнів класу, що необхідні класному керівнику. Сформуйте файл, що складається не менш, ніж з восьми учнів “Вашого” класу. Розробіть програму, яка за прізвищем та ім’ям учня друкує відомості про його батьків. Опишіть тип запису – відомості про успішність учня, що необхідні для вчителя-предметника зі свого предмета. Сформуйте файл, що складається не менш, ніж з восьми учнів “Вашого” класу. Розробіть програму, яка визначає найслабшого і найсильного учнів класу. Опишіть тип запису – рядок залікової книжки (екзаменаційна частина). Сформуйте файл іспитів, зданих Вами. Розробіть програму, яка визначає середній бал, складає список екзаменаторів і за номером семестру роздруковує результати Вашої сесії. Опишіть тип запису – рядок залікової книжки (залікова частина). Сформуйте файл заліків, зданих Вами. Розробіть програму, яка визначає дні, коли Ви здавали по два і більше заліків. Опишіть тип запису – відомості про вік, зріст і вагу учня. Сформуйте файл, що складається не менш, ніж з восьми учнів “Вашого класу”. Розробіть програму, яка визначає всіх учнів, що народилися в даний проміжок часу, вказаний датами початку і кінця, і визначає середній зріст і середню вагу цієї групи учнів. Опишіть тип запису – відомості про книгу (наприклад, з інформатики). Сформуйте файл книг, що необхідні учителю інформатики. Складіть програму, яка підбирає книги для курсу, номер якого вводиться, друкує імена їх авторів та рік видання. Опишіть тип запису – відомості про товар у магазині. Сформуйте файл товарів, що є в магазині. Розробіть програму коригування масиву товарів і визначення виручки магазину на даний момент часу. Опишіть тип запису – рядок у телефонній книзі. Сформуйте файл записів – вашу телефонну записну книжку. Розробіть програму пошуку номера телефона за прізвищем і пошуку адреси за номером телефона. Тема: Робота з файлами. Текстові файли. (2 години) Мета: Ознайомити з поняттям файлу. Формувати вміння і навички обробки текстових файлів мови програмування Pascal. Література: Архангельский А.Я. Язык Pascal и основы программирования в Delphi Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– М.: Мир, 1979.– 536 с. Культин Н.Б. Turbo Pascal в задачах и примерах М.С.Львов, О.В. Співаковський. Основи алгоритмізації та програмування. Марченко А.И., Марченко Л.А. Программирование в среде Turbo Pascal 7.0 Меженный О.А. Turbo Pascal Н.Вирт. Алгоритмы + структуры данных = программы. Москва, Мир, 1985 г. 406 с. Н.Вирт. Алгоритмы и структуры данных. Москва, Мир, 1989 г. 420 с. Немцова Т.И., Голова С.Ю., Абрамова И.В. Программирование на языке высокого уровня. программирование на языке Object Pascal Окулов С.М. Основы программирования.– М.: ЮНИМЕДИАСТАЙЛ, 2002.– 424 с. Павловская Т.А. Паскаль. Программирование на языке высокого уровня Пильщиков В.Н. Сборник упражнений по языку Паскаль. Москва, Наука, 1989 г., 160 с. Фаронов В.В. Turbo Pascal 7.0. Начальный курс. – Учебное пособие. – М.: Издательство «ОМД Групп», 2003 г. -616 с. Фаронов В.В. Turbo Pascal 7.0. Практика программирования Фаронов В.В. Turbo Pascal 7.0. Учебный курс Короткі теоретичні відомості. Програма, яка написана мовою Pascal, повинна якимось чином обмінюватись даними з зовнішніми пристроями (отримувати дані з клавіатури, магнітного диска, виводити дані на екран, принтер і т.д.) Для роботи з зовнішніми пристроями використовуються файли. Файли - це значення файлового типу даних - ще одного стандартного складного типу в мові. Файл – це послідовність однотипних компонент, яка має ознаку кінця і оброблюється послідовно – від початку до кінця. Порядок компонент визначається самою послідовністю, подібно до того, як порядок слідування чергового кадру кінофільму визначається його розташуванням на кіноплівці. У будь-який момент часу доступний тільки один елемент файла (кадр кінофільму). Інші компоненти доступні тільки шляхом послідовного просування по файлу. У результаті виконання програми відбувається перетворення одного текстового файла (який називається Input) в інший текстовий файл (який називається Output). Обидва ці файли є стандартними і використовуються для введення /виведення даних. Над файлами можна виконувати два явних види дій: Перегляд (читання) файла. Створення (запис) файла - виконується шляхом приєднання нових компонент у кінець початково порожнього файла. Файли, з якими працює програма, повинні бути описані в програмі. Частина файлів (що являють собою фізичні пристрої) має в операційній системі стандартні імена. Наприклад, для читання даних з клавіатури і виведення результатів на екран монітора ми користуємось стандартними файлами Input і Output. Файл - принтер має ім’я Prn:Імена нестандартних файлів, що використовуються в програмі, необхідно описувати у розділі змінних. Опис файлового типу відповідає діаграмі:
Файл, компоненти якого є символами, називається текстовим. Він має стандартний тип Text: Type Text = File of Char; Приклади: Type ExtClass = File of Person; CardList = File of Integer;Var F : Text; Data : File of real; List1, List2 : CardList; Class10A, Class10B : ExtClass; Для роботи з нестандартними файлами ім’я файла повинно бути зв’язане з реально існуючим об’єктом – зовнішнім пристроєм. А саме, якщо нам необхідно обробити дані з файла, що знаходиться на магнітному диску і який має (зовнішнє) ім’я D:\ExtName.dat, ми повинні повідомити системі, що працюючи з файлом IntName (читаючи з нього дані або записуючи у нього дані), ми працюємо з файлом ExtName.dat, який знаходиться на диску D:. Для ототожнення внутрішнього імені файла з зовнішнім іменем використовується процедура Assign(< внутрішнє ім’я >, < 'зовнішнє ім’я ' >). Після того, як ім’я файла описано і визначено, можна приступити до роботи з файлом. При використанні нестандартних файлів треба пам’ятати, що перед роботою необхідно відкрити їх, тобто зробити доступними з програми. Для цього треба застосувати одну з двох наступних процедур: Процедура Rewrite(<ім’я файла>) – відкриває файл для запису. Якщо файл раніше існував, всі дані, що зберігались у ньому, знищуються. Файл готовий до запису першої компоненти. Процедура Reset(<ім’я файла>) – відкриває файл для читання. Файл готовий для читання з нього першої компоненти. По закінченні роботи з файлом (на запис) він повинен бути закритий. Для цього використовується процедура Close(<ім’я файла>). Ця процедура виконує всі необхідні машинні маніпуляції, що забезпечують збереження даних у файлі. Для обміну даними з файлами використовують процедури Read і Writе. Процедура Read (<ім’я файла>,<список введення>), читає дані з файла ( по замовченню ім’я файла - Input). Список введення – це список змінних. Процедура Writе (<ім’я файла>,<список виведення>), записує дані у файл ( по замовченню ім’я файла - Output). Список виведення – це список виразів. Якщо F – файл типу Text, то у списку введення/виведення допустимі змінні/вирази типу Integer, Real, Char, String[N]. В інших випадках типи всіх компонент списку повинні співпадати з типом компоненти файла. При роботі з файлами застосовують стандартні логічні функції: Eof(F) (end of file) – стандартна функція – ознака кінця файла. Якщо файл F вичерпаний, то Eof(F) = True, в протилежному випадку Eof(F) = False. Eoln(F) (End of line) – стандартна функція – ознака кінця рядка текстового файла. Якщо рядок текстового файла F вичерпаний, то Eoln(F) = True, в протилежному випадку Eoln(F) = False. Функція Eoln визначена тільки для файлів типа Text. Звичайно в програмах використовують або текстові файли, або файли, компонентами яких є структуровані дані (наприклад, записи). Треба пам’ятати, що дані файлових типів не можна використовувати в якості компонент інших структур даних. Наприклад, не можна визначити масив, компонентами якого є файли, запис, полем якої є файл. Упорядкованість компонент файла за одним або кількома ключовими полями – одна з основних умов ефективної реалізації задач обробки файлів. Так, задача роздруку файла у визначеному порядку слідування компонент, якщо файл не впорядкований відповідним чином, розв’язується за допомогою багатократних переглядів (прогонів) файла. Кількість прогонів при цьому пропорційна кількості компонент. Відсутність прямого доступу до компонент приводить до того, що розглянуті вище алгоритми сортувань масиву неможливо ефективно адаптувати для сортування файла. На відміну від масивів, основні критерії ефективності алгоритму сортування файла – кількість прогонів файлів і кількість проміжних файлів. Так, наприклад, алгоритм сортування простими обмінами потребує N прогонів файла, що сортується (N – кількість компонент файла). Алгоритм швидкого сортування взагалі не має сенсу розглядати, оскільки при його реалізації необхідно було б читати файл від кінця до початку! Розглянемо тому новий для нас алгоритм – алгоритм сортування злиттям, який найбільш ефективний при сортуванні файлів, і відноситься до швидких алгоритмів при сортуванні масивів, хоча і потребує додаткової пам’яті. Приклад. Програма формування файла як вибірки з компонент іншого файла. Нехай F - файл записів виду (поле ключа, поле даних). Треба сформувати файл G, який містить ті компоненти F, ключі яких задовольняють умові: значення ключа – ціле число з інтервалу [Max, Min]. Program FileForm; Type Component = Record Key: Integer; { поле ключа } Data: String[20] { поле даних} End; OurFile = File of Component; Var F, G : OurFile; X: Component; Max, Min : Integer; Function Correct(var U: Component): Boolean; begin Correct := (U.Key < Max) and (U.Key > Min) end; Begin Read(Max, Min); Assign(F, 'D:InpFile.dat'); {визначення значення F } Assign(G, 'D:OutFile.dat'); {визначення значення G } Reset(F); {файл F відкритий для читання} Rewrite(G); {файл G відкритий для запису} While not(Eof(F)) do begin {цикл читання F - запису G} Read(F, X); If Correct(X) then Write(G, X) end; Close(G) {файл G закритий} End. Задачі для самостійного розв’язування Знайти у файлі F всі оборотні слова і скласти з них файл G. Знайти у файлі F входження слова p, замінити їх на слово q, отримавши новий файл G. Знайти у файлі F всі слова, що представляють числа (у десятковому запису) і отримати числовий файл G, що містить знайдені числа. Знайти у файлі F всі однобуквенні слова і зайві пробіли, і, вилучивши їх, отримати новий файл G. Знайти у файлі F всі слова, що зустрічаються більше одного разу, і скласти файл G, вилучивши з F знайдені слова. У файлі F знайти всі слова, що містять подвоєння букв і скласти з них файл G. Знайти у файлі F всі слова, що містять підслово p, і скласти з них файл G. Дано файл F. Відсортувати його в алфавітному порядку. Дано слово p і файл F. Знайти в F всі слова, які можна скласти з букв слова p. Дано текстовий файл, що містить символьні рядки. Знайти в файлі всі слова, які містять подвійні літери і скласти з них новий файл ‘q.txt’. Вивести вміст нового файлу. Ім’я даного файлу задається користувачем.
