close

Вход

Забыли?

вход по аккаунту

?

Barikov

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
Л. Н. Бариков
БАЗОВЫЕ АЛГОРИТМЫ
ОБРАБОТКИ ИНФОРМАЦИИ
Учебное пособие
Санкт-Петербург
2014
УДК 004.4
ББК 32.97
Б24
Рецензенты:
кафедра компьютерной математики и программирования
Института №4 Санкт-Петербургского государственного университета
аэрокосмического приборостроения;
канд. техн. наук, доцент В. П. Ильин
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Бариков, Л. Н.
Б24 Базовые алгоритмы обработки информации: учеб. пособие/
Л. Н. Бариков. – СПб.: ГУАП, 2014. – 139 с.: илл.
ISBN 978-5-8088-0907-9
Содержатся материалы, необходимые для выполнения всех видов работ, предусмотренных учебным планом по дисциплине «Программирование. Базовые алгоритмы обработки информации».
Предназначено для студентов, обучающихся по направлению
230100.62 «Информатика и вычислительная техника» (профиль –
«Вычислительные машины, комплексы, системы и сети») на очной
форме обучения.
Подготовлены к публикации кафедрой вычислительных систем
и сетей по рекомендации методической комиссии Института вычислительных систем и программирования Санкт-Петербургского государственного университета аэрокосмического приборостроения.
УДК 004.4
ББК 32.97
ISBN 978-5-8088-0907-9
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения (ГУАП), 2014
© Л. Н. Бариков, 2014
ВВЕДЕНИЕ
Учебное пособие содержит информационный материал, необходимый студентам очной формы обучения по направлению
230100.62 (профиль «Вычислительные машины, комплексы, системы и сети») для успешного освоения теоретического курса и
выполнения лабораторных работ по дисциплине «Программирование. Базовые алгоритмы обработки информации». Приводятся
необходимые теоретические материалы, методические указания к
выполнению лабораторных работ, варианты индивидуальных заданий и примеры их выполнения.
В пособие включен перечень тем, составляющих содержание
теоретического курса по этой дисциплине с указанием объема занятий в часах.
Кроме того, в пособии содержится подробный перечень основной и дополнительной литературы по этой дисциплине, а также
перечень действующих Государственных стандартов, которые требуется соблюдать при выполнении лабораторных работ.
Дальнейшее обучение программированию осуществляется в
рамках дисциплины «Программирование. Программирование на
языках высокого уровня». Необходимые для этого теоретические
материалы, а также методические указания по выполнению курсовой и лабораторных работ приведены в пособии [3].
3
1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ
Цель преподавания дисциплины – дать студентам представление о современном состоянии алгоритмизации, методах разработки алгоритмов и программ, а также развить практические навыки
разработки алгоритмов и структурных программ для обработки
информации с использованием инструментальных средств проектирования программ.
В области воспитания личности целью подготовки по данной
дисциплине является формирование следующих социально-личностных и общекультурных качеств:
− целеустремленность, организованность, трудолюбие, ответственность.
В результате изучения дисциплины студенты должны:
− знать
технологию разработки алгоритмов и программ,
методы отладки и решения задач на ЭВМ в различных режимах,
основные стандарты в области инфокоммуникационных систем
и технологий, в частности стандарты Единой системы программной документации;
− уметь
ставить задачу и разрабатывать алгоритм ее решения,
использовать прикладные системы программирования,
разрабатывать основные программные документы;
− иметь представление
о современном состоянии средств разработки программ, тенденциях развития средств и систем для проектирования программ.
4
2. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
Распределение фонда учебного времени и форма контроля
Вид учебной работы, ч
Аудиторные занятия, всего
В том числе:
лекции
лабораторные работы
Индивидуальная работа преподавателя
Самостоятельная работа, всего
Форма итогового контроля
Всего
85
34
51
36
23
экз.
Теоретический курс включает следующие разделы и темы.
1. Основы алгоритмов обработки информации
Тема 1.1. Этапы решения задач на ЭВМ. Постановка задачи и
спецификация программы. Формализация задачи. Алгоритмизация. Программирование. Тестирование и отладка. Документирование. Сопровождение программы.
Тема 1.2. Основы алгоритмизации. Алгоритмы. Свойства и способы записи алгоритма: естественные языки, схемы, структурограммы, псевдоязыки, языки программирования. Основные правила разработки алгоритмов. Базовые алгоритмические структуры: следование, развилка, повторение. Способы их изображения.
Типы алгоритмов. Пошаговая детализация как метод проектирования алгоритмов.
Тема 1.3. Современные методы программирования. Технология
нисходящего проектирования программ. Методы структурного
программирования, процедурного программирования, модульного программирования. Технология восходящего проектирования
программ. Метод объектно ориентированного программирования.
Сущность структурного программирования: разбиение на подзадачи, нисходящее проектирование, стандартные структуры управления. Достоинства и недостатки. Правила проектирования и оформления структурных программ.
Понятие языка программирования. Этапы развития языков
программирования. Современные тенденции в области языков программирования. Сравнение развития языков в представлении данных и способах реализации алгоритмов. Сравнительная характеристика языков программирования высокого уровня. Синтаксис и
5
семантика. Способы описания синтаксиса – лингвистические формулы и синтаксические диаграммы. Структура языка программирования. Базовые элементы языка: алфавит, лексемы, выражения.
Предложения языка: описания и операторы. Программа на языке
высокого уровня: состав и структура. Критерии качества программы. Жизненный цикл программы.
Тема 1.4. Инструментальные средства разработки программ.
Современные интегрированные среды проектирования программ.
Состав и назначение элементов интегрированной среды программирования: текстовый редактор, транслятор, редактор связей, компоновщик, загрузчик, отладчик, инструктор, библиотекарь, профайлер. Схема обработки программы на языке программирования.
Трансляция, виды трансляторов. Основные этапы трансляции. Набор, редактирование, отладка и выполнение программ в интегрированной среде программирования. Интерфейс пользователя среды.
Выбор среды программирования. Среда программирования
Borland Pascal 7.0, PascalABC.NET, Delphi, Free Pascal. Этапы разработки программ.
2. Применение структурного программирования
для обработки информации
Тема 2.1. Разработка линейных программ. Описательные предложения языка программирования высокого уровня. Описание используемых библиотек, модулей, меток, констант, типов, переменных. Области действия описаний. Исполнительные предложения
языка высокого уровня. Представление основных управляющих
структур программирования.
Переменные и их типы. Порядковые и непорядковые типы данных. Дерево типов. Простые типы данных: целые, вещественные,
символьный, логический, перечисляемые и ограниченные типы.
Встроенные языковые средства для работы с данными простых и
порядковых типов. Преобразование типов данных. Средства реализации линейных алгоритмов: арифметические операторы, операторы присваивания, вызова функции, составной, пустой. Стандартные функции. Ввод/вывод в текстовом режиме.
Тема 2.2. Разработка разветвляющихся программ. Логический
тип. Переменные логического типа. Операторы сравнения. Логические операторы. Представление основных управляющих структур. Средства реализации разветвляющихся алгоритмов: условный
оператор, оператор выбора, оператор перехода. Обход. Выбор. Вло6
женные условные операторы. Примеры задач на составление логических выражений. Примеры задач на выбор варианта.
Тема 2.3. Разработка циклических программ. Представление
основных управляющих структур. Средства реализации циклических алгоритмов: операторы цикла с предусловием, с постусловием, с параметром. Условие выхода из цикла. Вложенные циклы.
Перебор вариантов. Зацикливание. Реализация арифметических,
итерационных и вложенных циклов. Вычисление номера шага.
Вычисления с заданной точностью. Циклы с переспросом. Примеры решения задач.
Тема 2.4. Реализация алгоритмов обработки массивов. Структурированные типы данных. Одномерные и многомерные массивы.
Статическое распределение памяти. Реализация алгоритмов сортировки структур данных и поиска в этих структурах. Вычислимость индекса. Переменные – флаги. Переменная – счётчик событий. Примеры решения задач на поиск экстремальных элементов в
векторе и матрице.
Тема 2.5. Реализация рекуррентных вычислений. Понятие итерации. Алгоритмические приёмы накопления суммы и произведения. Вычисления с помощью рекуррентных соотношений. Одномерные и многомерные рекуррентные соотношения. Примеры решения задач.
3. Применение процедурного программирования
для обработки информации
Тема 3.1. Подпрограммы. Процедуры и функции. Основные понятия. Принципы использования процедур и функций в программах. Параметры процедур и функций. Виды параметров: параметры-значения, параметры-переменные, параметры-константы. Вызов процедур и функций на исполнение. Формальные и фактические
параметры. Механизм передачи параметров. Процедурные типы.
Параметры процедурного типа. Примеры использования. Области
действия описаний процедур и функций. Внутренние и внешние
блоки. Локальность и глобальность. Организация интерфейса диалоговых программ. Примеры решения задач: методы сортировки
вектора, перемножение матриц, сортировка фрагментов матрицы.
Тема 3.2. Рекурсия. Понятие рекурсии. Рекурсивные определения и алгоритмы. Программирование рекурсивных алгоритмов:
рекурсивные процедуры и функции. Механизм рекурсивных вызовов. Бинарное дерево как рекурсивная структура данных. Рекур7
сивные процедуры обхода дерева: инфиксная форма, префиксная
форма, постфиксная форма. Особенности использования рекурсии
при построении дерева. Примеры решения задач.
Тема 3.3. Реализация алгоритмов обработки строк, множеств и
записей. Структурированные типы данных: строки постоянной и
переменной длины, множества, записи с постоянной и вариантной
частью. Встроенные языковые средства для работы со строками и
множествами. Примеры решения задач.
Тема 3.4. Реализация алгоритмов обработки файловых структур
данных. Файлы. Структурная организация. Виды файлов. Файлы
прямого и последовательного доступа к элементам. Файл как основное понятие баз данных и знаний. Файлы типизированные, не
типизированные, текстовые. Стандартные файлы ввода и вывода.
Встроенные языковые средства для работы с файлами разных видов. Примеры решения задач.
4. Применение модульного программирования
для обработки информации
Тема 4.1. Модули. Назначение, структура, трансляция, тестирование. Особенности использования модулей. Модульные программы. Стандартные модули в системах программирования: назначение и правила использования. Организация взаимодействия программных модулей. Построение многомодульных программ средствами языка программирования высокого уровня. Запуск внешних программ. Командная строка. Многопрограммные комплексы.
Тема 4.2. Реализация алгоритмов работы с динамическими
структурами данных. Динамические структуры данных. Указатели и ссылки. Встроенные языковые средства для работы с динамической памятью. Динамические массивы. Списки. Виды списков:
односвязные и двусвязные списки, линейные и циклические списки. Линейные списки: основные виды и способы реализации. Линейный список как абстрактный тип данных. Деревья. Виды деревьев и способы их реализации. Другие виды динамических структур: стек, очередь, дек. Правила использования памяти при работе
с динамическими структурами данных. Примеры решения задач.
5. Объектно ориентированное программирование
Тема 5.1. Объекты. Понятие. Объект как тип данных, определяемый пользователем. Основные свойства объектно ориентирован8
ного программирования: инкапсуляция, наследование и полиморфизм. Взаимосвязи между объектами. Статические и виртуальные
методы. Ранее связывание полей и методов. Позднее связывание.
Таблица виртуальных методов. Конструкторы и деструкторы. Событийно-управляемая модель.
Тема 5.2. Статические и динамические объекты. Объектные переменные. Статическое и динамическое выделение памяти. Стандартные процедуры по работе с динамическими объектами. Технология восходящего программирования. Примеры решения задач.
Распределение времени по темам и видам занятий
Наименование темы
1.1. Этапы решения задач на ЭВМ
1.2. Основы алгоритмизации
1.3. Современные методы программирования
1.4. Инструментальные средства разработки
программ
2.1. Разработка линейных программ
2.2. Разработка разветвляющихся программ
2.3. Разработка циклических программ
2.4. Реализация алгоритмов обработки массивов
2.5. Реализация рекуррентных вычислений
3.1. Подпрограммы
3.2. Рекурсия
3.3. Реализация алгоритмов обработки строк,
множеств и записей
3.4. Реализация алгоритмов обработки файловых структур данных
4.1. Модули
4.2. Реализация алгоритмов работы с динамическими структурами данных
5.1. Объекты
5.2. Статические и динамические объекты
Итого:
Кол-во учебных часов
СамостоЛек- Лабораторятельная
ции ные работы
работа
2
2
2
–
1
–
2
–
2
2
2
–
1
2
2
2
6
8
2
2
2
2
6
2
1
2
2
4
4
–
2
–
2
3
2
–
3
4
–
2
–
2
1
6
–
3
2
34
–
6
51
5
–
23
9
3. МЕТОДЫ И ТЕХНОЛОГИИ РАЗРАБОТКИ
АЛГОРИТМОВ И ПРОГРАММ
Основной целью программирования является построение надёжной, легко читаемой и модифицируемой программы, решающей поставленную задачу. Для этого программа должна иметь возможно
более простую структуру. Хотя задачи имеют различную сложность,
выбор варианта их решения в большинстве случаев должен определяться простотой восприятия, поэтому для того чтобы стать профессионалом, необходим опыт и знание основных принципов, выработанных программистами за время существования программирования.
Рассмотрим основные типы методов и технологии разработки
алгоритмов и программ.
Структурное программирование – метод создания достаточно
простых, понятных и легко читаемых программ, в которых используются только стандартные управляющие структуры.
Процедурное программирование – метод построения программы как совокупности её функциональных частей – процедур или
функций. Каждая процедура или функция представляет собой
функционально законченную последовательность действий и выполняется как единая операция.
Модульное программирование – организация программы в виде
совокупности независимых частей – модулей, со строгим порядком их
взаимодействия. В модулях группируются процедуры и функции по
их назначению. Модули разрабатываются и транслируются отдельно.
Объектно ориентированное программирование – метод программирования, основанный на использовании в программе совокупности объектов, каждый из которых содержит некоторые данные и методы их обработки. Объекты связываются между собой по
принципу наследования. Перечисленные методы реализуют одну
из возможных технологий современного программирования: нисходящую или восходящую.
Нисходящее проектирование – технология разработки программ, при которой на каждом шаге проектирования задача разбивается на более мелкие подзадачи так, что для любого момента
разработки найдется действующий вариант программы в терминах
выделенных подзадач.
Восходящее проектирование – технология разработки программ, при которой сначала проектируются и отлаживаются подпрограммы для выполнения простых операций, после чего они связываются в единую программу.
10
3.1. Сущность структурного программирования
Структурное программирование представляет собой метод, реализующий нисходящую технологию проектирования программ.
Структурное программирование предполагает:
− разбиение задачи на взаимодействующие более простые подзадачи;
− составление программы последовательными уточняющими
шагами сверху вниз;
− использование в программе только стандартных управляющих структур.
Иногда этот метод называют «программированием без goto» (без
использования оператора безусловного перехода). Однако никакие
принципы нельзя возводить в абсолют. Поэтому иногда использование goto оправдано и приводит к упрощению алгоритма.
Стандартные управляющие структуры делятся на две группы:
базовые и дополнительные.
3.1.1. Базовые управляющие структуры
В теории программирования доказано, что любой алгоритм
любой сложности может быть представлен как совокупность трёх
структур, которые называются базовыми. Это следование, ветвление и цикл с предусловием. Каждая из них имеет один вход и один
выход, поэтому они могут вкладываться друг в друга произвольным образом. Программа, составленная из базовых конструкций,
легко читаема, её легко отлаживать и изменять.
Управляющая структура следование предполагает последовательное выполнение заданных действий в вычислительном процессе и представляет собой алгоритмическую структуру вида:
Вход
Оператор 1
Оператор 2
Выход
Реализация этой управляющей структуры на языке Турбо Паскаль имеет вид:
11
…
оператор 1;
оператор 2;
…
Управляющая структура ветвление предполагает выбор одного из двух направлений выполнения действий в вычислительном
процессе в зависимости от выполнения или невыполнения заданного условия и представляет собой алгоритмическую структуру вида:
Вход
Да
Условие
Оператор 1
Нет
Оператор 2
Выход
Реализация этой управляющей структуры на языке Турбо Паскаль имеет вид:
If условие;
Then оператор1;
Else оператор2.
Управляющая структура цикл с предусловием предполагает
многократное выполнение некоторого действия при сохранении
начальной истинности заданного условия и представляет собой
алгоритмическую структуру вида:
Вход
Условие
Нет
Да
Оператор
Выход
Реализация этой управляющей структуры на языке Турбо Паскаль имеет вид:
12
While условие;
Do оператор.
3.1.2. Дополнительные управляющие структуры
Управляющая структура обход предполагает выполнение или
невыполнение (обход) некоторого действия в вычислительном процессе в зависимости от выполнения условия и представляет собой
алгоритмическую структуру вида:
Вход
Нет
Условие
Да
Оператор
Выход
Реализация этой управляющей структуры на языке Турбо Паскаль имеет вид:
If условие;
Then оператор.
Управляющая структура выбор варианта предполагает выбор
одного действия из некоторого непустого множества действий в
вычислительном процессе в зависимости от значения заданного ключа
выбора и представляет собой алгоритмическую структуру вида:
Вход
Ключ
выбора
K1
Оператор_1
K2
…
Оператор_2
Kn
Оператор_n
Оператор
Выход
13
Реализация этой управляющей структуры на языке Турбо Паскаль имеет вид:
Case ключ выбора Of
K1: оператор_1;
K2: оператор_2;
…
Kn: оператор_n;
Else оператор;
End.
Управляющая структура цикл с постусловием предполагает
многократное выполнение некоторого действия, после чего
проверяется сохранение значения условия, и представляет собой
алгоритмическую структуру вида:
Вход
Оператор
Условие
Выход
Реализация этой управляющей структуры на языке Турбо Паскаль имеет вид:
Repeat оператор;
Until условие.
Управляющая структура цикл с параметром предполагает
многократное выполнение некоторого действия с изменением
значения параметра цикла от начального значения до конечного с
заданным шагом изменения и представляет собой алгоритмическую
структуру вида:
Вход
P = Pн (шаг) Pк
Оператор
Выход
14
Реализация этой управляющей структуры на языке Турбо Паскаль имеет вид:
For P := Pн To Pк;
Do оператор.
Достоинства структурного программирования:
− уменьшаются затраты времени на отладку программ (до 10
раз);
− повышается надежность разработанных программ;
− обеспечивается наиболее легкая модификация программ;
− упрощается эксплуатация программ.
Недостаток структурного программирования заключается в незначительном увеличении объема программ на величину не более
чем 10%.
3.2. Сущность процедурного программирования
С увеличением объёма программ программисту невозможно
удерживать в своей памяти все нюансы задачи, и он вынужден
структурировать информацию, выделяя главное и отбрасывая несущественное. Этот процесс называется повышением степени абстракции программы.
Первым шагом на этом пути является процедурное программирование.
Оно представляет собой метод, реализующий нисходящую технологию проектирования программ. Процедурное программирование предполагает разбиение задачи на более простые подзадачи,
каждая из которых оформляется в виде подпрограммы.
Подпрограмма – это именованная последовательность описаний
и операторов, выполняющая некоторое функционально законченное действие. Результирующая программа включает последовательность вызовов подпрограмм, при выполнении которых в свою
очередь могут вызываться другие подпрограммы.
Любая подпрограмма должна быть объявлена и определена.
Объявление (опережающее описание, прототип, сигнатура) подпрограммы должно находиться в тексте раньше её вызова для того,
чтобы компилятор мог выполнить проверку правильности вызова
подпрограммы. Объявление задаёт имя подпрограммы и список
передаваемых параметров.
Определение (описание) подпрограммы содержит кроме объявления тело подпрограммы, представляющее собой последовательность описаний и операторов.
15
Подпрограмма начинает выполняться в момент её вызова. Подпрограмма описывается один раз, а вызываться она может многократно из разных точек программы в соответствии с алгоритмом.
В определении, объявлении и при вызове подпрограммы типы,
количество и порядок следования параметров в списке параметров
подпрограммы должны совпадать. На их имена ограничений по соответствию не накладывается, поскольку подпрограмму можно вызывать с различными аргументами.
Описания, содержащиеся внутри подпрограммы, являются локальными по отношению к ней. Областью их действия является
подпрограмма.
Описания, содержащиеся вне каких-либо подпрограмм, называются глобальными. Областью их действия является вся часть текста программы ниже этого описания.
Обмен данными между подпрограммой и внешней средой может
осуществляться за счёт списка параметров подпрограммы и с использованием глобальных переменных.
Организация передачи данных за счёт глобальных переменных
очень легка. Однако она не рекомендуется (а при выполнении лабораторных работ по курсу программирования категорически запрещена), поскольку затрудняет отладку программы из-за возможности
возникновения побочных эффектов и нарушает автономность подпрограмм. Любая подпрограмма должна быть максимально независима, а её интерфейс должен полностью определяться заголовком.
Список параметров подпрограммы является наиболее предпочтительным способом организации передачи данных между подпрограммой и внешней средой. В нём указываются имена входных и
выходных данных подпрограммы. Использование списка параметров исключает возникновение побочных эффектов, т. е. непредвиденных искажений данных при использовании подпрограмм.
Параметры, перечисленные в списке параметров подпрограммы, называются формальными. Соответствующие параметры, записанные в операторе вызова подпрограммы, называются фактическими.
Существует два способа передачи параметров в подпрограмму:
по значению и по адресу.
При передаче по значению при вызове подпрограммы формальные параметры принимают значения копий значений фактических
параметров. После этого связь между фактическими и формальными параметрами теряется, и операторы подпрограммы работают с
этими копиями. Доступа к исходным значениям фактических па16
раметров у подпрограммы нет и, следовательно, нет возможности
их изменить.
При передаче по адресу формальные параметры подпрограммы
принимают значения адресов фактических параметров. Операторы
подпрограммы получают доступ к данным по этим адресам и могут
менять исходные значения фактических параметров.
3.3. Сущность модульного программирования
Модульное программирование является следующим шагом в
повышении уровня абстракции программы. В этом случае подпрограммы и связанные с ними данные помещаются в отдельные файлы (модули). Модули транслируются отдельно и подключаются на
этапе компоновки исполняемой программы.
Разбиение программы на модули позволяет:
− программировать и отлаживать программу по частям (в том
числе и разными программистами);
− облегчить процесс отладки программы, скрывая несущественные детали за интерфейсом модуля;
− создавать собственные библиотеки подпрограмм и данных.
Любой модуль должен содержать данные и подпрограммы их обработки. Поэтому не рекомендуется ситуация, когда другие модули
содержат средства обработки этих данных. Если такая обработка в
других модулях необходима, то эти модули должны использовать
подпрограммы обработки данных первого модуля.
Для того чтобы пользоваться модулем, необходимо знать только
его интерфейс, а не детали его реализации. Это уменьшает объём информации, которую должен помнить программист при отладке программы. Скрытие деталей реализации называется инкапсуляцией.
Интерфейс модуля содержит описания констант, типов, переменных и полные заголовки подпрограмм, которые используются
внешней средой (основной программой и другими модулями).
Исполнительная часть модуля содержит описание всех подпрограмм модуля.
3.4. Сущность объектно ориентированного
программирования
Основной целью введения методов структурного, процедурного
и модульного программирования является упрощение структуры
программы, представление её в виде меньшего количества более
17
крупных блоков с минимальным количеством связей между ними.
Такой подход позволяет создавать и отлаживать достаточно большие по объёму программы со сложным алгоритмом. При этом разработкой программы может одновременно заниматься большой
коллектив авторов.
Выбор степени абстракции определяется сложностью решаемой
задачи. При этом бессмысленно использовать сложные технологии
для решения простых задач, но точно также бесполезно решать
сложные задачи без использования соответствующих им технологий. Используемый инструмент должен быть адекватен решаемой
задаче и модели организации знаний.
Следующим этапом развития программирования является объектно ориентированное программирование (ООП), основные принципы которого были разработаны ещё в языке Simula-67.
Основой ООП является введение понятия объекта и взаимосвязей между ними.
Объект представляет собой тип данных, определяемый пользователем. В нём программист задаёт свойства некоторого явления
(предмета или процесса) в виде полей данных и алгоритмов их обработки в виде конкретных подпрограмм, называемых методами.
Поскольку любой тип данных (стандартный или определяемый
пользователем) задаёт внутреннее представление данных этого
типа в памяти компьютера, множество значений, которые могут
принимать данные этого типа, и набор допустимых операций и способов обработки, то всё это можно задать и при описании объекта.
Детали реализации объекта скрыты от пользователя за интерфейсом, которым являются заголовки его методов.
Конкретные данные этого типа называются экземплярами объектов.
С помощью ООП реализуется так называемая «событийно управляемая модель», при которой активны данные, управляющие вызовом того или иного метода их обработки (фрагмента программного кода).
Основными свойствами ООП являются инкапсуляция, наследование и полиморфизм.
Инкапсуляция – это объединение данных и алгоритмов (подпрограмм) их обработки, при котором и данные, и подпрограммы
в значительной степени теряют своё самостоятельное значение.
В результате при написании программ исключаются ошибки, связанные с тем, что для обработки данных примененяются не предназначенные для этого подпрограммы. Инкапсуляция повышает
18
уровень абстракции программы, которые становятся легко модифицируемыми.
Наследование – это возможность объявления любого объекта
потомком ранее описанного объекта, при котором новый объект наследует все поля и методы родителя и при этом может дополнять их
новыми, специфическими для себя полями и методами. Наследуемое не требует нового описания, что значительно сокращает объём программы. Такое выделение общих черт различных объектов
в один объект-предок позволяет получить иерархию родственных
объектов. Поскольку наследование распространяется и на объекты-потомки, то полученная иерархия объектов имеет древовидную
структуру.
Механизм наследования позволяет строить библиотеку объектов по принципу «от простого к сложному». Такая технология разработки программ реализует технологию восходящего программирования.
Полиморфизм – это возможность использования в родственных
объектах различного уровня иерархии одних и тех же имён для
обозначения сходных по смыслу действий. Это позволяет при разработке объектов-потомков не только дополнять методы объектародителя, но и заменять их новыми с сохранением названия.
19
4. МЕТОДИЧЕСКИЕ УКАЗАНИЯ
К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ
Лабораторные занятия проводятся с целью приобретения практических навыков алгоритмизации, программирования, тестирования и отладки программ на компьютере с использованием современных технологий и инструментальных средств.
Перечень лабораторных работ:
– №1. Работа с файлами в интегрированной среде программирования;
– №2. Отладка и тестирование программы;
– №3. Управляющая структура «Следование»;
– №4. Поиск экстремума;
– №5. Управляющая структура «Развилка»;
– №6. Управляющая структура «Выбор варианта»;
– №7. Управляющая структура «Циклы»;
– №8. Рекуррентные вычисления;
– №9. Суммирование рядов;
– №10. Обработка одномерных массивов;
– №11. Обработка двумерных массивов;
– №12. Методы сортировки;
– №13. Текстовые файлы;
– №14. Файлы прямого доступа;
– №15. Линейные списки;
– №16. Динамические структуры данных: стек, дек, очередь;
– №17. Статические и динамические объекты.
Выполнение каждой лабораторной работы включает разработку алгоритма, написание программы, тестирование и отладку программы на компьютере в одной из компьютерных лабораторий университета, демонстрацию результатов преподавателю, составление
отчета о лабораторной работе. Содержание отчета должно полностью соответствовать заданию на эту лабораторную работу.
Лабораторная работа №1. Работа с файлами в интегрированной
среде программирования
Цель лабораторной работы: изучение приемов работы с файлами в интегрированной среде программирования, приобретение навыков практической работы в этой среде.
Задание по изучению интегрированной среды программирования: освоить основные приёмы работы с файлами в интегрированной среде программирования.
20
Порядок выполнения работы:
1. Научиться запускать интегрированную среду программирования и выходить из неё.
2. В окне редактора набрать текст, содержащий 10 строк автобиографии. Сохранить его в файле личной папки.
3. В новом окне редактора набрать текст, содержащий 5 строк
с информацией о ближайших родственниках. Сохранить его в другом файле.
4. В новом окне редактора набрать текст, содержащий 5 строк с
информацией о своих увлечениях. Сохранить его в третьем файле.
5. Включить в первый файл информацию из второго и третьего
файлов, используя команды редактора.
6. Отредактировать полученный файл.
7. Изменить размеры и расположение окон на экране. Обеспечить одновременный обзор трех файлов в полном объёме.
8. Оформить отчет о лабораторной работе в составе: краткая характеристика интегрированной среды программирования, задание
на лабораторную работу, порядок выполнения лабораторной работы, содержимое созданных файлов.
Лабораторная работа №2. Отладка и тестирование
программы
Цель лабораторной работы: изучение приемов тестирования
и отладки программ в интегрированной среде программирования,
приобретение навыков практической работы в этой среде.
Задание на программирование: изучить этапы отладки и тестирования программ в интегрированной среде программирования.
Порядок выполнения работы:
1. Набрать текст программы, содержащей базовые управляющие структуры: следование, развилка, цикл с предусловием. Сохранить его в личной папке.
2. Выполнить трансляцию программы и получить информацию
о скомпилированном файле.
3. Исправить синтаксические ошибки, выявленные при трансляции программы.
4. Подготовить набор из 8 тестов для проверки логики работы
программы с нормальными и ошибочными исходными данными.
Набор тестов представить в виде таблицы с графами: номер теста,
входные данные, выходные данные.
21
5. Запустить программу на исполнение и проверить ее работу на
каждом тесте.
6. Открыть окно наблюдения и поместить в него имена всех переменных программы.
7. Осуществить пошаговое выполнение программы, наблюдая за
значениями переменных в этом окне.
8. Оформить отчет о лабораторной работе в составе: задание на
лабораторную работу, текст программы, набор тестов.
Текст программы
Program NOD;
{Определение наибольшего общего делителя двух натуральных чисел.
Входные данные: a, b – натуральные числа.
Выходные данные: x – натуральное число.}
Var
a,b,x,y:1..255; {описание переменных типа диапазон}
Begin
{$R+} {установка режима контроля диапазона значений}
Write(‘Введите два натуральных числа: ‘); {вывод запроса на экран}
ReadLn(a,b); {ввод данных с клавиатуры через пробел}
x:=a; {начальные установки}
y:=b;
While x<>y {Цикл Пока x не равно y}
Do If x>y {повторять, если x больше y}
Then x:=x-y
{то замена x}
Else y:=y-x;
{иначе замена y}
WriteLn(‘НОД(‘,a,’,’,b,’)=’,x); {вывод результата на экран}
End.
Лабораторная работа №3. Управляющая структура
«Следование»
Цель лабораторной работы: изучение концепций и освоение
технологии структурного программирования, приобретение навыков структурного программирования на языке Турбо Паскаль
при решении простейших вычислительных задач.
Задание на программирование: используя технологию структурного программирования, разработать линейную программу
решения индивидуальной вычислительной задачи.
Порядок выполнения работы:
22
1. Получить у преподавателя индивидуальное задание и выполнить постановку задачи: сформулировать условие, определить
входные и выходные данные.
2. Разработать математическую модель вычислений.
3. Выполнить все необходимые вычисления вручную и принять
полученные результаты в качестве контрольных значений.
4. Построить схему алгоритма решения задачи.
5. Составить программу на языке Турбо Паскаль.
6. В программе использовать исходные данные типа shortint, а
тип результата – byte.
7. Выходные данные (сообщения) выводить на экран в развернутой форме.
8. Проверить и продемонстрировать преподавателю работу программы.
9. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, текст
программы.
Варианты индивидуальных заданий
Выполнить поразрядные логические операции над машинными
кодами.
1.
117 AND 90
–117 XOR 90
117 → 3
NOT 21 XOR –13 AND (–23 OR NOT 9)
2.
115 AND 106
115 OR –106
115 → 4
NOT 17 OR (NOT 111 XOR –19) AND 91
3.
107 AND 37
107 XOR –37
25 ← 2
–21 AND (NOT 75 OR –20) XOR NOT 59
4.
27 AND 13
–27 OR 13
27 ← 2
23
NOT 21 XOR –3 AND (NOT 26 OR –13)
5.
–21 OR 43
21 XOR 43
43 ← 1
(NOT 19 OR –6) AND NOT –9 XOR 4
6.
55 AND 15
55 XOR –15
15 ← 3
NOT 7 AND –5 XOR (NOT 127 OR –8)
7.
99 OR –17
99 AND 17
17 ← 2
(18 OR NOT –8) AND NOT –7 XOR 3
8.
29 OR –49
29 XOR 49
49 ← 2
(NOT 8 XOR –6) AND 9 XOR NOT –12
9.
42 AND 17
42 OR –17
42 → 3
NOT 25 XOR –4 AND (NOT 22 OR –10)
10.
36 AND 12
36 XOR 12
36 ← 2
NOT –3 XOR 15 AND (NOT 8 OR –6)
11.
25 AND 18
25 XOR 18
25 ← 2
NOT 23 OR –4 AND (NOT 24 OR –9)
12.
39 AND 14
39 OR –14
39 ← 1
NOT 17 AND –5 OR (25 AND NOT –9)
24
13.
49 AND 11
49 XOR 11
49 → 2
15 OR NOT –3 AND (14 OR NOT 16)
14.
108 AND 35
108 XOR 35
31 ← 2
NOT –7 OR 8 AND (26 XOR NOT –9)
15.
120 AND 37
120 OR –37
120 → 2
85 OR NOT –9 AND (NOT 46 OR –13)
16.
117 AND 80
117 XOR 80
117 → 3
105 XOR NOT –15 AND (NOT 82 OR –25)
17.
125 AND 14
125 XOR 14
100 → 4
110 OR NOT –25 AND (NOT 46 XOR –11)
18.
119 AND 18
119 OR –18
119 → 3
80 OR NOT –11 AND (NOT 48 XOR –15)
19.
125 AND 20
125 OR –20
50 ← 2
40 OR NOT –19 AND (NOT 50 XOR –7)
20.
94 AND 15
94 XOR 15
94 → 2
86 XOR NOT –17 AND (NOT 40 OR –9)
25
21.
102 AND 31
102 OR –31
102 → 3
35 XOR NOT –9 AND (NOT 28 OR –17)
22.
90 AND 11
90 OR –11
20 ← 2
17 XOR NOT –11 AND (NOT 30 OR –15)
23.
74 AND 111
74 XOR 111
54 ← 1
28 OR NOT –13 AND (NOT 16 XOR –25)
24.
36 AND 21
36 XOR 21
26 ← 2
14 OR NOT –15 AND (NOT 26 XOR –17)
25.
61 AND 18
61 OR –18
61 ← 1
9 XOR NOT –21 AND (NOT 60 OR –5)
26.
75 AND 26
75 XOR 26
22 ← 2
NOT 80 XOR –31 AND (–16 OR NOT 11)
27.
81 AND 14
81 XOR 14
81 ← 3
70 XOR NOT –11 AND (NOT 36 OR 15)
28.
111 AND 14
111 XOR 14
11 ← 3
15 XOR NOT –9 AND (NOT 26 OR 31)
26
Пример программы
Program Log_Oper;
{Выполнение поразрядных логических операций над целыми числами}
Uses crt;
Var
a,b,c,d:Shortint;
e:Byte;
Begin
clrscr;
a := 111;
b := -111;
c := 12;
d := -12;
e := a AND d;
WriteLn(‘111 AND -12 =’,e,’ (контр. значение 100)’);
e := b AND d;
WriteLn(‘-111 AND -12 =’,e,’ (контр. значение 144)’);
e := a OR c;
WriteLn(‘111 OR 12 =’,e,’ (контр. значение 111)’);
e := a XOR c;
WriteLn(‘111 XOR 12 =’,e,’ (контр. значение 99)’);
e := a shr 2;
WriteLn(‘111 >> 2 =’,e,’ (контр. значение 27)’);
e := c shl 3;
WriteLn(‘12 << 3 =’,e,’ (контр. значение 96)’);
e := b AND (NOT c OR a) OR d;
WriteLn(‘-111 AND(NOT12 OR 111)OR -12 =’,e,’ (контр. знач. 245)’);
ReadLn;
End.
Лабораторная работа №4. Поиск экстремума
Цель лабораторной работы: изучение концепций и освоение
технологии структурного программирования, приобретение навыков структурного программирования на языке Турбо Паскаль
при решении логических задач.
Задание на программирование: используя технологию структурного программирования, разработать разветвляющуюся программу для решения индивидуальной задачи поиска экстремума.
Порядок выполнения работы:
27
1. Получить у преподавателя индивидуальное задание и выполнить постановку задачи: сформулировать условие, определить
входные и выходные данные.
2. Разработать математическую модель вычислений.
3. Построить схему алгоритма решения задачи двумя способами:
− с использованием управляющей структуры «Выбор»;
− с использованием управляющей структуры «Обход».
4. Составить программу на языке Турбо Паскаль.
5. Входные данные целого типа Integer вводить с клавиатуры по
запросу.
Выходные данные (сообщения) выводить на экран в развернутой
форме.
6. Подготовить набор тестов для проверки логики работы программы с различными исходными данными. Набор тестов представить в виде таблицы с графами: номер теста, входные данные,
выходные данные.
7. Запустить программу на исполнение и проверить её работу на
каждом тесте.
8. Продемонстрировать преподавателю работу программы.
9. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, текст
программы, контрольные примеры.
Варианты индивидуальных заданий
1. x = min(a, max(b, c))
2. x = max(min(a, b), c)
3. x = min(max(a, c), b)
4. x = max(c, min(a, b))
5. x = min(max(b, c), a)
6. x = max(a, min(b, c))
7. x = min(max(a, b), c)
8. x = max(b, min(a, c))
9. x = max(min(b, c), a)
10. x = min(b, max(a, c))
11. x = max(min(a, c), b)
12. x = min(c, max(a, b))
13. x = min(a, max(b, c))
14. x = max(min(a, b), c)
15. x = min(max(a, c), b)
16. x = max(c, min(a, b))
28
17. x = min(max(b, c), a)
18. x = max(a, min(b, c))
19. x = min(max(a, b), c)
20. x = max(b, min(a, c))
21. x = max(min(b, c), a)
22. x = min(b, max(a, c))
23. x = max(max(a, b) + min(b, c), b+c)
24. x = min(min(a, c) + max(a, b), a+c)
25. x = max(min(b, c) + min(a, b), a)
Пример схемы алгоритма и текста программы
определения экстремума для варианта задания вида:
x = max(min(a, b), max(c, d))
Начало
Ввод
a, b, c, d
да
a<b
min = a
да
min = a
нет
да
min = b
c>d
нет
min > b
нет
min = b
max = c
нет
max < d
max = c
да
max = d
да
max = d
min > max
нет
x = min
x = min
x = max
нет
x < max
Вывод
x
да
x = max
Вывод
x
Конец
29
Пример программы
Program Extremum;
{Определение максимального или минимального значения
с использованием структур «выбор» и «обход».
Вычислить x = max(min(a,b), max(c,d))}
Var
a,b,c,d:Integer;
{исходные данные}
max,min:Integer;
{промежуточные значения}
x:Integer;
{результат вычисления}
Begin
{Ввод исходных данных}
WriteLn(‘Введите значения a,b,c,d: ‘);
ReadLn(a,b,c,d);
{Решение задачи с использованием структуры “Выбор”}
If a<b
{Определяем наименьшее значение между a и b}
Then min:=a
Else min:=b;
If c>d
{Определяем наибольшее значение между c и d}
Then max:=c
Else max:=d;
If min>max {Определяем наибольшее значение между max и min}
Then x:=min
Else x:=max;
{Вывод результата решения с использованием структуры “Выбор”}
WriteLn(‘Использование структуры “Выбор”: x = ‘,x);
{Решение задачи с использованием структуры “Обход”}
min:=a;
{Определяем наименьшее значение между a и b}
If min>b
Then min:=b;
max:=c;
{Определяем наибольшее значение между c и d}
If max<d
Then max:=d;
x:=min;
{Определяем наибольшее значение между max и
min}
If x<max
Then x:=max;
{Вывод результата решения с использованием структуры “Обход”}
WriteLn(‘Использование структуры “Обход”: x = ‘,x);
ReadLn;
End.
30
Лабораторная работа №5. Управляющая структура
«Развилка»
Цель лабораторной работы: изучение концепций и освоение технологии структурного программирования, приобретение навыков
структурного программирования при решении логических задач.
Задание на программирование: используя технологию структурного программирования, разработать разветвляющуюся программу для решения индивидуальной задачи определения места
нахождения на плоскости точки с произвольно заданными координатами.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание и выполнить постановку задачи: сформулировать условие, определить
входные и выходные данные.
2. Разработать математическую модель – условия принадлежности точки выделенным областям.
3. Построить схему алгоритма решения задачи.
4. Составить программу на языке Турбо Паскаль.
5. Входные данные вещественного типа real вводить с клавиатуры по запросу. Выходные данные (сообщения) выводить на экран в
развернутой форме.
6. Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов.
7. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, текст
программы, контрольные примеры.
Варианты индивидуальных заданий
2 Y
2.
2 Y
1.
M1
1
–2
M1
1
M2
M3
–1
M2
1
2 –2
–1
1
X
M4
M3
–1
–2
M5
M4
2
X
–1
M5
–2
31
2 Y
3.
1
–2
M3
M1
M1
M2
–1
2 Y
4.
1
2 –2
X
M4
1
–1
1
M2
–1
–1
M5
M5
–2
–2
2 Y
5.
M3
2
X
M4
6.
2
Y
M1
M1
–2
1
M2
1
–1
1
M2
M4
M3
2 –2
X
–1
M3
1
2
X
M4
–1
–1
M5
M5
–2
7.
–2
2 Y
8.
2
Y
M1
M1
1
–2 M2 –1
M4
1 M3 2 –2
X
–1
M2
1
M3
1
M5
M4
–1
–1
M5
–2
32
–2
2
X
9.
2
Y
2 Y
M1
10.
M1
M2
1
1
M3
–2
–1
1
M4
–1
1 M4 2
X
M2
–1
M5
M5
–2
–2
2 Y
11.
M3
2 –2 M2 –1
X
12.
2
Y
M1
1
M2
–2
–1
M1
1
M2
1
M3
2 –2
X
1 M3 2
X
–1
M5
M4
–1
M4
–1
M5
–2
–2
2 Y
13.
M1
–2
M2
1
–1
M3
14.
1
2
2 –2 M3 –1
X
M2
1
M4
2
X
–1
M5
–2
M1
1
M4
–1
Y
M5
–2
33
2 Y
15.
2 Y
16.
M1
M2
1
–2
1
M1
M3
–1
1
2 –2
X
M2
–1
1
M3 2
X
1
2
X
M5
–1
M4
M4
–2
M5
–2
2 Y
17.
–1
18.
2
Y
M1
–2
–1
M2
1
M1
M3
1
1
2 –2 M2 –1
X
M3
M4
M5
–1
M4
–1
M5
–2
–2
2 Y
19.
20.
2
Y
M1
M1
1
1
M2
M2
–2
–1
1
M3
M5
M4
–1
–2
34
2 –2
X
–1
1
M5
M4
–1
–2
M3 2
X
2 Y
21.
22.
2
Y
M2
M1
–2
M1
1
M3
–1
1
2 –2
X
1
M2
–1
1
2
X
M3
M4
–1
–1
M5
M4
–2
–2
2 Y
23.
M2
–1
2 Y
24.
M1
M1
1
–2
M5
1
2 –2
X
M3
1
M2
–1
1
2
M4 X
M3
M4
–1
–1
M5
M5
–2
–2
2 Y
25.
2 Y
26.
M1
M1
1
M2
1
M2
–2
–1
1
M3
2 –2
X
–1
1
M3
2
X
M4
–1
M5
–2
–1
M4
M5
–2
35
2 Y
27.
2 Y
28.
M1
M2
M1
1
1
M2
–2
1 M3 2 –2
X
–1
M4
M4
M5
1 M3 2
X
–1
–1
–1
M5
–2
–2
2 Y
29.
2 Y
30.
M1
M1
1
M2
–2
1
2 –2
–1
X
M4
1
M4
M5
M3
M2
M3
–1
1
2
X
M5
–1
–1
–2
–2
Пример схемы алгоритма и текст программы определения
местоположения точки для варианта задания вида:
Y
M1
–2
–1
M2
1
M3
1
M4
M5
–1
–2
36
2
X
Схема алгоритма решения
Начало
Ввод
x, y
да
x=0 и y=0
Вывод
(.) в НК
да
Вывод
(.) в М1
нет
усл. 1
да
Вывод
(.) в М2
нет
усл. 2
да
Вывод
(.) в М3
нет
усл. 3
да
Вывод
(.) в М4
нет
усл. 4
да
Вывод
(.) в М5
нет
усл. 5
нет
Вывод
вне зон
Конец
Математическая модель
(условия принадлежности точек выделенным областям)
− Условие 1 (принадлежность области М1):
(x+1)2 + (y–1)2 < 1
{внутри верхней окружности},
x < –1
{левее линии x = –1},
y > 1
{выше линии y = 1};
− условие 2 (принадлежность области М2):
x > 1
{правее линии x = 1},
37
x < 2
{левее линии x = 2},
y < 2
{ниже линии y = 2},
y > x – 1
{выше линии y = x – 1};
− условие 3 (принадлежность области М3):
x2 + y2 < 1
{внутри центральной окружности},
(x+1)2 + (y–1)2 < 1
{внутри верхней окружности};
− условие 4 (принадлежность области М4):
x > –2
{правее линии x = –2},
y < 0
{ниже оси x},
y > x + 1
{выше линии y = x + 1};
− условие 5 (принадлежность области М5):
(x–1)2 + (y+1)2 < 1
{внутри нижней окружности},
x2 + y2 > 1
{вне центральной окружности}.
Текст программы
Program Tochka;
{Определение местоположения точки на плоскости.
Входные данные: x, y – координаты точки
Выходные данные: s – сообщение}
Var x, y: Real;
s: String;
Begin
{Ввод исходных данных}
Write(‘Введите координаты точки x и y: ‘);
ReadLn(x, y);
{Анализ координат}
If (x = 0) And (y = 0)
Then s:= ‘ в начале координат’
Else If(((x+1)*(x+1)+(y-1)*(y-1))<1)AND(x<-1)AND(y>1)
Then s:= ‘ в области М1’
Else If(x>1)AND(x<2)AND(y<2)AND(y>x-1)
Then s:= ‘ в области М2’
Else If(x*x+y*y<1)AND(((x+1)*(x+1)+(y-1)*(y-1))<1)
Then s:= ‘ в области М3’
Else If(x>-2)AND(y<0)AND(y>x+1)
Then s:= ‘ в области М4’
Else If(((x-1)*(x-1)+(y+1)*(y+1))<1)AND(x*x+y*y>1)
38
{Область М1?}
{Область М2?}
{Область М3?}
{Область М4?}
{Область М5?}
Then s:= ‘ в области М5’
Else s:= ‘ вне всех обозначенных областей’;
{Вывод сообщения}
WriteLn(‘Положение точки:’, s);
ReadLn;
End.
Лабораторная работа №6. Управляющая структура
«Выбор варианта»
Цель лабораторной работы: изучение концепций и освоение
технологии структурного программирования, приобретение навыков структурного программирования на языке Турбо Паскаль
многовариантных вычислений.
Задание на программирование: используя технологию структурного программирования, разработать разветвляющуюся программу для решения индивидуальной задачи выбора варианта вычисления по ключу.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание и выполнить постановку задачи: сформулировать условие, определить
входные и выходные данные.
2. Разработать математическую модель:
− составить список различных вариантов получения выходных
данных задачи;
− выявить ключ выбора – данное целого типа, значения которого могут служить ключами различных вариантов выполнения действий;
− с помощью формул описать варианты получения выходных
данных задачи в зависимости от значения ключа выбора варианта.
3. Построить схему алгоритма решения задачи.
4. Составить программу на языке Турбо Паскаль.
5. Входные данные вводить с клавиатуры по запросу.
6. Выходные данные выводить на экран в развернутой форме с
пояснениями.
7. Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов, в том числе с ошибочными входными данными.
8. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, текст
программы, контрольные примеры.
39
Варианты индивидуальных заданий
1. Определить название месяца года, следующего за заданным
месяцем.
2. Определить название k-го месяца после заданного месяца года.
3. Определить название столицы по заданному названию страны.
4. Определить название десятичной цифры по заданному ее значению.
5. Написать заданную десятичную цифру римскими цифрами.
6. Определить двоичный код заданной десятичной цифры.
7. Определить сезон года (зима, весна, лето, осень), на который
приходится заданный месяц.
8. Определить название континента (Азия, Америка, Африка,
Европа) по заданному названию страны.
9. Определить название цвета радуги, следующего за заданным
цветом.
10. Определить название интервала (секунда, терция, кварта,
квинта, секста, септима), образованного двумя заданными нотами
(до, ре, ми, фа, соль, ля, си).
11. Определить величину в метрах некоторой длины, заданной в
одной из указанных единиц измерения (километр, метр, дециметр,
сантиметр, миллиметр).
12. Для целого числа k от 1 до 130 вывести фразу «Мне k лет»,
учитывая при этом, что при некоторых значениях k слово «лет»
надо заменить словом «год» или «года».
13. Для натурального числа k вывести фразу «Мы нашли k грибов в лесу», согласовав слово «гриб» с числом k.
14. Для целого числа d от 1 до 9999, обозначающего денежную
единицу, дописать слово «рубль» в правильной форме.
15. Для целого числа d от 1 до 9999, обозначающего денежную
единицу, дописать слово «копейка» в правильной форме.
16. Вычислить стоимость междугородного телефонного разговора заданной продолжительности. Цена одной минуты определяется
по указанному коду города.
17. Вывести указанное слово из группы однотипно склоняемых
слов (степь, боль, тетрадь, дверь) в заданном падеже (им., род.,
дат., вин., твор., предл.).
18. Корабль сначала шел по заданному курсу (север, восток, юг,
запад). Затем его курс был изменен согласно заданному приказу
(вперед, вправо, назад, влево). Определить новый курс корабля.
40
19. Определить количество дней в указанном месяце заданного
года.
20. Определить, образует ли заданная тройка чисел y (год), m
(месяц), d (день) правильную дату.
21. По заданной дате d (день), m (месяц), y(год) определить дату
d1, m1, y1 следующего дня.
22. Определить порядковый номер того дня високосного года,
который имеет заданную дату d (день), m (месяц).
23. Определить d (день), m (месяц) – дату k-го по счету дня високосного года.
24. Считая, что год не високосный и 1 января приходится на
день недели wd1, определить wd – день недели, на который приходится день с датой d (день), m (месяц).
25. Считая, что год не високосный и 1 января приходится на
день недели wd1, определить количество пятниц в году, приходящихся на 13-е числа месяца.
Пример программы
Program PloFig;
{Вычисление площадей геометрических фигур.
Входные данные: t – тип фигуры,
a,l,h,r – параметры фигур.
Выходные данные: s – площадь фигуры.}
Var
t:Byte;
a,l,h,r,s:Real;
Begin {Ввод и контроль}
WriteLn(‘Задайте тип фигуры:’);
Write(‘1-квадрат,2-прямоугольник,3-круг? ->’);
ReadLn(t);
If (t<1)or(t>3)
Then Begin
WriteLn(‘Ошибочный тип фигуры!’);
Write(‘Нажмите Enter ->’);
ReadLn; Halt;
End;
{Вычисление площади}
Case t Of
1: Begin
Write(‘Размер стороны квадрата? ->’);
41
ReadLn(a);
s:=a*a;
End;
2: Begin
Write(‘Размеры сторон прямоугольника? ->’);
ReadLn(l,h);
s:=l*h;
End;
3: Begin
Write(‘Величина радиуса круга? ->’);
ReadLn(r);
s:=Pi*r*r;
End;
End;
WriteLn(‘Площадь фигуры: ‘,s:7:2);
End.
Лабораторная работа №7. Управляющая структура «Циклы»
Цель лабораторной работы: изучение концепций и освоение
технологии структурного программирования, приобретение навыков структурного программирования на языке Турбо Паскаль
циклических вычислений.
Задание на программирование: используя технологию структурного программирования, разработать программу решения индивидуальной задачи, содержащую 3 вида циклических управляющих
структур: Цикл – Пока (с предусловием), Цикл – До (с постусловием), Цикл – Для (с параметром). Реализовать интерфейс, обеспечивающий заданное расположение и назначение окон на экране при выполнении программы в соответствии с индивидуальным заданием.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание: а) схему
расположения и назначения окон на экране; б) индивидуальную
задачу. Выполнить постановку задачи: сформулировать условие,
определить входные и выходные данные.
2. Разработать математическую модель.
3. Построить схему алгоритма, последовательно используя для
решения задачи все три циклические управляющие структуры
(операторы while, repeat…until, for).
4. Составить программу на языке Турбо Паскаль.
5. Входные данные вводить с клавиатуры по запросу.
42
6. Выходные данные выводить на экран в развернутой форме с
пояснениями.
7. Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов, в том числе с ошибочными входными данными.
8. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, текст
программы, контрольные примеры.
Варианты индивидуальных заданий
1. Для введенных с клавиатуры значений X и m вычислить S:
2m+1
S=
å
iX-2 .
i=1,3,5,...
2. Для введенных с клавиатуры значений X и m вычислить P:
mæ
ö÷
X
P = Õ ççm +
÷.
çè
m - i + 1÷ø
i=1
3. Для введенных с клавиатуры значений A, B, n, m и X вычислить S:
2
n æ
Bö
S = A + å çç X + ÷÷÷ .
çè
iø
i=m
4. Для введенных с клавиатуры значений A, B, n и X вычислить S:
S= A+B
n
X - ABi
.
X
+ ABi
i=2,4,6,...
å
5. Для введенных с клавиатуры значений A, B, n, m и X вычислить S:
n
A + Xi
S = A + B å (-1)i
.
B
+ Xi
i=m
6. Для введенного с клавиатуры значения m вычислить S:
x2 - 3x + 2
; при x = 1.5 + i.
2x2 -1
i=1
m
S=å
7. Для введенного с клавиатуры значения m вычислить S:
43
m
æ x2 + 1 ö÷
ç
S = å lg çç
÷÷; при x = –1 + i.
ç (i -1)! ÷÷ø
i=1 è
8. Для введенного с клавиатуры значения X вычислить S:
S=
(X - 2)(X - 4)(X - 8)...(X -128)
.
(X -1)(X - 3)(X - 7)...(X -127)
9. Найти сумму всех целых чисел из отрезка [A,B], которые
кратны 5.
10. Найти сумму всех целых чисел из отрезка [A,B], которые
кратны 7.
11. Для введённого с клавиатуры значения N найти (2*N)!! по
формуле
(2*N)!! = 2*4*6*…*(2*N–2)*(2*N).
12. Для введённого с клавиатуры значения N найти (2*N+1)!! по
формуле
(2*N+1)!! = 1*3*5*…*(2*N–1)*(2*N+1).
13. Найти сумму всех целых чисел из отрезка [A,B], которые при
делении на 5 дают остаток 3.
14. Найти сумму всех целых чисел из отрезка [A,B], которые при
делении на 7 дают остаток 4.
¥
1
15. Найти сумму бесконечного ряда  å
с точ2
n=1 n * (sin(n) + 1.1)
ностью ε.
16. Для введённого с клавиатуры значения А найти сумму бес¥
1
конечного ряда å
с точностью ε.
*
(
n
n
+ A)
n=1
¥
1
17. Найти сумму бесконечного ряда  å
с
(
5
*
1
)
*
(5 * n + 1)
n
n=1
точностью ε.
¥
18. Найти сумму бесконечного ряда  å (-1)n
n
с точно2 * n2 -1
стью ε.
π

¥ cos( + 30 )
n
19. Найти сумму бесконечного ряда  å
с точноn
стью ε.
n=1
20. Найти предел последовательности
n=1
lim
n®¥ 3 *
44
5* n
2
(n + 1) + 2 * (n2 -1)
с точностью ε.
n3 + 5
21. Найти предел последовательности  lim
с точn®¥ 2 * n3 + n2 + 1
ностью ε.
22. Для введенного с клавиатуры значения m вычислить сумму
S значений функции Y=f(x):
m
æ x2 + 1 ö÷
ç
÷÷; при x = –1 + i.
S = å lg çç
÷÷
ç
i
(
1
)!
ø
i=1 è
Расположение окон
1.
2.
Формулировка задания
Формулировка задания
Ввод
Сообщение
об ошибке
Ввод
Вывод
Сообщение
об ошибке
Вывод
3.
4.
Формулировка задания
Формулировка задания
Ввод
Ввод
Вывод
Сообщение
об ошибке
Сообщение
об ошибке
Вывод
5.
6.
Формулировка задания
Ввод
Сообщение
об ошибке
Формулировка задания
Вывод
Ввод
Вывод
Сообщение
об ошибке
45
7.
8.
Формулировка задания
Ввод
Формулировка задания
Сообщение
об ошибке
Сообщение
об ошибке
Вывод
Ввод
Вывод
9.
10.
Формулировка задания
Формулировка задания
Ввод
Сообщение
об ошибке
Ввод
Вывод
11.
Вывод
12.
Формулировка задания
Формулировка задания
Ввод
Ввод
Вывод
Сообщение
об ошибке
Вывод
Сообщение
об ошибке
13.
14.
Формулировка задания
Формулировка задания
Ввод
Вывод
Ввод
Сообщение
об ошибке
Сообщение
об ошибке
46
Сообщение
об ошибке
Вывод
15.
16.
Формулировка
задания
Вывод
Формулировка
задания
Ввод
Вывод
Ввод
Сообщение
об ошибке
Сообщение
об ошибке
17.
18.
Формулировка
задания
Вывод
Ввод
Сообщение
об ошибке
Формулировка
задания
Ввод
Вывод
Сообщение
об ошибке
19.
20.
Формулировка
задания
Вывод
Формулировка
задания
Ввод
Ввод
Вывод
Сообщение
об ошибке
Сообщение
об ошибке
21.
22.
Ввод
Формулировка
задания
Ввод
Вывод
Формулировка
задания
Вывод
Сообщение
об ошибке
Сообщение
об ошибке
47
23.
24.
Ввод
Вывод
Ввод
Сообщение
об ошибке
Сообщение
об ошибке
Формулировка
задания
Вывод
Формулировка
задания
Ввод
Вывод
25.
26.
Ввод
Вывод
Сообщение
об ошибке
Формулировка
задания
Формулировка задания
Сообщение
об ошибке
27.
28.
Ввод
Вывод
Ввод
Сообщение
об ошибке
Вывод
Сообщение
об ошибке
Формулировка задания
Формулировка задания
29.
30.
Ввод
Вывод
Сообщение
об ошибке
Ввод
Сообщение
об ошибке
Формулировка задания
Формулировка задания
48
Вывод
Пример программы
Формулировка задания:
Последовательность {an} задана равенствами: a1 = 0.5; an = n *
(an–1 + 0.5). Вычислить предел произведения (1 + 1 / a1)*(1 + 1 /
a2)*…*(1 + 1 / an)…
Вычисления закончить при (1 / an) < eps.
Ввод исходных данных и вывод результатов вычислений должен осуществляться в разных пользовательских окнах.
Program Cikly;
{Вычисление предела произведения с заданной точностью.
Входные данные: a1 – начальное значение,
eps – точность вычисления.
Выходное данное: pr – предел произведения
}
USES Crt;
{подключение модуля}
{Процедура вывода пользовательского окна на экран}
PROCEDURE Okno(xv,yv,xn,yn,colfona,colbukv:BYTE;zag:STRING);
VAR
i:INTEGER;
BEGIN
Window(xv,yv,xn,yn);
{Установка размеров окна}
TextColor(colbukv);
{Установка цвета шрифта}
TextBackGround(colfona); {Установка цвета фона}
ClrScr; {переводит курсор в левый верхний угол окна и
очищает окно, заливая его цветом установленного фона}
GoToXY((xn-xv) DIV 2 – Length(zag) DIV 2,1);
Write(zag);
Window(xv+1,yv+1,xn-1,yn);
END;
Var
a1,eps,pr:Real;
n:Integer;
{порядковый номер сомножителя}
txt:string;
{заголовок диалогового окна}
Begin
TextBackGround(BLACK);
TextColor(15);
clrscr;
{Окно формулировки задания. Белый текст на синем фоне.}
49
Okno(8,15,72,20,BLUE,15,’Формулировка задания’);
WriteLn(‘Вычисление предела произведения (1+1/a(1))*.*(1+1/a(n))*’);
WriteLn(‘с заданной точностью 0 <eps<= 0.1’);
WriteLn(‘Значение a(1)=0.5; a(n)=n*(a(n-1)+0.5)’);
WriteLn(‘Вычисления закончить при (1/a(n))<eps’);
{Окно ввода. Белый текст на зеленом фоне.}
Okno(9,2,71,5,2,15,’Ввод’);
Write(‘Задайте значение точности вычисления 0<eps<=0.1 -> ‘);
ReadLn(eps);
If (eps<=0) Or (eps>0.1)
Then Begin
{Окно вывода сообщения об ошибке. Красный текст на зеленом фоне.}
Okno(9,7,71,8,GREEN,RED,’Сообщение об ошибке’);
Write(‘Ошибка: точность <=0 или >0.1 ! Нажмите Enter’);
ReadLn;
Exit;
End;
{Окно вывода результата. Белый текст на красном фоне.}
Okno(8,7,72,12,4,15,’Вывод’);
{Решение с использованием управляющей структуры While-Do}
a1:=0.5;
n:=1;
pr:=1;
While Abs(1/a1)>eps
Do Begin
pr:=pr*(1+1/a1);
n:=n+1;
a1:=n*(a1+0.5);
End;
WriteLn(‘ While: предел = ‘,pr:7:4,’; число сомножителей = ‘,n);
{Решение с использованием управляющей структуры Repeat-Until}
a1:=0.5;
n:=1;
pr:=1;
Repeat
pr:=pr*(1+1/a1);
n:=n+1;
a1:=n*(a1+0.5);
Until Abs(1/a1)<eps;
WriteLn(‘ Repeat: предел = ‘,pr:7:4,’; число сомножителей = ‘,n);
50
{Решение с использованием управляющей структуры For-To-Do}
a1:=0.5;
pr:=1;
For n:=2 To MAXINT
{наибольшее значение типа Integer = 32767}
Do Begin
pr:=pr*(1+1/a1);
a1:=n*(a1+0.5);
If Abs(1/a1)<eps
Then break;
{досрочное завершение цикла}
End;
WriteLn(‘ For:
предел = ‘,pr:7:4,’; число сомножителей = ‘,n);
ReadLn;
End.
Лабораторная работа №8. Рекуррентные вычисления
Цель лабораторной работы: изучение концепций и освоение
технологии структурного программирования, приобретение навыков структурного программирования на языке Турбо Паскаль
рекуррентных вычислений.
Задание на программирование: используя технологию структурного программирования, разработать программу решения индивидуальной задачи, содержащей 3 вида циклических управляющих структур: Цикл – Пока (с предусловием), Цикл – До (с постусловием), Цикл – Для (с параметром). Реализовать интерфейс,
обеспечивающий заданное расположение и назначение окон на
экране при выполнении программы в соответствии с индивидуальным заданием (вид интерфейса сохраняется из задания на
предыдущую лабораторную работу).
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание. Выполнить постановку задачи: сформулировать условие, определить
входные и выходные данные.
2. Разработать математическую модель.
3. Построить схему алгоритма, последовательно используя для
решения задачи все три циклические управляющие структуры
(операторы while, repeat…until, for).
4. Составить программу на языке Турбо Паскаль.
5. Входные данные вводить с клавиатуры по запросу.
6. Выходные данные выводить на экран в развернутой форме с
пояснениями.
51
7. Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов, в том числе с ошибочными входными данными.
8. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, текст
программы, контрольные примеры.
Варианты индивидуальных заданий
m
1. Для заданного значения m вычислить Sm = å Yi .
i=0
Значения m, Y0, Y1, Y2 вводятся с клавиатуры, а Yi вычисляется
по формуле
Yi = lg Yi2-2 + Yi-3 + 1 ; i = 3, 4, 5, …, m.
2. Для заданного значения m вычислить Ym.
Значения m, Y0, Y1,Y2 вводятся с клавиатуры, а Yi вычисляется
по формуле
Yi – tg2(Yi–3) + Yi–2; i = 3,4,5, …, m.
m
3. Для заданного значения m вычислить Sm = å ln( Yi + 0.5).
i=0
Значения m, Y0, Y1, Y2 вводятся с клавиатуры, а Yi вычисляется
по формуле
Yi = Yi-1 + Yi2-2 - 2* Yi-3 ; i = 3, 4, 5, …, m.
4. Для заданного значения m вычислить Ym.
Значения m, Y0, Y1 вводятся с клавиатуры, а Yi вычисляется по
формуле
2 * Yi-1 + Yi-2
Yi =
; i = 3, 4, 5, …, m.
3
5. Для заданного значения m вычислить Ym.
Значения m, Y0,Y1,Y2 вводятся с клавиатуры, а Yi вычисляется
по формуле
Yi= sin2(Yi–1) + cos2(Yi–3); i = 3, 4, 5, …, m.
m
6. Для заданного значения m вычислить Sm = å Yi .
i=0
52
Значения m, Y0, Y1, Y2 вводятся с клавиатуры, а Yi вычисляется
по формуле
Yi = sin(Yi–1) – cos(Yi–3); i = 3, 4, 5, …, m.
m
7. Для заданного значения m вычислить Sm = å Yi .
i=0
Значения m, Y0,Y1 вводятся с клавиатуры, а Yi вычисляется по
формуле
Yi =
sin(Yi-1 ) + cos(Yi-2 ) ; i = 2, 3, 4, …, m.
8. Вычислить предел последовательности {Yn} при n → ¥, где Yn
вычисляется по формуле
Yn = 0.25sin(Yn–1) + sin(Yn–2); n = 2, 3, 4,…
Значения Y0, Y1 вводятся с клавиатуры. Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
9. Вычислить предел последовательности {Yn} при n → ∞, где Yn
вычисляется по формуле
Yn = 0.2 + 0,1sin(Yn–1); n = 1, 2, 3,...
Значение Y0 вводится с клавиатуры. Вычисления прекратить
при выполнении условия |Yn – Yn–1| < e.
10. Вычислить предел последовательности {Yn} при n → ¥, где
Yn вычисляется по формуле
Yn=0.1tg(Yn–1) + 0.3tg(Yn–3); n = 3, 4, 5,...
Значения Y0, Y1, Y2 вводятся с клавиатуры. Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
11. Вычислить предел последовательности {Yn} при n → ¥, где
Y0=0, а Yn вычисляется по формуле
Yn =
1
; n = 1, 2, 3,…
1 + Yn-1
Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
12. Вычислить предел последовательности {Yn} при n → ¥, где
Yn вычисляется по формуле
Yn = 0.352 * Yn–1 + cos(π/2 + Yn–2); n = 2, 3, 4,…
Значения Y0, Y1 вводятся с клавиатуры. Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
53
13. Вычислить предел последовательности {Yn} при n → ¥, где
Yn вычисляется по формуле
1
; n = 2, 3, 4,…
Yn =
2
12 + Yn-1 + Yn2-2
Значения Y0, Y1 вводятся с клавиатуры. Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
14. Вычислить предел последовательности {Yn} при n → ¥, где
Yn вычисляется по формуле
1
; n = 3, 4, 5,…
Yn =
2
10 + Yn-2 + Yn2-3
Значения Y0, Y1, Y2 вводятся с клавиатуры. Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
15. Вычислить предел последовательности {Yn} при n → ¥, где
Yn вычисляется по формуле
1
; n = 2, 3, 4,…
Yn =
1 + sin2 Yn-1 + sin2 Yn-2
Значения Y0, Y1 вводятся с клавиатуры. Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
16. Вычислить предел последовательности {Yn} при n → ¥, где
Yn вычисляется по формуле
Y
+ 0.5Yn-3
Yn = 2 n-2
; n = 3, 4, 5,…
Yn-2 + 2Yn4-3 + 1.5
Значения Y0, Y1, Y2 вводятся с клавиатуры. Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
17. Вычислить предел последовательности {Yn} при n ® ¥, где
Yn вычисляется по формуле
Yn =
n
n + 1 + 2 * n2 -1
; n = 1, 2, 3,…
Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
18. Для приближенного решения уравнения Кеплера X–q*
sin(X)=m, 0 < q < 1 полагают X0 = m, X1 = m + q*sin(X0), …,
Xn = m + q*sin(Xn–1),…
Значения m и q вводятся с клавиатуры. Найти решение уравнения Кеплера, принимая за него такое Xn, при котором |Xn – Xn–1| < e.
54
19. Вычислить k A – корень k-й степени из положительного
числа A, пользуясь последовательным приближением:
X0 = A; Xn =
k -1
A
Xn-1 +
;
-1
k
kXnk1
n = 1, 2, 3,…
За корень принять такое Xn, при котором |Xn – Xn–1| < e.
20. Члены последовательностей {Xi} и {Yi} вычисляются по двум
рекуррентным формулам. Вычислить X20,Y20, если
Xi+1 =
Xi * (Yi + 5)-1
; X0 = 3.5;
2
Yi+1 = Xi + 1.6; Y0 = 2.2.
21. Вычислить предел последовательности {Yn} при n ® ¥, где
Yn вычисляется по формулам
X
1
Y1 = ; Yn = (X + Yn2-1 ); n = 2, 3, 4,…
2
2
Значение X (0 ≤ X < 1) вводится с клавиатуры. Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
22. Вычислить предел последовательности {Yn} при n ® ¥, где
Yn вычисляется по формулам:
Y1 = X; Yn = Yn–1(2 – X*Yn–1); n = 2, 3, 4,…
Значение X (X > 0) вводится с клавиатуры. Вычисления прекратить при выполнении условия |Yn – Yn–1| < e.
Примеры программ
Пример 1.
Формулировка задания:
Пользуясь рекуррентной формулой Yi = Yi–1 + Yi–3 * Yi–3, где
i=3,4,…n, для заданного значения n вычислить Yn, если известны
Y0, Y1, Y2.
Ввод исходных данных и вывод результатов вычислений должен осуществляться в разных пользовательских окнах.
Program Recur_1;
{Пользуясь рекуррентной формулой y(i)=y(i-1)+y(i-3)^2
где i=3,4,...,n для заданного значения n вычислить y(n),
если известны y(0), y(1), y(2).
55
Входные данные: y(0),
y(1),
y(2) – значения начальных элементов
n – номер искомого значения.
Выходное данное: y(n) – значение элемента с номером n
}
USES Crt;
{подключение модуля}
{Процедура вывода пользовательского окна на экран}
PROCEDURE Okno(xv,yv,xn,yn,colfona,colbukv:BYTE;zag:STRING);
VAR
i:INTEGER;
BEGIN
Window(xv,yv,xn,yn);
{Установка размеров окна}
TextColor(colbukv);
{Установка цвета шрифта}
TextBackGround(colfona); {Установка цвета фона}
ClrScr; {переводит курсор в левый верхний угол окна и
очищает окно, заливая его цветом установленного фона}
GoToXY((xn-xv) DIV 2 – Length(zag) DIV 2,1);
Write(zag);
Window(xv+1,yv+1,xn-1,yn);
END;
Var
y0, y1, y2,
{исходные данные}
y:LongInt;
{результат}
a, b, c,
{вспомогательные переменные}
i,
{номер текущего элемента}
n:Integer;
{номер искомого элемента}
txt:string;
{вид заголовка пользовательского окна}
Begin
TextBackGround(BLACK);
TextColor(15);
clrscr;
{Окно формулировки задания. Белый текст на синем фоне.}
Okno(8,15,72,20,BLUE,15,’Формулировка задания’);
WriteLn(‘Пользуясь рекуррентной формулой y(i)=y(i-1)+y(i-3)^2’);
WriteLn(‘где i=3,4,...,n для заданного значения n вычислить y(n),’);
WriteLn(‘если известны y(0), y(1), y(2).’);
{Окно ввода исходных данных. Белый текст на зеленом фоне.}
Okno(10,2,70,5,2,15,’Ввод’);
56
Write(‘Задайте значения y(0), y(1) и y(2) -> ‘);
ReadLn(y0,y1,y2);
Write(‘Задайте значение n -> ‘);
ReadLn(n);
a:=y0;
b:=y1;
c:=y2;
{Окно вывода результата. Белый текст на красном фоне.}
Okno(7,7,73,12,4,15,’Вывод’);
{Решение с использованием управляющей структуры While-Do}
i:=3;
While i<=n
Do Begin
y:=y2+y0*y0; {значение очередного элемента последовательности}
y0:=y1;
y1:=y2;
y2:=y;
i:=i+1;
End;
WriteLn(‘While: значение элемента последовательности y(‘,n,’)=’,y);
{Решение с использованием управляющей структуры Repeat-Until}
y0:=a;
y1:=b;
y2:=c;
i:=3;
Repeat
y:=y2+y0*y0;
{значение очередного элемента последовательности}
y0:=y1;
y1:=y2;
y2:=y;
i:=i+1;
Until i>n;
WriteLn(‘Repeat: значение элемента последовательности y(‘,n,’)=’,y);
{Решение с использованием управляющей структуры For-To-Do}
y0:=a;
y1:=b;
y2:=c;
For i:=3 To n
Do Begin
y:=y2+y0*y0; {значение очередного элемента последовательности}
y0:=y1;
57
y1:=y2;
y2:=y;
End;
WriteLn(‘For:
ReadLn;
End.
значение элемента последовательности y(‘,n,’)=’,y);
Пример 2.
Формулировка задания:
Последовательность функций Yn = Yn(X), где 0 < X < 1 определяется следующим образом: Y1 = (X + 1) / 2; Yn = (X + Yn–1 + 1) / 2;
n = 2,3,4…
Для заданного значения X найти предел последовательности,
принимая за таковой значение Yn, удовлетворяющее условию |Yn –
Yn–1| < e, где 0 < e <= 0.1.
Ввод исходных данных и вывод результатов вычислений должны осуществляться в разных пользовательских окнах.
Program Recur_2;
{Последовательность функций yn= yn(x), где 0 < x < 1 определяется
следующим образом: y(1)=(x+1)/2; y(n)=(x+y(n-1)+1)/2; n=2,3,4...
Для заданного x найти предел последовательности, принимая за таковой
значение y(n), удовлетворяющее условию |y(n) – y(n-1)|<eps,
где 0 < eps <= 0.1.
}
Uses Crt;
{Подключение модуля}
{Процедура вывода пользовательского окна на экран}
PROCEDURE Okno(xv,yv,xn,yn,colfona,colbukv:BYTE;zag:STRING);
VAR
i:INTEGER;
BEGIN
Window(xv,yv,xn,yn);
{Установка размеров окна}
TextColor(colbukv);
{Установка цвета шрифта}
TextBackGround(colfona); {Установка цвета фона}
ClrScr; {переводит курсор в левый верхний угол окна и
очищает окно, заливая его цветом установленного фона}
GoToXY((xn-xv) DIV 2 – Length(zag) DIV 2,1);
Write(zag);
Window(xv+1,yv+1,xn-1,yn);
END;
58
Var
x,
{входное данное – значение аргумента}
eps,
{входное данное – точность вычисления}
y1,
{текущее значение функции}
yn:Real;
{значение предела последовательности}
n:Integer; {номер предельного элемента}
Begin
TextBackGround(BLACK);
TextColor(15);
ClrScr;
{Окно формулировки задания. Белый текст на синем фоне.}
Okno(5,15,75,20,BLUE,15,’Формулировка задания’);
WriteLn(‘Последовательность функций yn=yn(x), где 0<x<1 определяется’);
WriteLn(‘следующим образом: y(1)=(x+1)/2; y(n)=(x+y(n-1)+1)/2; n=2,3,4...’);
WriteLn(‘Для заданного x найти предел последовательности, принимая за таковой’);
WriteLn(‘значение y(n), удовлетворяющее условию |y(n)-y(n-1)|<eps’);
Write(‘где 0 < eps <= 0.1’);
{Окно ввода исходных данных. Белый текст на зеленом фоне.}
Okno(9,2,71,5,2,15,’Ввод’);
Write(‘ Введите значение точности: eps=’);
ReadLn(eps);
If (eps<=0)OR(eps>0.1)
Then Begin
{Окно вывода сообщения об ошибке. Красный текст на зеленом фоне.}
Okno(10,11,70,13,GREEN,RED,’Сообщение об ошибке’);
Write(‘ Ошибка ввода! Значение eps должно быть <=0.1 и >0’);
ReadLn;
Exit;
End;
Write(‘ Введите значение аргумента: x=’);
ReadLn(x);
If (x<=0)OR(x>=1)
Then Begin
{Окно вывода сообщения об ошибке. Красный текст на зеленом фоне.}
Okno(10,11,70,13,GREEN,RED,’Сообщение об ошибке’);
Write(‘ Ошибка ввода! Значение x должно быть >0 и <1’);
ReadLn;
Exit;
End;
{Окно вывода результата. Белый текст на красном фоне.}
Okno(8,7,72,12,4,15,’Вывод’);
59
{Цикл While}
n:=1;
y1:=0;
yn:=(x+1)/2;
While (Abs(yn – y1)>eps)AND(n<MAXINT)
{наибольшее значение типа Integer=32767}
Do Begin
y1:=yn;
yn:=(x+y1+1)/2;
n:=n+1;
End;
If n=MAXINT
Then WriteLn(‘ Точность не достигнута.’)
Else WriteLn(‘ Для цикла While предел y(‘,n,’)=’,yn:1:7,’, n=’,n);
{Цикл Repeat}
n:=1;
y1:=0;
yn:=(x+1)/2;
Repeat
y1:=yn;
n:=n+1;
yn:=(x+y1+1)/2;
Until (Abs(yn-y1)<eps)OR(n>=MAXINT);
If n=MAXINT
Then WriteLn(‘ Точность не достигнута.’)
Else WriteLn(‘ Для цикла Repeat предел y(‘,n,’)=’,yn:1:7,’, n=’,n);
{Цикл For}
yn:=(x+1)/2;
for n:=2 To MAXINT
Do Begin
y1:=yn;
yn:=(x+y1+1)/2;
If(Abs(yn-y1)<eps)
Then Break;
End;
If n=MAXINT
Then WriteLn(‘ Точность не достигнута.’)
Else WriteLn(‘ Для цикла For
предел y(‘,n,’)=’,yn:1:7,’, n=’,n);
ReadLn;
End.
60
Лабораторная работа №9. Суммирование рядов
Цель лабораторной работы: применение технологии структурного программирования для решения задач суммирования рядов.
Задание на программирование: используя технологию структурного программирования, разработать программу вычисления
суммы ряда с заданной точностью в заданном интервале допустимых значений аргумента.
Программа должна формировать таблицу, содержащую столбцы:
− значения аргумента;
− значения суммы ряда;
− количество слагаемых, попавших в сумму;
− контрольные значения суммы, полученные с помощью стандартных функций библиотеки.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание и выполнить постановку задачи: сформулировать условие, определить
входные данные и их ограничения, определить вид выходной таблицы значений.
2. Разработать математическую модель:
− вывести рекуррентную формулу для расчета очередного слагаемого;
− описать начальные установки номера слагаемого, величины
слагаемого, значения суммы;
− описать процесс накопления суммы.
3. Построить схему алгоритма. Обосновать выбор циклических
управляющих структур.
4. Составить программу на языке Турбо Паскаль.
5. Использовать оконный интерфейс предыдущих лабораторных работ.
6. Входные данные вводить с клавиатуры по запросу.
7. Выходные данные выводить на экран в форме таблицы с графами: аргумент, сумма, количество слагаемых, контрольное значение суммы.
8. Проверить и продемонстрировать преподавателю работу программы, при этом значение суммы должно совпадать с соответствующим контрольным значением (с заданной точностью). Выходная
таблица должна содержать от 5 до 10 строк.
9. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, текст
программы, контрольные примеры.
61
Варианты индивидуальных заданий
¥
x2n+1
å (-1)n 2n + 1 = x -
1.  arctg(x) =
n=0
n+1
π ¥
+ å (-1)
2 n=0
2.  arctg (x) =
x3 x5 x7
+
+ ..., | x |£ 1.
3
5
7
1
(2n + 1)x2n+1
=
1
1
1
π 1
= - +
+
+ ...), x > 1.
3
5
2 x 3x
5x
7x7
¥
x2n+1
å 2n + 1 = x +
3.  arcth(x) =
n=0
¥
x3 x5 x7
+
+
+ ..., x < 1.
3
5
7
1
1
1
1
1
å (2n + 1)x2n+1 = x + 3x3 + 5x5 + 7x7 + ...,
4.  arcth(x) =
x > 1.
n=0
¥
5.  ln (x) = å (-1)n+1
n=1
(x -1)n
=
n
(x -1)1 (x -1)2 (x -1) 3 (x -1)4
=
+
+ ..., 0 < x £ 2.
1
2
3
4
¥
6.  ln (1 + x) = å (-1)n+1
n=1
xn
x2 x 3 x 4
= x+
+ ..., -1 < x £ 1.
2
3
4
n
¥
xn
x2 x 3 x 4
= -(x +
+
+
+ ...), x < 1.
2
3
4
n
n=1
7.  ln (1 - x) = - å
¥ 2n+1
æ
ö÷
æ1 + x ö÷
x
x3 x5 x7
ç
=2å
= 2ççx +
+
+
+ ...÷÷÷, x < 1.
8.  ln çç
÷
çè
èç 1 - x ø÷
2n + 1
3
5
7
÷ø
n=0
¥
æ x + 1ö÷
1
9.  ln çç
=2å
=
÷
÷
2n+1
çè x -1 ø
n=0 (2n + 1) x
æ1
ö
1
1
1
= 2çç +
+
+
+ ...÷÷÷, x > 1.
èç x 3x3 5x5 7x7
ø÷
10.  ex (1 + x) =
¥
å
n=0
62
xn (n + 1)
n!
=1+
2x 3x2 4x3
+
+
+ ..., x < 2.4.
1!
2!
3!
-x2
11.  e
=
n
¥
x2n x0 x2 x4 x6
=
+
+ ..., x < ¥.
n!
0 ! 1!
2! 3!
å (-1)
n=0
(x -1)2n+1
=
2n+1
n=0 (2n + 1)( x + 1)
¥
12.  ln (x) = 2 å
3
æ
ö÷
çç x -1 (x -1)
(x -1)5
...÷÷÷, x > 0.
= 2çç
+
+
+
3
5
÷
çè x + 1 3(x + 1)
5(x + 1)
ø÷
¥
13.  ln (x) = å
(x -1)n
n=1
nx n
¥
n-1
14.  sin (x) = å (-1)
n=1
15.  cos(x) =
2
¥
n
3
(x -1)
x -1 (x -1)
=
+
+
+ ..., x > 0.5.
2
x
2x
3x3
x2n-1
x3 x5 x7
= x+
+ ..., x < ¥.
3!
5! 7 !
(2n -1)!
x2n
x2
x4
x6
x8
å (-1) (2n)! = 1 - 2! + 4 ! - 6 ! + 8 ! -..., x > 0.
n=0
¥
x2n-1
x3 x5 x7
=x+
+
+
+ ..., x < ¥.
2n -1)!
3!
5!
7!
n=1 (
16.  sh (x) = å
17.  ch (x) =
¥
x2n
x2
x4
x6
x8
å (2n)! = 1 + 2! + 4 ! + 6 ! + 8 ! + ...,
x < ¥.
n=0
¥
2n-1 2n
x
n+1 2
18.  sin2 (x) = å (-1)
=
(2n)!
n=1
3 4
=
21 x2 2 x
25 x6 27 x8
+
+ ..., x < 1.
2!
4!
6!
8!
¥
2n-1 2n
x
n+1 2
19.  cos2 (x) = 1 - å (-1)
n=1
3 4
(2n)!
=
æ 21 x2 2 x
ö÷
25 x6 27 x8
ç
= 1 - çç
+
+ ...÷÷÷, x < 1.
çè 2 !
4!
6!
8!
÷ø
63
20.  arcctg (x) =
=
2n+1
π ¥
n+1 x
+ å (-1)
=
2 n=0
2n + 1
ö÷
π æç
x3 x5 x7
+ çç-x +
+
- ...÷÷÷, x £ 1.
3
2 çè
5
7
÷ø
1
π ¥
n+1
21.  arctg (x) = - + å (-1)
=
2 n=0
(2n + 1)x2n+1
ö
1
1
1
π æ 1
= - + çç- +
+
- ...÷÷÷, x <-1.
3
5
7
2 èç x 3x
ø÷
5x
7x
22.  arcctg (x) =
¥
1
n
å (-1)
n=0
(2n + 1)x2n+1
=
æ1
ö
1
1
1
= çç +
+ ...÷÷÷, x > 1.
çè x 3x3 5x5 7x7
ø÷
¥
23.  arcsin (x) = x + å
=x+
n=1
5
1× 3 × 5...(2n -1)x2n+1
2 × 4 × 6...(2n)(2n + 1)
=
1× 3 × 5x7
x3 1× 3x
+
+
+ ..., x < 1.
2× 3 2× 4 × 5 2× 4 × 6 ×7
2n+1
π ¥ 1× 3 × 5...(2n -1)x
24.  arccos(x) = - å
=
2 n=1 2 × 4 × 6...(2n)(2n + 1)
ö÷
π æç
x3 1× 3x5 1× 3 × 5x7
= - ççx +
+
+
+ ...÷÷÷, x < 1.
2 çè
2× 3 2× 4 × 5 2× 4 × 6 ×7
÷ø
¥
n 1× 3 × 5...(2n - 1) x
25.  arcsh(x) = x + å (-1)
n=1
2n+1
2 × 4 × 6...(2n)(2n + 1)
=
3
æ
1× 3x5 1× 3 × 5x7
÷ö
ç x
= x + çç+
+ ...÷÷÷, x < 1.
çè 2 × 3 2 × 4 × 5 2 × 4 × 6 × 7
ø÷
¥
26.  arcch(x) = ln(2x) - å
1× 3 × 5...(2n -1)
n=1 2 × 4 × 6...(2n)(2n) x
2n
æ 1
ö
1× 3
1× 3 × 5
= ln (2x) - çç
- ...÷÷÷, x > 1.
çè 2 × 2x2 2 × 4 × 4x4 2 × 4 × 6 × 6x6
÷ø
64
27.  sin3 (x) =
2n+1
1 ¥
- 3 2n+1
n+1 3
1
=
x
(
)
å
4 n=1
(2n + 1)!
1 çæ 33 - 3 3 35 - 3 5 37 - 3 7
÷ö
= çç
x x +
x - ...÷÷÷, x < 1.
4 çè 3 !
5!
7!
ø÷
28.  cos3 (x) =
2n
1 ¥
n 3 + 3 2n
1
x =
(
)
å
4 n=0
(2n)!
ö÷
1 æç 30 + 3 0 32 + 3 2 34 + 3 4
= çç
x x +
x - ...÷÷÷, x < 1.
4 çè 0 !
2!
4!
ø÷
Проверочные формулы:
æ x ÷ö
ç
÷÷;
arcsin(x) = arctg çç
÷
çç
è 1 – x2 ÷ø
æ x ö÷
π
ç
÷÷;
arccos(x) = - arctg çç
÷
çç
2
è 1 – x2 ÷ø
arcctg(x) =
π
- arctg(x);
2
1 æ x + 1ö÷
arcth(x) = ln çç
÷, x > 1;
2 çè x -1 ÷ø
æ
ö
arcsh(x) = ln ççx + x2 + 1÷÷;
è
ø
sh(x) =
ex - e-x
;
2
ch(x) =
ex + e-x
.
2
Пример программы
Формулировка задания:
Вычислить ax = ex*ln(a) = 1 + x * ln(a) / 1! + (x * ln(a))2 / 2! + (x *
ln(a))3 / 3!… для заданного диапазона изменения аргумента x. Зна65
чение а и точность вычисления вводятся с клавиатуры. Результаты
представить в виде таблицы: аргумент, сумма, количество слагаемых, контрольное значение.
Program SummaRiada;
{Вычислить a^x=e^(x*ln(a))=1+x*ln(a)/1!+(x*ln(a))^2/2!+...
Результаты представить в виде таблицы:
аргумент, сумма, кол. слагаемых, контрольное значение.}
USES Crt;
{подключение модуля}
{Процедура вывода пользовательского окна на экран}
PROCEDURE Okno(xv,yv,xn,yn,colfona,colbukv:BYTE;zag:STRING);
VAR
i:INTEGER;
BEGIN
Window(xv,yv,xn,yn);
{Установка размеров окна}
TextColor(colbukv);
{Установка цвета шрифта}
TextBackGround(colfona); {Установка цвета фона}
ClrScr; {переводит курсор в левый верхний угол окна и
очищает окно, заливая его цветом установленного фона}
GoToXY((xn-xv) DIV 2 – Length(zag) DIV 2,1);
Write(zag);
Window(xv+1,yv+1,xn-1,yn);
END;
Var
eps:Real;
{точность вычисления}
a:Real;
{значение основания}
x,xn,xk:Real;
{текущее, начальное и конечное значение степени}
h:Real;
{шаг изменения степени}
rez:Real;
{результат вычисления}
pr:Real;
{значение текущего слагаемого}
n:Longint;
{текущий номер слагаемого}
Begin
TextBackGround(BLACK);
TextColor(15);
clrscr;
{Окно формулировки задания. Белый текст на синем фоне.}
Okno(8,20,72,25,BLUE,15,’Формулировка задания’);
WriteLn(‘Вычисление предела произведения (1+1/a(1))*..*(1+1/a(n))’);
WriteLn(‘с заданной точностью 0 <eps<= 0.1’);
WriteLn(‘Значение a(1)=0.5; a(n)=n*(a(n-1)+0.5)’);
Write(‘Вычисления закончить при (1/a(n))<eps’);
66
{Окно ввода. Белый текст на зеленом фоне.}
Okno(9,2,71,8,2,15,’Ввод’);
Write(‘Введите значение точности вычисления: ‘);
ReadLn(eps);
If (eps>0.1)Or(eps<=0)
Then Begin
{Окно вывода сообщения об ошибке. Красный текст на зеленом фоне.}
Okno(10,11,70,13,GREEN,RED,’Сообщение об ошибке’);
Write(‘Ошибка ввода! Значение eps должно быть <=0.1 и >0’);
ReadLn;
Exit;
End;
Write(‘Введите значение числа a: ‘);
ReadLn(a);
Write(‘Введите начальное значение степени: ‘);
ReadLn(xn);
Write(‘Введите конечное значение степени: ‘);
ReadLn(xk);
If xk<xn
Then Begin
{Окно вывода сообщения об ошибке. Красный текст на зеленом фоне.}
Okno(10,11,70,13,GREEN,RED,’Сообщение об ошибке’);
Write(‘Ошибка ввода! xk д.б. >=xn’);
ReadLn;
Exit;
End;
Write(‘Введите значение шага изменения степени: ‘);
ReadLn(h);
If (h<=0)
Then Begin
{Окно вывода сообщения об ошибке. Красный текст на зеленом фоне.}
Okno(10,11,70,13,GREEN,RED,’Сообщение об ошибке’);
Write(‘Ошибка ввода! Значение должно быть >0.’);
ReadLn;
Exit;
End;
{Окно вывода результата. Белый текст на краснном фоне.}
Okno(10,10,70,18,4,15,’Вывод’);
WriteLn(‘Степень |
Сумма |Кол.слаг.|Контрольное значение’);
x:=xn;
Repeat
67
rez:=0;
n:=0;
pr:=1;
While abs(pr)>eps Do
Begin
rez:=rez+pr;
Inc(n);
pr:=pr*x*ln(a)/n;
End;
WriteLn(x:6:2,rez:15:4,n:6,exp(x*ln(a)):17:4);
x:=x+h;
Until x>xk;
End.
Лабораторная работа №10. Обработка одномерных массивов
Цель лабораторной работы: изучение структурной организации массивов и способов доступа к их элементам; совершенствование навыков структурного программирования на языке Турбо
Паскаль при решении задач обработки массивов.
Задание на программирование: используя технологию структурного программирования, разработать программу обработки
одномерных массивов в соответствии с индивидуальным заданием.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание и выполнить постановку задачи: сформулировать условие, определить
входные и выходные данные, их ограничения.
2. Разработать математическую модель: описать с помощью
формул и рисунков структуру массивов и процесс их преобразования.
3. Построить схему алгоритма решения задачи.
4. Составить программу на языке Турбо Паскаль.
5. Использовать оконный интерфейс предыдущих лабораторных работ.
6. Входные данные вводить с клавиатуры по запросу.
7. Выходные данные выводить на экран с пояснениями.
8. Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов, в том числе с ошибочными входными данными. Входные и выходные массивы должны выводиться
в одном и том же формате.
68
9. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, текст
программы, контрольные примеры.
Варианты индивидуальных заданий
1. Дан массив b1, b2, …, b2n. Написать программу построения
массивов x1, x2, …, xn и y1, y2, …, yn, элементы которых равны соответственно значениям: b1, b3, …, b2n–1 и b2, b4, …, b2n.
2. Дан целочисленный массив a1, a2, …, am. Из абсолютных величин его элементов выбрать наибольшую. Далее построить массив, i-й элемент которого равен нулю, если |ai| не совпадает с выбранным значением, и равен 1 в противном случае.
3. Написать программу построения массива с элементами: a1,
a1+a2, a1+a2+a3, a1+a2+a3+…+an по заданному массиву a1, a2, …, an.
4. В вещественном массиве x1, x2, …, xn заменить нулем все отрицательные элементы, предшествующие его максимальному элементу.
5. Даны массивы a1, a2, …, an и b1, b2, …, bn. Получить новый
массив, элементы которого: a1, b1, a2, b2, …, an, bn.
6. Дан вещественный массив x1, x2, …, xm. Все его элементы,
следующие за наибольшим элементом, заменить значением b.
7. Даны вещественные массивы x1, x2, …, xn и y1, y2, …, yn. Преобразовать их по правилу: большее из значений xi и yi принять в
качестве нового значения xi, а меньшее – в качестве нового значения yi.
8. Дан целочисленный массив a1, a2, …, an. Если в массиве нет
ни одной компоненты с заданным значением К, то первую по порядку компоненту этого массива, не меньшую всех остальных компонент, заменить значением К.
9. Написать программу, осуществляющую циклический сдвиг
компонент массива x1, x2, …, xn (n>=2) на одну позицию влево, т. е.
получающую массив x2, x3, …, xn, x1.
10. Дан вещественный массив a1, a2, …, an. Если в этом массиве
есть хотя бы один элемент, значение которого меньше Р, то значения всех отрицательных элементов массива заменить их квадратами, в противном случае массив а умножить на число b.
11. Дан вещественный массив x1, x2, …, xn. Определить сумму и
количество компонент этого массива, принадлежащих отрезку [a, b].
12. Преобразовать массив а1, а2, …, аn так, чтобы его элементы
расположились в обратном порядке: аn, аn–1, …, а1.
69
13. Написать программу выбора среди элементов массива а1, а2,
…, аn наибольшего среди остающихся после выбрасывания наибольшего и всех ему равных. Предполагается, что не все элементы
равны между собой.
14. Из массива а1, а2, …, а3n получить массив b1, b2, …, bn, очередная компонента которого равна среднему арифметическому
тройки очередных компонент массива а.
15. Дан целочисленный массив b1, b2, …, bn. Если элементы этого массива не образуют убывающей последовательности, то заменить его отрицательные элементы единицами.
16. Дан целочисленный массив а1, а2, …, аn, среди элементов которого могут быть равные. Из каждой группы равных между собой
элементов нужно оставить только один, выбросив все остальные.
Освободившийся хвост массива заполнить нулями.
17. Дан вещественный массив а1, а2, …, аn. Если в этом массиве
есть хотя бы один элемент, принадлежащий отрезку [x, y], то все элементы, не принадлежащие этому отрезку, заменить значением k.
18. Дан массив а1, а2, …, аn. Переставить его элементы так, чтобы в начале массива расположились все его неотрицательные элементы, а в конце – отрицательные.
19. Написать программу сжатия массива x1, x2, …, xn отбрасыванием нулевых элементов. Освобождающийся хвост заполнять
нулями.
20. Написать программу выполнения следующего задания: из всех
непрерывных участков массива а1, а2, …, аn, состоящих из нулей, выбрать наибольший по длине. Вывести индексы его начала и конца.
21. Дан вещественный массив x1, x2, …, xm. Найти число компонент, значения которых принадлежат отрезку [c, d], предшествующих первой по порядку отрицательной компоненте.
22. Дан массив b1, b2, …, b2m. Написать программу построения
массива с элементами, соответственно равными: b2m, b1, b2m–1, b2,
…, bm+1, bm.
23. Дан массив x1, x2, …, xn. Все элементы массива, предшествующие наибольшему из его отрицательных элементов, заменить их
квадратами.
24. Дан массив а1, а2, …, а2n. Написать программу построения
массива с элементами, соответственно равными: а1, аn+1, а2, аn+2,
…, аn, a2n.
25. Дан вещественный массив с1, с2, …, сn. Если элементы этого
массива не образуют неубывающей последовательности, то значения всех его отрицательных элементов заменить их квадратами.
70
26. Написать программу циклического сдвига вправо на k позиций одномерного массива из n элементов.
27. Написать программу слияния двух упорядоченных одномерных массивов x1, x2, …, xn и y1, y2, …, ym в третий массив z1, z2, …,
zn+m, также упорядоченный по возрастанию.
28. Написать программу циклического сдвига влево на k позиций одномерного массива из n элементов.
29. Найти сумму и произведение всех элементов массива b1, b2,
…, bm.
30. Найти сумму положительных и число отрицательных элементов массива а1, а2, …, аn.
31. Написать программу вычисления числа положительных и
суммы отрицательных элементов массива x1, x2, …, xm.
32. Заданы упорядоченный по возрастанию массив y1 < y2 <…< ym
и величина x. Известно, что y1 < x < ym. Написать программу определения целого числа k, удовлетворяющего условию: yk–1 < x < yk.
Пример программы
Program ObrMas;
{Последовательный поиск и перестановка местами
минимального и максимального элементов в массиве
Входные данные: k – количество элементов в массиве,
M – массив из целых чисел.
Выходное данное: M – преобразованный массив.}
Const
R=10;
{Размер массива}
Type
TInd=1..R;
{Тип индекса элемента массива}
TElem=Integer; {Тип элемента массива}
TMas=Array [TInd] Of TElem; {Тип массив}
Var
k,i,nmin,nmax:TInd; {1..R}
M:TMas;
{Исходный и преобразованный массив}
min,max:TElem; {Текущие значения минимума и максимума}
Begin
{$R+} {Установка режима контроля индекса элемента}
Write(‘Задайте количество элементов не более ‘,R,’: ‘);
ReadLn(k);
{Ввод массива}
Write(‘Введите ‘,k,’ целых чисел одной строкой:’);
71
For i:=1 To k
Do Read(M[i]);
{Ввод элемента массива}
{Поиск минимума и максимума в массиве}
min:=M[1];
nmin:=1;
{Начальные установки минимума}
max:=M[1];
nmax:=1;
{Начальные установки максимума}
For i:=2 To k
{Перебор элементов массива}
Do If M[i]<min
{Сравнение элемента с минимумом}
Then Begin
min:=M[i];
{Текущий минимум}
nmin:=i
{Номер минимального элемента}
End
Else If M[i]>max
{Сравнение элемента с максимумом}
Then Begin
max:=M[i]; {Текущий максимум}
nmax:=i
{Номер максимального элемента}
End;
{Перестановка местами минимума и максимума}
M[nmin]:=max;
M[nmax]:=min;
{Вывод массива}
WriteLn(‘Массив после перестановки:’);
For i:=1 To k
Do Write (M[i],’ ‘);
{Вывод элемента массива}
WriteLn;
End.
Лабораторная работа №11. Обработка двумерных массивов
Цель лабораторной работы: изучение структурной организации массивов и способов доступа к их элементам; совершенствование навыков процедурного программирования на языке Турбо
Паскаль при решении задач обработки массивов.
Задание на программирование: используя технологию процедурного программирования, разработать программу обработки
двумерных массивов в соответствии с индивидуальным заданием.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание и выполнить постановку задачи: сформулировать условие, определить
входные и выходные данные, их ограничения.
72
2. Разработать математическую модель: описать с помощью
формул и рисунков структуру массивов и процесс их преобразования.
3. Построить схему алгоритма решения задачи.
4. Составить спецификации необходимых подпрограмм: создания матрицы, вывода матрицы, обработки матрицы и др.
5. Составить программу на языке Турбо Паскаль.
6. Использовать оконный интерфейс предыдущих лабораторных работ.
7. Входные данные вводить с клавиатуры по запросу.
8. Выходные данные выводить на экран с пояснениями.
9. Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов, в том числе с ошибочными входными данными. Входные и выходные массивы должны выводиться
в одном и том же формате.
10. Оформить отчет о лабораторной работе в составе: постановка задачи, математическая модель, схема алгоритма решения,
текст программы, спецификация подпрограмм, контрольные
примеры.
Варианты индивидуальных заданий
1. В заданной матрице поменять местами первую строку и строку, содержащую наибольший элемент матрицы.
2. В заданной матрице поменять местами последний столбец и
столбец, содержащий наименьший элемент матрицы.
3. В заданной матрице поменять местами две строки: строку,
содержащую максимальный элемент матрицы, и строку, содержащую минимальный элемент матрицы.
4. В заданной матрице поменять местами главную и побочную
диагонали.
5. В заданной матрице поменять местами первый столбец со
столбцом, содержащим наибольший элемент матрицы.
6. В заданной матрице поменять местами среднюю строку и
средний столбец.
7. В заданной матрице поменять местами последнюю строку со
строкой, содержащей наибольший элемент матрицы.
8. В заданной матрице поменять местами первую строку и первый столбец.
9. В заданной матрице поменять местами последний столбец со
столбцом, содержащим наибольший элемент матрицы.
73
10. В заданной матрице поменять местами последнюю строку со
строкой, содержащей наименьший элемент матрицы.
11. В заданной матрице поменять местами первый столбец
со столбцом, содержащим наибольший элемент главной диагонали.
12. В заданной матрице поменять местами последний столбец и
побочную диагональ.
13. В заданной матрице поменять местами две строки: строку с
указанным номером и строку, содержащую наименьший элемент
матрицы.
14. В заданной матрице из целых чисел поменять местами первую строку и строку, содержащую наибольший по абсолютной величине элемент матрицы.
15. В заданной матрице поменять местами два столбца: содержащий максимальный элемент матрицы и минимальный элемент
матрицы.
16. В заданной матрице поменять местами первую строку и строку, содержащую максимальный элемент матрицы.
17. В заданной матрице поменять местами первый столбец и побочную диагональ.
18. В заданной матрице поменять местами последнюю строку со
строкой, содержащей минимальный элемент матрицы.
19. В заданной матрице поменять местами последний столбец и
столбец, содержащий минимальный элемент матрицы.
20. В заданной матрице поменять местами последнюю строку со
строкой, содержащей максимальный элемент матрицы.
21. В заданной матрице поменять местами последний столбец со
столбцом, содержащим максимальный элемент матрицы.
22. В заданной матрице поменять местами первую строку и
главную диагональ.
23. В заданной матрице поменять местами главную диагональ и
последний столбец.
24. В заданной матрице поменять местами два столбца, содержащих максимальный отрицательный элемент матрицы и минимальный положительный элемент матрицы.
25. В заданной матрице поменять местами последний столбец и
столбец, содержащий минимальный положительный элемент матрицы.
26. В заданной матрице из целых чисел поменять местами первую строку и строку, содержащую максимальный отрицательный
элемент матрицы.
74
Пример программы
Program ObrMatr;
{Программа поиска и перестановки в матрице двух строк:
строки с минимальным и строки с максимальным элементом}
Uses Crt;
{Подключение модуля}
Const
R=10;
{Размер строки (столбца) матрицы}
Type
TInd=1..R;
{Тип индекса элемента матрицы}
TElem=Integer;
{Тип элемента матрицы}
TVect=Array[Tind] Of TElem; {Тип вектор}
TMatr=Array[Tind] Of TVect; {Тип матрица}
{$R+}
Procedure InMatr(kStr,kStb:TInd;Var M:TMatr);
{Процедура ввода значений элементов матрицы.
Входные данные: kStr – количество строк матрицы,
kStb – количество столбцов матрицы.
Выходное данное:
M – матрица.}
Var
i,j:TInd;
{Локальные переменные}
Begin
WriteLn(‘Вводите матрицу по строкам:’);
For i:=1 To kStr
Do Begin
For j:=1 To kStb
Do Read(M[i,j]);
ReadLn;
End;
End;{InMatr}
Function NomMin(kStr,kStb:TInd; Const M:TMatr):TInd;
{Функция определения номера строки с минимальным элементом.
Входные данные: kStr – количество строк матрицы,
kStb – количество столбцов матрицы,
M – матрица.
Выходное данное: NomMin – номер строки с миним. элементом.}
Var
i,j,nmin:TInd;
min:TElem; {Локальные переменные}
Begin
75
min:=M[1,1]; nmin:=1;
For i:=1 To kStr
Do For j:=1 To kStb
Do If M[i,j]<min
Then Begin
min:=M[i,j];
nmin:=i;
End;
NomMin:=nmin;
End; {NomMin}
Function NomMax(kStr,kStb:TInd; Const M:TMatr):TInd;
{Функция определения номера строки с максимальным элементом.
Входные данные:
kStr – количество строк матрицы,
kStb – количество столбцов матрицы,
M – матрица.
Выходное данное: NomMax – номер строки с макс. элементом.}
Var
i,j,nmax:TInd;
max:TElem;
{Локальные переменные}
Begin
max:=M[1,1]; nmax:=1;
For i:=1 To kStr
Do For j:=1 To kStb
Do If M[i,j]>max
Then Begin
max:=M[i,j];
nmax:=i;
End;
NomMax:=nmax;
End; {NomMax}
Procedure ObmenStr(kStr,kStb:TInd; Var M:TMatr);
{Процедура перестановки строк с минимальным и максимальным элементом.
Входные данные: kStr – количество строк матрицы,
kStb – количество столбцов матрицы,
M – матрица целых чисел.
Выходное данное:
M – преобразованная матрица.}
Var
strM:TVect;
nmin,nmax:TInd;
{Локальные переменные}
Begin
nmin:=NomMin(kStr,kStb,M);
76
nmax:=NomMax(kStr,kStb,M);
If nmin<>nmax
Then Begin
strM:=M[nmin];
M[nmin]:=M[nmax];
M[nmax]:=strM;
End;
End; {ObmenStr}
Procedure Okno(x1,y1,x2,y2,cf,ct:Byte);
{Процедура формирования окна}
Begin
Window(x1,y1,x2,y2); {Установка параметров окна}
TextBackGround(cf); {Установка цвета фона}
TextColor(ct);
{Установка цвета текста}
ClrScr;
{Очистка окна}
End;{Okno}
Procedure OutMatr(kStr,kStb:TInd; Const M:TMatr);
{Процедура вывода матрицы.
Входные данные: kStr – количество строк матрицы,
kStb – количество столбцов матрицы,
M – матрица.}
Var
i,j:TInd;
{Локальные переменные}
Begin
For i:=1 To kStr
Do Begin
For j:=1 To kStb
Do Write(M[i,j]:3);
WriteLn;
End;
End;{OutMatr}
Var
n,m,nStb:TInd;
Matr:TMatr;
Begin
Okno(1,1,80,25,0,15);
{На черном фоне белый текст}
Write(‘Размеры матрицы? ‘);
ReadLn(n,m);
Okno(1,6,38,20,2,15);
{На зеленом фоне белый текст}
InMatr(n,m,Matr);
{Ввод матрицы}
77
WriteLn(‘Исходная матрица’);
OutMatr(n,m,Matr);
{Вывод матрицы}
ObmenStr(n,m,Matr);
{Перестановка строк}
Okno(40,6,80,20,3,15);
{На голубом фоне белый текст}
WriteLn(‘Матрица после перестановки строк’);
OutMatr(n,m,Matr);
{Вывод матрицы}
ReadLn;
End.
Лабораторная работа №12. Методы сортировки
Цель лабораторной работы: изучение методов сортировки
статических структур данных; освоение навыков процедурного
программирования на языке Турбо Паскаль при решении задач сортировки матриц.
Задание на программирование: используя технологию процедурного программирования, реализовать заданный метод сортировки
и применить его для указанных фрагментов числовой матрицы в
соответствии с индивидуальным заданием.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание: метод сортировки и вид сортируемых фрагментов матрицы. Исходная матрица, содержащая 2*n строк и 2*n столбцов, не должна содержать
одинаковых и нулевых элементов. Значения элементов матрицы
необходимо формировать программно (с клавиатуры не вводить) с
помощью формул.
2. Разработать математическую модель: описать с помощью
формул и рисунков структуру массива и процесс его преобразования. У результирующей матрицы должны быть отсортированы
заданные фрагменты, а значения элементов не сортируемых фрагментов должны быть обнулены.
3. Построить схему алгоритма решения задачи.
4. Составить спецификации подпрограмм: создания матрицы, вывода матрицы, сортировки заданных фрагментов матрицы, обнуления значений элементов не сортируемых фрагментов матрицы и др.
5. Составить программу на языке Турбо Паскаль.
6. Использовать оконный интерфейс предыдущих лабораторных работ.
7. Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов. Обеспечить одновременный показ в
окнах на экране входной и выходной матриц в одном и том же формате.
78
8. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, спецификация подпрограмм, текст программы, контрольные примеры.
Варианты индивидуальных заданий
Методы сортировки
1. Сортировка по возрастанию методом выбора минимума.
2. Сортировка по возрастанию методом выбора максимума.
3. Сортировка по убыванию методом выбора минимума.
4. Сортировка по убыванию методом выбора максимума.
5. Сортировка по возрастанию методом обмена без флага перестановки.
6. Сортировка по убыванию методом обмена без флага перестановки.
7. Сортировка по возрастанию методом обмена с флагом перестановки.
8. Сортировка по убыванию методом обмена с флагом перестановки.
9. Сортировка по возрастанию методом вставки.
10. Сортировка по убыванию методом вставки.
11. Быстрая сортировка по возрастанию.
12. Быстрая сортировка по убыванию.
Области сортировки элементов матриц
1.
2.
3.
4.
5.
6.
7.
8.
79
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
80
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
Примеры программ
Пример №1
Program MetodSort;
{Методы сортировки числовых массивов}
Const
R=10;
{Длина числового массива}
Type
TInd=1..R;
TElem=Integer;
TMas=Array[TInd] Of TElem;
Procedure SortVibor(n:TInd; Var M:TMas);
{Процедура сортировки массива по возрастанию
методом выбора элементов}
Var
i,k,imin:TInd;
t:TElem;
Begin
81
For i:=1 To n-1
Do Begin
imin:=i; {Поиск очередного минимума}
For k:=i+1 To n
Do If M[k]<M[imin]
Then imin:=k;
{Перестановка элементов}
t:=M[i];
M[i]:=M[imin];
M[imin]:=t;
End;
End; {SortVibor}
Procedure SortObmen(n:TInd; Var M:TMas);
{Процедура сортировки массива по возрастанию
методом обмена элементов}
Var
i,k:TInd;
t:TElem;
Begin
For k:=n DownTo 2
Do For i:=1 To k-1 {Цикл сравнений и обменов}
Do If M[i]>M[i+1] {соседних элементов}
Then Begin
{Перестановка элементов}
t:=M[i];
M[i]:=M[i+1];
M[i+1]:=t;
End;
End; {SortObmen}
Procedure SortObmenF(n:TInd; Var M:TMas);
{Процедура сортировки массива по возрастанию
методом обмена с флагом}
Var
i,k:TInd;
flag:Boolean;
t:TElem;
Begin
k:=n;{Начальное количество не отсортированных элементов}
Repeat
flag:=FALSE; {Нет перестановок}
For i:=1 To k-1
82
Do If M[i]>M[i+1]
Then Begin
{Перестановка элементов}
t:=M[i];
M[i]:=M[i+1];
M[i+1]:=t;
flag:=TRUE; {Была перестановка}
End;
k:=k-1;
Until (Not flag) Or (k=1);
End; {SortObmenF}
Procedure SortVstav(n:TInd; Var M:TMas);
{Процедура сортировки массива по возрастанию
методом вставки элементов}
Var
i,j,k:TInd;
t:TElem;
Begin
For i:=2 To n
Do Begin
t:=M[i]; {Выделение текущего элемента}
j:=1;
{Поиск места вставки в отсортированной части}
While (j<i) And (M[j]<=M[i])
Do j:=j+1;
For k:=i-1 DownTo j
Do M[k+1]:=M[k]; {Сдвиг элементов}
M[j]:=t; {Вставка текущего элемента}
End;
End; {SortVstav}
Procedure SortQuick(Var a: TMas; l,r: TInd);
{Процедура быстрой сортировки массива по возрастанию}
var
i,j: TInd;
x,y: TElem;
Begin
i:=l; j:=r; x:=a[(l+r) DIV 2];
Repeat
While a[i]<x Do i:=i+1;
While x<a[j] Do j:=j-1;
If i<=j
83
Then Begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
i:=i+1; j:=j-1;
End;
Until i>j;
If l<j Then SortQuick(a,l,j);
If i<r Then SortQuick(a,i,r);
End;{SortQuick}
Procedure OutMas(n:Tind; name:String; Var M:Tmas);
{Процедура вывода массива с именем}
Var
i:Tind;
Begin
Write(‘Числовой массив ‘,name,’: ‘);
For i:=1 To n
Do Write(M[i]:3);
WriteLn;
End; { OutMas }
Const
MasA:Tmas= (10, 9, 8, 7, 6, 5, 4, 3, 2, 1);
MasB:Tmas= (19,17,15,13,11, 9, 7, 5, 3, 1);
MasC:Tmas= (20,18,16,14,12,10, 8, 6, 4, 2);
MasD:Tmas= ( 1,10, 2, 9, 3, 8, 4, 7, 5, 6);
MasE:TMas= ( 2, 9, 4,10, 7, 1, 6, 5, 3, 8);
Begin
ClrScr;
SortVibor(R,MasA); OutMas(R,’MasA’,MasA);
SortObmen(R,MasB); OutMas(R,’MasB’,MasB);
SortObmenF(R,MasC); OutMas(R,’MasC’,MasC);
SortVstav(R,MasD); OutMas(R,’MasD’,MasD);
SortQuick(MasE,1,R); OutMas(R,’MasE’,MasE);
ReadLn;
End.
Пример №2
Program SortStrMatr;
{Сортировка строк матрицы по главному столбцу.
Главный столбец матрицы – это столбец с минимальным элементом}
Uses Crt;
{Подключение модуля}
84
Const
R=10;
Type
TInd= 1..R;
TElem= Integer;
TVect= Array[TInd] of TElem;
TMatr= Array[TInd] of TVect;
{$R+}
Procedure InMatr(kstr,kstb:TInd;Var M:TMatr);
{Процедура ввода матрицы}
Var
i,j:TInd;
Begin
Writeln(‘Вводите матрицу по строкам:’);
For i:=1 To kstr
Do Begin
For j:=1 To kstb
Do Read(M[i,j]);
ReadLn;
End;
End;{InMatr}
Function NStbMin(kstr,kstb:TInd; Const M:TMatr):TInd;
{Функция определения номера столбца с минимальным элементом}
Var
i,j:TInd;
min:TElem;
Begin
min:=M[1,1];
NStbMin:=1;
For i:=1 To kstr
Do For j:=1 To kstb
Do If M[i,j]<min
Then Begin
min:=M[i,j];
NStbMin:=j;
End;
End;{NStbMin}
Procedure SortMatr(kstr,nstb:TInd; Var M:TMatr);
{Процедура сортировки строк матрицы методом выбора}
Var
85
i,k,imax:TInd;
StrM:TVect;
Begin
For i:=1 To kstr-1
Do Begin
imax:=i;
For k:=i+1 To kstr
Do If M[k,nstb]>M[imax,nstb]
Then imax:=k;
StrM:=M[i];
M[i]:=M[imax];
M[imax]:=StrM;
End;
End;{SortMatr}
Procedure Okno(x1,y1,x2,y2,cf,ct:Byte);
{Процедура формирования окна на экране}
Begin
Window(x1,y1,x2,y2); {Установка параметров окна}
TextBackGround(cf); {Установка цвета фона}
TextColor(ct);
{Установка цвета текста}
ClrScr;
{Очистка окна}
End;{Okno}
Procedure OutMatr(kstr,kstb:TInd; Const M:TMatr);
{Процедура вывода матрицы}
Var
i,j:TInd;
Begin
For i:=1 To kstr
Do Begin
For j:=1 To kstb
Do Write(M[i,j]:4);
WriteLn;
End;
End;{OutMatr}
Var
N,M,NStb:TInd;
Matr:TMatr;
Begin
Okno(1,1,80,25,0,15);
86
{На черном фоне белый текст}
Write(‘Размеры матрицы? ‘);
ReadLn(N,M);
Okno(1,6,38,20,2,15); {На зеленом фоне белый текст}
InMatr(N,M,Matr);
{Ввод матрицы}
NStb:=NStbMin(N,M,Matr);{Поиск главного столбца}
SortMatr(N,NStb,Matr); {Сортировка строк}
Okno(40,6,80,20,3,15); {На голубом фоне белый текст}
WriteLn(‘Отсортированная матрица’);
OutMatr(N,M,Matr);
ReadLn;
End.
Лабораторная работа №13. Текстовые файлы
Цель лабораторной работы:
− изучение структурной организации, способов доступа к элементам и других особенностей текстовых файлов;
− изучение стандартных средств Турбо Паскаля для работы с
множествами, строками и текстовыми файлами;
− приобретение навыков работы с текстовыми файлами;
− совершенствование навыков процедурного программирования
при решении задач редактирования текстовых файлов.
Задание на программирование: используя технологию процедурного программирования, разработать программу обработки
текстовых файлов с числом строк не менее 5 в соответствии с
индивидуальным заданием. При обработке строк необходимо использовать множества. Массивы не использовать!
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание.
2. Построить дерево подзадач и на его основе – структурную диаграмму программы для решения индивидуальной задачи.
3. Описать и использовать подпрограмму обработки отдельной
строки, подпрограммы проверки существования, создания, просмотра и редактирования текстового файла. Использовать оконный интерфейс предыдущих лабораторных работ.
4. Составить спецификации используемых подпрограмм.
5. Составить программу на языке Турбо Паскаль. Раздел операторов программы должен содержать только вызовы подпрограмм.
6. При демонстрации выполнения программы обеспечить одновременный показ в окнах на экране исходного и отредактированного файлов.
87
7. Оформить отчет о лабораторной работе в составе: постановка
задачи, структурная диаграмма программы, спецификация подпрограмм, текст программы, контрольные примеры.
Варианты индивидуальных заданий
1. Дан текст. Словом текста является последовательность букв
алфавита; между соседними словами – не менее одного пробела.
Перед первым и за последним словом каждой строки – произвольное число пробелов. Найти и сохранить в каждой строке только те
слова, в которых гласные буквы алфавита образуют симметричную
последовательность букв (палиндром). Строчные и прописные буквы считать эквивалентными.
2. Дан текст. Словом текста является последовательность цифр;
между соседними словами – не менее одного пробела. Перед первым и за последним словом каждой строки – произвольное число
пробелов. Найти и сохранить в каждой строке только те слова, в
которых все чётные цифры образуют неубывающую последовательность. Одну цифру не считать неубывающей последовательностью.
3. Дан текст. Словом текста является последовательность цифр
и букв алфавита; между соседними словами – не менее одного пробела. Перед первым и за последним словом каждой строки – произвольное число пробелов. Найти и сохранить в каждой строке только те слова, в которых цифры и буквы алфавита чередуются.
4. Дан текст. Словом текста считается любая последовательность цифр и букв алфавита; между соседними словами – не менее
одного пробела. Перед первым и за последним словом каждой строки – произвольное число пробелов. Найти и сохранить в каждой
строке только те слова, в которых есть хотя бы одна цифра.
5. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Найти и сохранить в каждой строке
те слова, которые содержат только прописные буквы.
6. Дан текст. Словом текста считается любая последовательность
цифр; между соседними словами – не менее одного пробела. Перед
первым и за последним словом каждой строки – произвольное число пробелов. Найти и сохранить в каждой строке только те слова,
которые образованы неубывающей последовательностью символов.
7. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
88
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Удалить из каждой строки те слова,
которые содержат двойные согласные буквы.
8. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Найти и сохранить в каждой строке
только те слова, в которых буквы образуют симметричную последовательность (палиндром). Строчные и прописные буквы считать
эквивалентными.
9. Дан текст. Словом текста считается любая последовательность цифр; между соседними словами – не менее одного пробела.
Перед первым и за последним словом каждой строки – произвольное число пробелов. Поменять местами в каждой строке первое и
последнее слово.
10. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Найти и сохранить в каждой строке
только те слова, которые содержат одинаковое количество гласных
и согласных букв алфавита.
11. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Найти и сохранить в каждой строке
только те слова, количество гласных букв в которых превышает количество согласных.
12. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Найти и сохранить в каждой строке
только те слова, которые начинаются с прописной буквы.
13. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Найти и сохранить в каждой строке только те слова, в которых первая буква слова повторяется еще
один раз.
14. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
89
произвольное число пробелов. Найти и сохранить в каждой строке только те слова, в которых согласные буквы алфавита образуют
симметричную последовательность букв (палиндром). Строчные и
прописные буквы считать эквивалентными.
15. Дан текст. Словом текста считается любая последовательность букв латинского алфавита; между соседними словами – не
менее одного пробела. Перед первым и за последним словом каждой строки – произвольное число пробелов. Найти и сохранить в
каждой строке только те слова, которые совпадают с начальным отрезком латинского алфавита (a, ab, abc, abcd,…).
16. Дан текст. Словом текста считается любая последовательность букв латинского алфавита; между соседними словами – не
менее одного пробела. Перед первым и за последним словом каждой строки – произвольное число пробелов. Найти и сохранить в
каждой строке только те слова, которые совпадают с конечным отрезком латинского алфавита (z, yz, xyz,…).
17. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Найти и сохранить в каждой строке
только те слова, в которых нет повторяющихся букв.
18. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки – произвольное число пробелов. Найти и сохранить в строке только те
слова, в которых каждая буква входит в это слово не менее двух раз.
19. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Найти и сохранить в строке только
те слова, в которых гласные буквы чередуются с согласными.
20. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Перенести первую букву каждого
слова в его конец.
21. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Перенести последнюю букву каждого слова в его начало.
90
22. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Удалить в каждом слове его первую
букву.
23. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Удалить в каждом слове его последнюю букву.
24. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Удалить в каждом слове все последующие повторения первой буквы.
25. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Удалить в каждом слове все предыдущие повторения последней буквы.
26. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Оставить в каждом слове только первые появления каждой буквы.
27. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Если слово нечетной длины, то удалить его среднюю букву.
28. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Изменить в каждой строке порядок
слов на обратный порядок.
29. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Оставив первое слово без изменения,
удалить из строки лишние слова таким образом, чтобы оставшиеся
слова были упорядочены по алфавиту.
91
30. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Сохранить в каждой строке только
первые вхождения каждого слова.
31. Дан текст. Словом текста считается любая последовательность букв алфавита; между соседними словами – не менее одного
пробела. Перед первым и за последним словом каждой строки –
произвольное число пробелов. Найти и сохранить в каждой строке
только те слова, которые встречаются в ней по одному разу.
Пример программы
Program TextFile;
{Сортировка слов в строках текстового файла по алфавиту.
Дан текст. Словом является любая последовательность букв
алфавита. Перед первым словом, после последнего слова и
между словами произвольное число пробелов.
Переставить в каждой строке слова таким образом,
чтобы они были упорядочены по алфавиту.}
Uses Crt; {подключение стандартного модуля Crt}
Procedure Exist(Var nameFT:String);
{Проверка существования файла с указанным именем}
Var
ch:Char;
FT:Text;
Begin
Assign(FT,nameFT);
{$I-} {отключение контроля ошибок ввода-вывода}
Reset(FT);
{$I+} {включение контроля ошибок ввода-вывода}
If IOResult=0
Then Begin
WriteLn(‘Файл с таким именем уже существует!’);
Write(‘Хотите его уничтожить? Y/N ->’);
ReadLn(ch);
If ch In [‘n’,’N’,’т’,’Т’]
Then Repeat
WriteLn(‘Введите другое имя:’);
ReadLn(nameFT);
92
End;
End;
Assign(FT,nameFT);
{$I-}
Reset(FT);
{$I+}
If IOResult=0
Then Begin
WriteLn(‘Файл с таким именем уже существует!’);
Write(‘Хотите его уничтожить? Y/N ->’);
ReadLn(ch);
End;
Until (IOResult<>0)Or(ch In[‘y’,’Y’,’н’,’Н’]);
Procedure SozdFT(Const nameFT:String);
{Создание исходного текстового файла}
Var
FT:Text;
i:Byte;
st:String;
Begin
Assign(FT,nameFT);
ReWrite(FT);
{открытие файла для записи}
Write(‘Начинаем ввод. ‘);
WriteLn(‘Признак окончания ввода – пустая строка.’);
i:=0;
WriteLn(‘Введите ‘,i+1,’-ую строку создаваемого файла:’);
ReadLn(st);
{ввод строки с клавиатуры}
While st<>’’
{пока строка не пустая}
Do Begin
WriteLn(FT,st); {запись строки в файл}
Inc(i);
WriteLn(‘Введите ‘,i+1,’-ую строку создаваемого файла:’);
ReadLn(st);
End;
WriteLn(‘Введено ‘,i,’ строк’);
Close(FT);
{закрытие файла}
End;
Procedure ProsmFT(Const nameFT:String);
{Процедура просмотра текстового файла}
Var
93
st:String;
FT:Text;
Begin
Assign(FT,nameFT);
Reset(FT);
{открытие файла для чтения}
If Eof(FT)
Then Begin
Writeln(‘Файл пуст!’);
WriteLn(‘Нажмите Enter ->’);
ReadLn;
Halt;
End;
Writeln(‘ содержимое файла:’); Writeln;
While Not Eof(FT)
{пока не конец файла:}
Do Begin
Readln(FT,st); {чтение строки из файла}
Writeln(st);
{вывод строки на экран}
End;
Writeln;
Close(FT);
{закрытие файла}
End; {ProsmFT}
Function NovSt(st:String):string;
{Удаление лишних пробелов.
Входное данное:
st-строка из слов, разделенных пробелами.
Выходное данное: NovSt-строка без лишних пробелов.}
Var
L,i:Byte;
Begin
L:=Length(st);
{текущая длина строки}
i:=1;
{текущий номер символа строки}
While i<=L
{пока текущий номер в пределах строки}
Do Begin
If st[i]=’ ‘ {если текущий символ – пробел}
Then Begin
If (i=1) Or (i=L) {пробел в начале или конце строки}
Then Delete(st,i,1) {удаление пробела}
Else If (i<L) And (st[i+1]=’ ‘) {второй пробел подряд}
Then Delete(st,i+1,1)
{удаление пробела}
Else i:=i+1; {текущий номер символа}
L:=Length(st);
{текущая длина строки}
End
94
Else i:=i+1; {новый текущий номер символа}
End;
NovSt:=st;
End; {UdalLP}
Function Slovo(pn:Byte; st:String):String;
{Выделение очередного слова строки.
Входные данные: pn – начальная позиция слова в строке,
st – строка из слов.
Выходное данное: Slovo – очередное слово строки.}
Var
L,p:Byte;
Begin
L:=Length(st);
{длина строки}
p:=pn;
{Цикл поиска очередного пробела}
While (p<=L)And(st[p]<>’ ‘) {Пока не конец слова}
Do p:=p+1;
{изменение позиции в строке}
Slovo:=Copy(st,pn,p-pn);
{Выделение слова}
End;{Slovo}
Function LexSort(st:String):String;
{Сортировка слов строки по алфавиту.
Входное данное:
st-строка из слов, разделенных пробелами.
Выходное данное: LexSort-строка из слов по алфавиту.}
Var
L,
{длина строки}
p1,p2:Byte;
{начальные позиции соседних слов в строке}
sl1,sl2:String; {соседние слова в строке}
flag:Boolean; {флаг перестановки слов}
Begin
L:=Length(st);
{определение длины строки}
Repeat
flag:=FALSE;
{отсутствие перестановки}
p1:=1; sl1:=Slovo(p1,st); {первое слово}
While p1+Length(sl1)<L
{пока sl1 не последнее}
Do Begin
p2:=p1+Length(sl1)+1;{позиция 2-го слова}
sl2:=Slovo(p2,st); {второе слово}
If sl2<sl1
Then Begin
{обмен соседних слов}
Delete(st,p1,p2+Length(sl2)-p1);
95
Insert(sl2+’ ‘+sl1,st,p1);
p1:=p1+Length(sl2)+1;
flag:=TRUE; {есть перестановка}
End
Else Begin
{переход к очередной паре слов}
sl1:=sl2; {новое первое слово}
p1:=p2; {новая позиция слова}
End;
End;
Until Not flag; {до отсутствия перестановок}
LexSort:=st;
End; {LexSort}
Procedure RedaktFT(Const nameF1,nameF2:String);
{Процедура редактирования текстового файла.
Входные данные: F1 – исходный текстовый файл.
Выходные данные: F2 – отредактированный текстовый файл.}
Var
F1,F2:Text;
st:String;
{редактируемая строка}
Begin
Assign(F1,nameF1); Assign(F2,nameF2);
Reset(F1); Rewrite(F2); {открытие файлов}
While Not Eof(F1)
{пока не конец входного файла}
Do Begin
ReadLn(F1,st);
{чтение очередной строки}
st:=NovSt(st);
{удаление лишних пробелов}
st:=LexSort(st);
{сортировка слов строки по алфавиту}
WriteLn(F2,st);
{запись строки в новый файл}
End;
Close(F1); Close(F2);
{закрытие файлов}
End; {RedaktFT}
{Основная программа}
Var
nameF1,nameF2:String;
Begin
ClrScr;
Write(‘Введите имя исходного
ReadLn(nameF1);
Exist(nameF1);
SozdFT(nameF1);
96
{имена текстовых файлов}
{очистка экрана}
файла: ‘);
{создание исходного файла}
Write(‘После создания’);
ProsmFT(nameF1);
Write(‘Введите имя результирующего файла: ‘);
ReadLn(nameF2);
Exist(nameF2);
RedaktFT(nameF1,nameF2);
{редактирование файла}
Write(‘После редактирования’);
ProsmFT(nameF2);
ReadLn;
End. {FileText}
Лабораторная работа №14. Типизированные файлы
Цель лабораторной работы:
− изучение структурной организации, способов доступа к элементам и других особенностей типизированных файлов;
− изучение стандартных подпрограмм библиотеки Турбо Паскаля для работы с типизированными файлами;
− приобретение навыков работы с типизированными файлами;
− совершенствование навыков процедурного программирования
при решении задач обработки типизированных файлов.
Задание на программирование: используя технологию процедурного программирования, разработать программу обработки
типизированных файлов с числом записей не менее 5, структуру
которых определяет индивидуальное задание. Вспомогательные
файлы и массивы не использовать.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание.
2. Построить дерево подзадач и на его основе – структурную диаграмму программы для решения индивидуальной задачи.
3. Сформулировать условие поиска данных в файле и организовать поиск по условию с сохранением найденных записей в новом
файле.
4. Описать и использовать подпрограммы: проверки существования, создания, просмотра, сортировки файла записей, поиска
данных в файле.
5. Предусмотреть в программе возможность выбора варианта
выполнения программы с помощью меню в окне диалога с пользователем.
6. Использовать оконный интерфейс предыдущих лабораторных работ.
97
7. При демонстрации выполнения программы обеспечить одновременный показ в окнах на экране исходного и результирующего
файла.
8. Оформить отчет о лабораторной работе в составе: постановка
задачи, дерево подзадач, спецификация подпрограмм, текст программы, контрольные примеры.
Варианты индивидуальных заданий
1. Самолеты
Тип
Фамилия
конструктора
Год
выпуска
Количество
кресел
Грузоподъемность, т
Тип
самолета
Количество
рейсов
Налет,
тыс. км
Пассажирооборот,
человекокилометр
Номер
борта
Количество
рейсов
Налет,
ч
Налет,
тыс. км
Наименование
рейса
Тип
самолета
Стоимость
билета
Протяженность
линии
Этажность
Год
сооружения
Стоимость,
млн руб.
Вид
ремонта
Стоимость
ремонта
Наименование
подрядчика
2. Расчет движения
Наименование
воздушной
линии
3. Перевозки
Тип
самолета
4. Расписание
Номер
рейса
5. Сооружения аэропорта
Наименование
Площадь
6. Ремонт аэродромных сооружений
Наименование
Шифр
7. Кассы авиабилетов
Номер
кассы
ФИО
кассира
Количество Суммарная
проданных
выручка
билетов
Дата
продажи
Тактовая
частота
Емкость
ОП, Мбайт
Емкость
ЖМД,
Мбайт
Тип
монитора
Количество
жителей
Площадь,
кв. км
Год
основания
Количество
школ
8. Характеристики ПК
Тип
процессора
9. Города
Наименование
98
10. Мосты
Наименование
Высота, м
Ширина, м Количество Протяженность,
опор
км
11. Программные продукты
Наименование
Фирма
Стоимость
Объем
Количество
Назначение
Адрес
Время
работы
Стоимость
билета, руб.
12. Музеи
Наименование
13. Экскурсии
Наименование
Страна
Стоимость, Продолжируб.
тельность, ч
Транспорт
14. Квартиры
Адрес
Площадь кв. м
Сторона
света
Стоимость
1 кв. м,
тыс. руб.
Этаж
Стоимость
билета
Время
сеансов
Адрес
мест
Количество
мест
Фирмаизготовитель
Сорт
Цена,
тыс. руб.
Размер
партии
Дата
Время
Место
Цена билета,
руб.
Поезд
Вагон
Место
Стоимость
проезда, руб.
Автор
Издание
Год
издания
Количество
экземпляров
Цвет
Номер
Год
выпуска
Владелец
Название
линии
Кол-во
станций
Время
стоянки
Время
разворота
15. Кинотеатры
Наименование
16. Магазин
Наименование
товара
17. Театр
Наименование
спектакля
18. Железная дорога
Пункт
назначения
19. Библиотека
Название книги
20. Автоинспекция
Марка машины
21. Метрополитен
Номер линии
Пример программы
{Разработать программу, создающую файл записей, содержащий информацию о проживающих в гостиничном комплексе (фамилия, занимаемый
номер, дата приезда, дата отъезда). Реализовать процедуры добавле99
ния новых записей, поиска по фамилии, вывода информации, начиная с
конкретной даты, удаление записей, сортировки файла по возрастанию
номеров апартаментов.}
Program TipFile;
Uses Crt;
Const
FLOOR=5;
APPART=20;
TEX_1=’Ввод’;
TEX_2=’Сообщения’;
TEX _ 3=’| Фамилия
Type
TData=Record
gg,mm,dd:Byte;
End;
TZap=Record
fam:String;
nomer:Word;
data_pr,
data_ot:TData;
End;
TFZ= File Of TZap;
{число этажей в гостинице}
{число номеров на этаже}
|Занимаемый номер|Дата приезда|Дата отъезда’;
{фамилия проживающего}
{занимаемый номер}
{дата приезда, дата отъезда}
{Процедура рисования окна диалога}
Procedure Okno(xv,yv,xn,yn,colfona,colbukv:Byte;zag:String);
Var
i:Integer;
Begin
Window(xv,yv,xn,yn);
TextColor(colbukv);
TextBackGround(colfona);
ClrScr;
GoToXY((xn-xv) Div 2 – Length(zag) Div 2,1);
Write(zag);
Window(xv+2,yv+2,xn-2,yn-3);
End;
{Проверка наличия файла с указанным именем}
Function FileExist(fname:String):Boolean;
Var
f:TFZ;
100
Begin
Assign(f,fname);
{$i-}
Reset(f);
{$i+}
If IOResult <> 0
Then FileExist:=FALSE
Else Begin
FileExist:=TRUE;
Close(f);
End;
End;
{Создание нового файла}
Procedure SozdFZ(fname:String);
Var
z:TZap;
i:1..FLOOR;
j:1..APPART;
otv:CHAR;
fz:TFZ;
Begin
If FileExist(fname)
Then Begin
Okno(46,2,80,18,13,10,TEX_2);
WriteLn(‘Файл ‘,fname,’ уже существует.’);
WriteLn(‘Хотите создать новый с тем же’);
Write(‘именем? д/н->’);
ReadLn(otv);
If Not (otv In [‘l’,’L’,’д’,’Д’])
Then Exit;
End;
Assign(fz,fname); ReWrite(fz);
Window(1,1,80,25);
TextBackGround(1);
ClrScr;
Repeat
Okno(2,2,45,18,14,10,TEX_1);
ClrScr;
WriteLn(‘Добавляется новая запись:’);
WriteLn;
101
With z
Do Begin
Write(‘ ФИО проживающего..’); ReadLn(fam);
Write(‘ занимаемый номер..’); ReadLn(nomer);
i:=z.nomer Div 100;
j:=z.nomer-i*100;
If(i<1)Or(i>FLOOR)Or(j<1)Or(j>APPART)
Then Begin
WriteLn(‘Ошибка в указании номера’);
WriteLn(‘Повторите ввод после нажатия ENTER’);
ReadLn; Continue;
End;
Write(‘дата приезда: год.(гг)..’);ReadLn(data_pr.gg);
Write(‘
месяц.(мм)..’);ReadLn(data_pr.mm);
Write(‘
день.(дд)..’);ReadLn(data_pr.dd);
Write(‘дата отъезда: год.(гг)..’);ReadLn(data_ot.gg);
Write(‘
месяц.(мм)..’);ReadLn(data_ot.mm);
Write(‘
день.(дд)..’);ReadLn(data_ot.dd);
If (data_pr.gg>data_ot.gg)Or
((data_pr.gg=data_ot.gg)And(data_pr.mm>data_ot.mm))Or
((data_pr.gg=data_ot.gg)And(data_pr.mm=data_ot.mm)And
(data_pr.dd>data_ot.dd))
Then Begin
WriteLn(‘Ошибка в наборе дат.’);
WriteLn(‘Повторите ввод после нажатия ENTER’);
ReadLn; Continue;
End;
End;
Write(fz,z);
Write(‘Продолжать ввод?..д/н..’); ReadLn(otv);
Until Not (otv In [‘l’,’L’,’д’,’Д’]);
Close(fz);
End;
{Сортировка файла вторичному ключу (по занятым номерам апартаментов)}
Procedure Sort_Fz(fname:String);
Var
z1,z2:TZap;
fp:Boolean;
i,nom:Integer;
fz:TFZ;
102
Begin
If Not FileExist(fname)
Then Begin
Okno(46,2,80,18,13,10,TEX_2);
WriteLn(‘файл ‘,fname,’ не существует, сортировка невозможна’);
Exit;
End;
Assign(fz,fname); Reset(fz);
nom:=FileSize(fz)-1;
Repeat
fp:=FALSE;
For i:=0
To nom-1
Do Begin
Seek(fz,i);
Read(fz,z1,z2);
If z1.nomer>z2.nomer
Then Begin
Seek(fz,FilePos(fz)-2);
Write(fz,z2,z1);
fp:=true;
End;
End;
Until Not fp;
Close(fz);
End;
{Печать существующих записей, начиная с указанной даты}
Procedure ProsmFz(fname:String; den:TData);
Var
z:TZap;
i:Byte;
fz:TFZ;
Begin
If Not FileExist(fname)
Then Begin
Okno(46,2,80,18,13,10,TEX_2);
WriteLn(‘Файл ‘,fname,’ не существует’);
WriteLn(‘Просмотр невозможен’);
WriteLn(‘Нажмите ENTER’);
ReadLn; Exit;
End;
103
Okno(1,1,80,25,13,10,’’);
ClrScr;
Write(‘С ‘);
If den.dd<10 Then Write(‘0’);
Write(den.dd,’.’);
If den.mm<10 Then Write(‘0’);
Write(den.mm,’.’);
If den.gg<10 Then Write(‘0’);
WriteLn(den.gg,’ в гостинице проживали:’);
WriteLn;
WriteLn(‘ ‘,TEX_3);
Assign(fz,fname); Reset(fz);
i:=3;
WHILE Not EOF(fz)
Do Begin
Inc(i);
Read(fz,z);
With z Do
Begin
If(den.gg<data_ot.gg)Or
((den.gg=data_ot.gg)And(den.mm<data_ot.mm))Or
((den.gg=data_ot.gg)And(den.mm=data_ot.mm)And
(den.dd<=data_ot.dd))
Then Begin
Write(‘
| ‘);
GoToXY( 9,i); Write(fam);
GoToXY(25,i); Write(‘|
‘,nomer);
With data_pr Do
Begin
Write(‘
| ‘);
If dd<10 Then Write(‘0’);
Write(dd,’.’);
If mm<10 Then Write(‘0’);
Write(mm,’.’);
If gg<10 Then Write(‘0’);
Write(gg);
End;
With data_ot Do
Begin
Write(‘ | ‘);
If dd<10 Then Write(‘0’);
104
Write(dd,’.’);
If mm<10 Then Write(‘0’);
Write(mm,’.’);
If gg<10 Then Write(‘0’);
Write(gg);
End;
End;
End;
WriteLn;
If i=20
Then Begin
Write(‘Для продолжения нажмите ENTER’);
ReadLn;
i:=0;
ClrScr; WriteLn;
End;
End;
WriteLn;
WriteLn(‘Для продолжения нажмите ENTER’);
ReadLn;
Window(1,1,80,25);
TextBackGround(1);
ClrScr;
Close(fz);
End;
{Процедура добавления новых записей}
Procedure Dobavl(fname:String);
Var
z:TZap;
otv:CHAR;
i:1..FLOOR;
j:1..APPART;
fz:TFZ;
Begin
Assign(fz,fname);
If Not FileExist(fname)
Then ReWrite(fz)
Else Begin
Reset(fz);
Seek(fz,FileSize(fz));
End;
105
Repeat
Okno(2,2,45,18,14,10,TEX_1);
ClrScr;
WriteLn(‘Добавляется новая запись:’); WriteLn;
With z
Do Begin
Write(‘ФИО проживающего..’); ReadLn(fam);
Write(‘занимаемый номер..’); ReadLn(nomer);
i:=z.nomer Div 100;
j:=z.nomer-i*100;
If(i<1)Or(i>FLOOR)Or(j<1)Or(j>APPART)
Then Begin
WriteLn(‘Ошибка в указании номера’);
WriteLn(‘Повторите ввод после нажатия ENTER’);
ReadLn; Continue;
End;
Write(‘дата приезда: год.(гг)..’);ReadLn(DATA_pr.gg);
Write(‘
месяц.(мм)..’);ReadLn(DATA_pr.mm);
Write(‘
день.(дд)..’);ReadLn(DATA_pr.dd);
Write(‘дата отъезда: год.(гг)..’);ReadLn(DATA_ot.gg);
Write(‘
месяц.(мм)..’);ReadLn(DATA_ot.mm);
Write(‘
день.(дд)..’);ReadLn(DATA_ot.dd);
If(data_pr.gg>data_ot.gg)Or
((data_pr.gg=data_ot.gg)And(data_pr.mm>data_ot.mm))Or
((data_pr.gg=data_ot.gg)And(data_pr.mm=data_ot.mm)And
(data_pr.dd>data_ot.dd))
Then Begin
WriteLn(‘Ошибка в наборе дат.’);
WriteLn(‘Повторите ввод после нажатия ENTER’);
ReadLn; Continue;
End;
End;
Write(fz,z);
Write(‘Продолжать ввод?..д/н..’); ReadLn(otv);
Until Not (otv In [‘l’,’L’,’д’,’Д’]);
Close(fz);
End;
{Поиск проживающего по фамилии}
Procedure Poisk_Fam(fname:String; famil:String);
Var
106
z:TZap;
otv:CHAR;
i:Word;
fz:TFZ;
Begin
If Not FileExist(fname)
Then Begin
Okno(46,2,80,18,13,10,TEX_2);
WriteLn(‘Файл ‘,fname,’ не существует.’);
WriteLn(‘Поиск записей невозможен.’);
WriteLn(‘Нажмите ENTER.’);
ReadLn; Exit;
End;
Okno(1,1,80,25,13,10,’’);
ClrScr;
WriteLn(‘С фамилией ‘,famil,’ в гостинице проживали:’);
WriteLn;
WriteLn(‘ ‘,TEX_3);
Assign(fz,fname); Reset(fz);
i:=3;
While Not EOF(fz)
Do Begin
Read(fz,z);
If z.fam=famil
Then Begin
Inc(i);
With z Do
Begin
Write(‘
| ‘);
GoToXY( 9,i); Write(fam);
GoToXY(25,i); Write(‘|
‘,nomer);
With data_pr Do
Begin
Write(‘
| ‘);
If dd<10 Then Write(‘0’);
Write(dd,’.’);
If mm<10 Then Write(‘0’);
Write(mm,’.’);
If gg<10 Then Write(‘0’);
Write(gg);
End;
107
With data_ot Do
Begin
Write(‘ | ‘);
If dd<10 Then Write(‘0’);
Write(dd,’.’);
If mm<10 Then Write(‘0’);
Write(mm,’.’);
If gg<10 Then Write(‘0’);
Write(gg);
End;
End;
WriteLn;
End;
If i=20
Then Begin
Write(‘Для продолжения нажмите ENTER’);
ReadLn;
i:=0;
ClrScr;
End;
End;
WriteLn;
WriteLn(‘Для продолжения нажмите ENTER’);
ReadLn;
Window(1,1,80,25);
TextBackGround(1);
ClrScr;
Close(fz);
End;
{Удаление записей}
Procedure Udal_Zap(fname:String);
Var
z:TZap;
otv:CHAR;
nomer:Word;
i:1..FLOOR;
j:1..APPART;
fz,fpr:TFZ;
pr:Boolean;
108
Begin
If Not FileExist(fname)
Then Begin
Okno(46,2,80,18,13,10,TEX_2);
WriteLn(‘Файл ‘,fname,’ не существует.’);
WriteLn(‘Удаление записей невозможно.’);
WriteLn(‘Нажмите ENTER’);
ReadLn; Exit;
End;
Okno(2,2,45,18,14,10,TEX_1);
ClrScr;
Repeat
Assign(fz,fname); Reset(fz);
WriteLn(‘Введите номер апартаментов для поиска:’);
ReadLn(nomer);
i:=nomer Div 100;
j:=nomer-i*100;
If(i<1)Or(i>FLOOR)Or(j<1)Or(j>APPART)
Then Begin
WriteLn(‘Ошибка в указании номера’);
WriteLn(‘Повторите ввод после нажатия ENTER’);
ReadLn; Continue;
End;
Assign(fpr,’C:\pr.txt’); Rewrite(fpr);
pr:=TRUE;
Repeat
Read(fz,z);
If z.nomer=nomer
Then Begin
pr:=FALSE;
ClrScr;
Okno(46,2,80,18,13,10,TEX_2);
WriteLn(‘Производится удаление’);
WriteLn(‘записи для апартаментов ‘,nomer);
Write(‘Подтвердите удаление д/н ->’);
ReadLn(otv);
If (otv In[‘l’,’L’,’д’,’Д’])
Then Continue;
End;
Write(fpr,z);
Until EOF(fz);
109
Erase(fz);
Close(fpr);
Rename(fpr,fname);
Okno(46,2,80,18,13,10,TEX_2);
WriteLn(‘Корректировка закончена.’);
If pr Then WriteLn(‘Запись не обнаружена.’);
Write(‘Продолжать корректировку?.д/н.’); ReadLn(otv);
Until Not (otv In [‘l’,’L’,’д’,’Д’]);
Close(fz);
End;
{основная программа}
Var
fname:String;
z:TZap;
txt:String;
otv:Byte;
den:TData;
ch:Char;
familiya:String;
Begin
TextBackGround(1);
ClrScr;
Okno(2,2,45,18,14,10,TEX_1);
WriteLn(‘Выбор операции:1-создание файла’);
WriteLn(‘
2-поиск записей’);
WriteLn(‘
3-добавление записи’);
WriteLn(‘
4-удаление записи’);
WriteLn(‘
5-просмотр записей’);
WriteLn(‘
6-завершение работы’);
ReadLn(otv);
Repeat
Case otv Of
1:Begin
ClrScr;
WriteLn(‘Введите имя создаваемого файла:’);
ReadLn(fname);
SozdFZ(fname);
End;
2:Begin
110
ClrScr;
Write(‘Введите фамилию для поиска..’);
ReadLn(familiya);
WriteLn(‘Введите имя существующего файла..’);
ReadLn(fname);
Poisk_fam(fname,familiya);
End;
3:Begin
ClrScr;
WriteLn(‘Добавляем новые записи.’);
WriteLn(‘Введите имя существующего файла..’);
ReadLn(fname);
Dobavl(fname);
End;
4:Begin
ClrScr;
WriteLn(‘Удаление записи.’);
WriteLn(‘Введите имя существующего файла..’);
ReadLn(fname);
Udal_Zap(fname);
End;
5:Begin
ClrScr;
WriteLn(‘Введите имя существующего файла..’);
ReadLn(fname);
WriteLn(‘Введите дату начала просмотра’);
Write(‘ год.(гг)..’); ReadLn(den.gg);
Write(‘месяц.(мм)..’); ReadLn(den.mm);
Write(‘ день.(дд)..’); ReadLn(den.dd);
WriteLn(‘Нужна ли предварительная сортировка’);
Write(‘записей по номерам апартаментов? д/н..’);
ReadLn(ch);
If ch In[‘l’,’L’,’д’,’Д’]
Then Sort_Fz(fname);
ProsmFz(fname,den);
End;
6:Begin
Okno(2,2,45,18,14,10,TEX_1);
WriteLn(‘Работа действительно заканчивается?’);
Write(‘д/н..’);
ReadLn(ch);
111
If ch In[‘l’,’L’,’д’,’Д’]
Then Exit;
End;
End;
Window(1,1,80,25);
TextBackGround(1);
ClrScr;
Okno(2,2,45,18,14,10,TEX_1);
ClrScr;
WriteLn(‘Выбор операции:1-создание файла’);
WriteLn(‘
2-поиск записей’);
WriteLn(‘
3-добавление записи’);
WriteLn(‘
4-удаление записи’);
WriteLn(‘
5-просмотр записей’);
WriteLn(‘
6-завершение работы’);
ReadLn(otv);
Until otv=6;
End.
Лабораторная работа №15. Линейные списки
Цель лабораторной работы: изучение способов создания и принципов использования односвязных линейных списков; изучение
стандартных средств языка Турбо Паскаль для работы с динамической памятью; изучение концепций и освоение технологии
модульного программирования; приобретение навыков модульного
программирования на языке Турбо Паскаль при решении задач обработки односвязных линейных списков.
Задание на программирование: используя технологию модульного программирования, разработать программу обработки односвязных линейных списков с числом элементов в списке не менее
пяти в соответствии с индивидуальным заданием. Программа
должна включать модуль, содержащий набор всех необходимых
средств (типов, подпрограмм и т.д.) для решения поставленной
задачи.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание.
2. Разработать математическую модель: описать с помощью
формул и рисунков структуру односвязного линейного списка и
процессы его создания и преобразования.
3. Построить схему алгоритма решения задачи.
112
4. Составить спецификации подпрограмм: инициализации создания, проверки на пустоту, преобразования в соответствии с формулировкой задания и просмотра односвязного линейного списка.
5. Разработать модуль обработки линейного списка в соответствии с заданием.
6. Составить программу на языке Турбо Паскаль.
7. Использовать оконный интерфейс предыдущих лабораторных работ.
8. Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов. Обеспечить одновременный показ в окнах на экране исходного и преобразованного списков.
9. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, спецификация подпрограмм, текст программы, контрольные примеры.
Варианты индивидуальных заданий
1. По списку L построить два новых списка L1 и L2: первый из
элементов с положительными значениями, а второй – из остальных
элементов исходного списка.
2. Вставить в список L новый элемент E1 за каждым вхождением заданного элемента E, если Е входит в L.
3. Вставить в список L новый элемент Е1 перед каждым вхождением заданного элемента Е, если Е входит в L.
4. Вставить в непустой список L перед его последним элементом
пару новых элементов Е1 и Е2.
5. Вставить в непустой список L, элементы которого изначально
упорядочены по не убыванию их значений, новый элемент E так,
чтобы сохранить упорядоченность элементов списка.
6. Удвоить каждое вхождение элемента Е в список L.
7. Удалить из списка L все вхождения элемента Е.
8. Удалить из списка L все элементы с отрицательными значениями.
9. Удалить из списка L после каждого вхождения элемента Е
один элемент, если он есть и отличен от Е.
10. Оставить в списке L только первые вхождения одинаковых
элементов.
11. В списке L из каждой группы подряд идущих элементов с
равными значениями оставить только один.
12. Перевернуть список L, т. е. изменить ссылки в этом списке так,
чтобы его элементы оказались расположенными в обратном порядке.
113
13. Найти элемент непустого списка с максимальным значением.
14. Проверить, есть ли в списке L хотя бы два элемента с одинаковыми значениями.
15. Проверить на равенство два списка L1 и L2.
16. Построить список L1 – копию списка L.
17. Добавить в конец списка L1 все элементы списка L2.
18. Вставить в список L после первого вхождения элемента Е все
элементы списка L1, если Е входит в L.
19. Сформировать список L, включив в него по одному разу элементы, которые входят хотя бы в один из списков L1 и L2.
20. Сформировать список L, включив в него по одному разу элементы, которые входят одновременно в оба списка L1 и L2.
21. Сформировать список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в список L2.
22. Сформировать список L, включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время
не входят в другой.
23. Объединить два упорядоченных списка L1 и L2 в один упорядоченный список, построив новый список L.
24. Объединить два упорядоченных списка L1 и L2 в один упорядоченный список L1, меняя соответствующим образом ссылки в
L1 и L2.
25. Найти среднее арифметическое значений элементов непустого списка.
26. Поменять местами первый и последний элемент списка.
27. Проверить, упорядочены ли элементы списка по алфавиту.
28. Найти сумму значений последнего и предпоследнего элементов списка.
29. Удалить из списка первый отрицательный элемент, если такой есть.
30. Заменить в списке L все вхождения элемента Е1 на Е2.
31. Вставить новый элемент после первого элемента непустого
списка.
32. Перенести в конец списка его первый элемент.
33. Удалить из списка второй элемент, если такой есть.
34. Подсчитать число вхождений элемента Е в список L.
35. Удалить из списка L первое вхождение элемента Е, если такое есть.
36. Перенести в начало списка его последний элемент.
37. Подсчитать количество слов списка, которые совпадают с
последним словом.
114
38. Подсчитать количество слов списка, которые начинаются и
оканчиваются одной и той же литерой.
39. Подсчитать количество слов списка, которые начинаются с
той же литеры, что и следующее слово.
Пример программы
{Определить, входит ли список L1 в список L2}
Program Spisok;
Uses Crt, M_Spis;
{Решение поставленной задачи}
Function Rez(head1,head2:Ref):Boolean;
Var
tec1,
tec2:Ref;
Begin
Rez:=False; {предполагаем, что L1 не входит в L2}
tec2:=head2;
While tec2<>Nil
Do Begin
tec1:=head1;
While (tec2^.inf<>tec1^.inf)And(tec2^.sled<>Nil)
Do tec2:=tec2^.sled;
If tec2^.inf=tec1^.inf
Then Begin
While (tec2^.inf=tec1^.inf)And(tec2<>Nil)And(tec1<>Nil)
Do Begin
tec1:=tec1^.sled;
tec2:=tec2^.sled;
End;
If tec1=Nil
Then Begin
Rez:=True; {L1 входит в L2}
Exit;
End
Else Continue;
End;
tec2:=tec2^.sled;
End;
End;
115
{Рисование окна на экране}
Procedure Okno(x1,y1,x2,y2,bkcl,cl:Byte;title:String);
Var i:Byte;
Begin
Window(x1,y1,x2,y2);
TextBackGround(bkcl);
TextColor(cl);
ClrScr;
GoToXY((x2-x1) Div 2 – Length(title) Div 2,1);
Write(title);
Window(x1,y1+1,x2,y2);
End;
{Основная программа}
Var
head1,
head2:Ref;
Begin
TextBackGround(1);
ClrScr;
Okno(45,1,80,5,12,10,’Исходный список L1:’);
Okno(45,6,80,10,12,10,’Исходный список L2:’);
Okno(45,12,80,18,13,10,’Результат:’);
Okno(1,20,80,25,2,15,’Задача:’);
WriteLn(‘ Определить, входит ли список L1 в список L2.’);
Okno(1,1,43,18,14,10,’Ввод:’);
WriteLn(‘Создание списка L1.’);
SozdSpis(head1);
Okno(45,1,80,5,12,10,’Исходный список L1:’);
Vivod(head1);
Okno(1,1,43,18,14,10,’Ввод:’);
WriteLn(‘Создание списка L2.’);
SozdSpis(head2);
Okno(45,6,80,10,12,10,’Исходный список L2:’);
Vivod(head2);
If Pust(head1) Or Pust(head2)
Then Begin
Okno(45,12,80,18,13,10,’Результат:’);
WriteLn(‘Один из списков пуст.’);
Write(‘Нажмите <Enter>.’);
ReadLn;
116
Exit;
End;
Okno(45,12,80,18,13,10,’Результат:’);
If Rez(head1,head2)
Then WriteLn(‘Список L1 входит в список L2’)
Else WriteLn(‘Список L1 не входит в список L2’);
Write(‘Для продолжения нажмите Enter->’);
ReadLn;
End.
Unit M_Spis;{Модуль работы со списком}
Interface
Type
TElem=Byte;
Ref=^Spis;
Spis=Record
inf:TElem;
sled:Ref;
End;
Procedure InitSpis(Var head,zam:Ref); {инициализации списка}
Function Pust(head:Ref):Boolean;
{проверка списка на пустоту}
Procedure VSpisok(Var head,zam:Ref;nov:TElem);{добавление нового
элемента в конец списка}
Procedure SozdSpis(Var head:Ref);
{создание списка}
Procedure Vivod(head:Ref);
{просмотр списка}
Implementation
{Процедура инициализации списка}
Procedure InitSpis(Var head,zam:Ref);
Begin
head:=Nil;
zam:=Nil;
End;
{Проверка списка на пустоту}
Function Pust(head:Ref):Boolean;
Begin
If head=Nil
Then Pust:=True
{список пуст}
Else Pust:=False;
{список не пуст}
End;
117
{Процедура добавления одного элемента в конец списка}
Procedure VSpisok(Var head,zam:Ref;nov:TElem);
Var
tec:Ref;
Begin
New(tec);
tec^.inf:=nov;
tec^.sled:=Nil;
If Pust(head)
Then head:=tec
Else zam^.sled:=tec;
zam:=tec;
End;
{Процедура создания списка}
Procedure SozdSpis(Var head:Ref);
Var
inf:TElem;
zam:Ref;
Begin
InitSpis(head,zam);
WriteLn(‘Вводите числа одной строкой через пробел.’);
WriteLn(‘Признак конца ввода – ввод 0.’);
Read(inf);
While inf<>0
Do Begin
VSpisok(head,zam,inf);
Read(inf);
End;
ReadLn;
End;
{Просмотр списка}
Procedure Vivod(head:Ref);
Var
prom:Ref;
Begin
prom:=head;
While prom<>Nil
Do Begin
Write(prom^.inf,’ ‘);
prom:=prom^.sled;
118
End;
WriteLn;
WriteLn(‘Нажмите <Enter>’);
ReadLn;
End;
End.
Лабораторная работа №16. Динамические структуры данных:
стек, дек, очередь
Цель лабораторной работы: изучение способов создания и принципов использования динамических структур данных типа стек,
дек, очередь; изучение стандартных средств языка Турбо Паскаль для работы с динамической памятью; совершенствование
навыков модульного программирования на языке Турбо Паскаль
при решении задач обработки динамических структур данных.
Задание на программирование: используя технологию модульного программирования, разработать программу обработки данных,
содержащихся в заранее подготовленном файле, в соответствии с
индивидуальным заданием. Применить динамическую структуру
указанного в задании вида: стек, очередь или дек. Программа должна включать модуль, содержащий набор всех необходимых средств
(типов, подпрограмм и т.д.) для решения поставленной задачи.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание.
2. Разработать математическую модель: описать с помощью
формул и рисунков вид используемой динамической структуры и
процессы её создания и использования.
3. Построить схему алгоритма решения задачи.
4. Использовать подпрограммы, реализующие полный набор
операций для этой структуры:
− допустимые операции для стека: инициализация, проверка
на пустоту, добавление нового элемента в начало, извлечение элемента из начала;
− допустимые операции для очереди: инициализация, проверка
на пустоту, добавление нового элемента в конец, извлечение элемента из начала;
− допустимые операции для дека: инициализация, проверка на
пустоту, добавление нового элемента в начало, добавление нового
элемента в конец, извлечение элемента из начала, извлечение элемента из конца.
119
5. Составить спецификации используемых подпрограмм.
6. Составить программу на языке Турбо Паскаль, включающую
модуль обработки соответствующей динамической структуры.
7. Использовать оконный интерфейс предыдущих лабораторных работ.
8. Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов. Обеспечить одновременный показ в окнах на экране содержимого входного и выходного файлов.
9. Оформить отчет о лабораторной работе в составе: постановка
задачи, математическая модель, схема алгоритма решения, спецификация подпрограмм, текст программы, контрольные примеры.
Варианты индивидуальных заданий
1. Отсортировать строки файла, содержащие названия книг, в
алфавитном порядке с использованием двух деков.
2. Дек содержит последовательность символов для шифровки
сообщений. Дан текстовый файл, содержащий зашифрованное сообщение. Пользуясь деком, расшифровать текст. Известно, что
при шифровке каждый символ сообщения заменялся следующим
за ним в деке по часовой стрелке через один.
3. Дек содержит последовательность символов для шифровки
сообщений. Дан текстовый файл, содержащий сообщение. Пользуясь деком, зашифровать текст, заменяя каждый символ сообщения
следующим за ним в деке против часовой стрелки через один.
4. Написать программу, моделирующую железнодорожный сортировочный узел. Исходный файл содержит информацию об имеющихся вагонах двух типов, при этом количество вагонов обоих
типов одинаково. Последовательность элементов файла неупорядочена, в каждом элементе файла – тип вагона и идентификационный номер вагона. Используя стек («тупик»), за один просмотр
исходного файла сформировать новый файл («состав вагонов»), в
котором типы вагонов чередуются.
5. Даны три стержня и n дисков различного размера. Диски можно надевать на стержни, образуя из них башни. Перенести n дисков
со стержня А на стержень С, сохранив их первоначальный порядок.
При переносе дисков необходимо соблюдать следующие правила:
на каждом шаге со стержня на стержень переносить только один
диск;
диск нельзя помещать на диск меньшего размера;
для промежуточного хранения можно использовать стержень В.
120
Реализовать алгоритм, используя три стека вместо стержней А,
В, С. Информация о дисках хранится в исходном файле.
6. Дан файл из вещественных чисел. Используя очередь, за один
просмотр файла напечатать сначала все числа, меньшие a, затем
все числа из интервала [a, b] и наконец все остальные числа, сохраняя исходный порядок в каждой группе.
7. Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс круглых скобок в
тексте, используя стек.
8. Дан текстовый файл с программой на алгоритмическом языке. За один просмотр файла проверить баланс круглых скобок в
тексте, используя очередь.
9. Дан текстовый файл. Используя очередь, переписать содержимое его строк в новый текстовый файл, перенося при этом в конец
каждой строки все входящие в нее цифры, сохраняя исходный порядок следования среди цифр и среди остальных символов строки.
10. Дан файл из символов. Используя очередь, за один просмотр
файла напечатать сначала все цифры, затем все буквы и наконец
все остальные символы, сохраняя исходный порядок в каждой
группе символов.
11. Дан текстовый файл. Используя стек, сформировать новый
текстовый файл, каждая строка которого содержит символы соответствующей строки исходного файла, записанные в обратном порядке.
12. Дан файл из целых чисел. Используя очередь, за один просмотр файла напечатать сначала все отрицательные числа, затем все
положительные числа, сохраняя исходный порядок в каждой группе.
13. Дан текстовый файл. Используя стек, сформировать новый
текстовый файл, содержащий строки исходного файла, записанные в обратном порядке: первая строка становится последней, вторая – предпоследней и т.д.
14. Дан текстовый файл. Используя очередь, переписать содержимое его строк в новый текстовый файл, перенося при этом в начало каждой строки все входящие в нее буквы, затем все цифры и,
наконец, все остальные символы строки, сохраняя исходный порядок в каждой группе символов.
15. Дан текстовый файл. Используя стек, вычислить значение
логического выражения, записанного в текстовом файле в следующей форме:
< ЛВ > ::= T | F | (N<ЛВ>) | (<ЛВ>A<ЛВ>) | (<ЛВ>X<ЛВ>) |
(<ЛВ>O<ЛВ>),
121
где буквами обозначены логические константы и операции:
T – True, F – False, N – Not, A – And, X – Xor, O – Or.
16. Дан текстовый файл. В текстовом файле записана формула
следующего вида:
<Формула> ::= <Цифра> | M(<Формула>,<Формула>) |
N(Формула>,<Формула>)
< Цифра > ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,
где буквами обозначены функции:
M – определение максимума; N – определение минимума.
Используя стек, вычислить значение заданного выражения.
17. Дан текстовый файл. Используя стек, проверить, является ли
содержимое текстового файла правильной записью формулы вида:
< Формула > ::= < Терм > | < Терм > + < Формула > |
< Терм > – < Формула >;
< Терм > ::= < Имя > | (< Формула >);
< Имя > ::= x | y | z.
18. В текстовом файле хранится выражение, записанное в постфиксной форме. Используя стек, вычислить значение выражения.
Пример выражения: 2 3 5 + * 7 6 – * => 16.
19. В текстовом файле хранится выражение, записанное в инфиксной форме. Используя стек, перевести его в постфиксную
форму и в таком виде записать в новый текстовый файл.
Пример выражения: a + b / c / d * e => a b c / d / e * +.
20. В текстовом файле хранится выражение, записанное в постфиксной форме. Используя стек, перевести его в инфиксную форму и в таком виде записать в новый текстовый файл.
Пример выражения: a b + c * d – f * => ((a + b) * c – d) * f.
Пример программы
{Дан текстовый файл, содержащий числа, разделённые пробелами.
Используя стек, реализовать программу быстрой сортировки.
Используется модуль M_Stek}
Program QSortStek;
Uses Crt, M_Stek;
{Рисование окна на экране}
Procedure Dialog(x1,y1,x2,y2,bkcl,cl:Byte;title:String);
Var i:Byte;
Begin
122
Window(x1,y1,x2,y2);
TextBackGround(bkcl);
TextColor(cl);
ClrScr;
GoToXY((x2-x1) Div 2 – Length(title) Div 2,1);
Write(title);
Window(x1,y1+1,x2,y2);
End;
{Проверка существования файла с таким именем}
Procedure Exist(Var fname:String);
Var
ch:Char;
fisx:Text;
Begin
Assign(fisx,fname);
{$I-} {Отключение контроля ошибок ввода-вывода}
Reset(fisx);
{$I+} {Включение контроля ошибок ввода-вывода}
If IOResult=0
Then Begin
WriteLn(‘ Такой файл уже существует!’);
Write(‘ Хотите его уничтожить? Y/N ->’);
ReadLn(ch);
If ch In [‘n’,’N’,’т’,’Т’]
Then Repeat
WriteLn(‘ Введите другое имя:’);
ReadLn(fname);
Assign(fisx,fname);
{$I-}
Reset(fisx);
{$I+}
If IOResult=0
Then Begin
WriteLn(‘ Такой файл уже существует!’);
Write(‘ Хотите его уничтожить? Y/N ->’);
ReadLn(ch);
End;
Until (IOResult<>0)Or(ch In[‘y’,’Y’,’н’,’Н’]);
End;
End;
123
{Создание текстового файла}
Procedure Make(fname:String);
Var
fisx:Text;
i:Byte;
st:String;
Begin
Assign(fisx,fname);
ReWrite(fisx);
WriteLn(‘ Начинаем ввод.’);
WriteLn(‘ Признак окончания ввода-пустая строка.’);
i:=0;
WriteLn(‘ Введите ‘,i+1,’-ую строку файла:’);
ReadLn(st);
While st<>’’
DO Begin
WriteLn(fisx,st);
Inc(i);
WriteLn(‘ Введите ‘,i+1,’-ую строку файла:’);
ReadLn(st);
End;
WriteLn(‘ Введено ‘,i,’ строк’);
Close(fisx);
End;
{Заполнение исходного массива из файла}
Procedure SozdMas(Const fname:String;Var mas:TMas;n:TInd);
Var
fisx:Text;
ch:TElem;
i:TInd;
Begin
Assign(fisx,fname);
ReSet(fisx);
i:=1;
While (Not Eof(fisx))AND(i<=n)
DO Begin
Read(fisx,ch);
mas[i]:=ch;
i:=i+1;
End;
124
Close(fisx);
End;
{Сортировка массива по возрастанию методом быстрой сортировки}
Procedure QuickSort(Var mas:TMas;n:TInd);
Var
i,j,l,r:TInd;
middle,
temp:TElem;
top:TRef;
Begin
InitSt(top);
VStek(top,1,n);
While top<>NIL
Do Begin
IzSteka(top,l,r);
While l<r
Do Begin
i:=l; j:=r;
middle:=mas[(l+r)Div 2];
While i<j
Do Begin
While mas[i]<middle Do i:=i+1;
While middle<mas[j] Do j:=j-1;
If i<=j
Then Begin
temp:=mas[i];
mas[i]:=mas[j];
mas[j]:=temp;
i:=i+1; j:=j-1;
End;
End;
If i<r
Then VStek(top,i,r);
r:=j;
End;
End;
End;
{Вывод отсортированного массива}
Procedure Vivod(Const mas:TMas;n:TInd);
Var
125
i:TInd;
Begin
For i:=1 To n
Do Write(mas[i]:3);
WriteLn;
Write(‘ Для продолжения нажмите <Enter>’);
ReadLn;
End;
{Основная программа}
Var
fname:String;
mas:TMas;
n:TInd;
Begin
TextBackGround(1);
ClrScr;
Dialog(42,1,80,25,13,10,’Результат:’);
Dialog(1,17,40,25,2,15,’Описание задачи:’);
WriteLn(‘ Дан текстовый файл с числами,’);
WriteLn(‘ разделёнными пробелами.’);
WriteLn(‘ Отсортировать числа, используя метод’);
WriteLn(‘ быстрой сортировки и модуль работы’);
Write(‘ со стеком.’);
Dialog(1,1,40,16,14,10,’Ввод:’);
WriteLn(‘ Создание исходного файла.’);
WriteLn(‘ Введите имя исходного файла’);
ReadLn(fname);
Exist(fname);
Make(fname);
Write(‘ Введите размер массива ->’);
ReadLn(n);
SozdMas(fname,mas,n);
Dialog(42,1,80,25,13,10,’Результат:’);
WriteLn(‘ Исходный массив:’);
Vivod(mas,n);
WriteLn;
QuickSort(mas,n);
WriteLn(‘ Отсортированный массив:’);
Vivod(mas,n);
End.
===============================================================
126
Unit M_Stek;
Interface
Const
R=100;
Type
TInd=1..R;
TElem=Integer;
TRef=^TStek;
TStek=Record
l,r:TInd;
sled:TRef;
End;
TMas=Array[TInd] Of TElem;
Procedure InitSt(Var head:TRef);
{инициализация стека}
Function PuStek(head:TRef):Boolean;
{проверка на пустоту}
Procedure VStek(Var head:TRef;Const l,r:TInd);{занесение в стек}
Procedure IzSteka(Var head:TRef;Var l,r:TInd); {извлечение из стека}
Implementation
{Процедура инициализации стека}
Procedure InitSt(Var head:TRef);
Begin
head:=NIL;
End;
{Проверка стека на пустоту}
Function PuStek(head:TRef):Boolean;
Begin
PuStek:=head=NIL;
End;
{Процедура занесения нового элемента в стек}
Procedure VStek(Var head:TRef;Const l,r:TInd);
Var
tec:TRef;
Begin
New(tec);
tec^.l:=l;
tec^.r:=r;
tec^.sled:=head;
head:=tec;
End;
127
{Процедура извлечения элемента из стека}
Procedure IzSteka(Var head:TRef;Var l,r:TInd);
Var
tec:TRef;
Begin
tec:=head;
l:=head^.l;
r:=head^.r;
head:=head^.sled;
Dispose(tec);
End;
End.
Лабораторная работа №17. Статические и динамические
объекты
Цель лабораторной работы: изучение структуры, свойств и
видов объектов; изучение способов доступа к полям и правил вызова методов объектов; получение навыков объектно ориентированного программирования на языке Турбо Паскаль.
Задание на программирование: используя технологию объектно ориентированного программирования, разработать два варианта программы, реализующей движущийся графический объект
в соответствии с индивидуальным заданием:
− с использованием статического объекта;
− с использованием динамического объекта.
Порядок выполнения работы:
1. Получить у преподавателя индивидуальное задание.
2. Разработать иерархию и структуру объектов, связанных на
принципах наследования, в соответствии с индивидуальным заданием. Дерево наследования должно содержать не менее трех уровней.
3. Описать типы объектов и методы обработки их полей.
4. Составить спецификации необходимых подпрограмм.
5. Составить две программы на языке Турбо Паскаль, реализующие движение графического объекта по заданной траектории в виде
динамического объекта и статического объекта описанного типа.
6. Проверить и продемонстрировать преподавателю работу программы.
7. Оформить отчет о лабораторной работе в составе: постановка
задачи, спецификация подпрограмм, тексты программ, контрольные примеры.
128
Варианты индивидуальных заданий
1. Движение закрашенного прямоугольника по прямоугольному контуру.
2. Движение окружности по окружности.
3. Движение закрашенного квадрата по окружности.
4. Движение треугольника по треугольному контуру.
5. Движение закрашенного эллипса по эллиптическому контуру.
6. Движение закрашенного прямоугольника по треугольному
контуру с изменением цвета при изменении направления движения.
7. Движение закрашенного треугольника по эллиптическому
контуру.
8. Движение закрашенного полукруга по полуокружности.
9. Движение закрашенного круга по кромке экрана с изменением цвета при изменении направления движения.
10. Движение закрашенного полукруга по кромке экрана с поворотом на 90° в углах экрана.
11. Движение отрезка линии в центре экрана по вертикали
сверху вниз и обратно с изменением цвета.
12. Движение отрезка линии по диагонали экрана из левого
нижнего угла в правый верхний угол и обратно с изменением цвета.
13. Движение закрашенного прямоугольника по синусоиде в середине экрана.
14. Движение закрашенного треугольника в центре экрана по
синусоиде сверху вниз.
15. Движение закрашенного круга по синусоиде из левого нижнего угла экрана в правый верхний угол.
16. Движение закрашенного квадрата по синусоиде из левого
верхнего угла экрана в правый нижний угол с изменением цвета.
17. Движение креста из двух отрезков линии по синусоиде по середине экрана слева направо и обратно.
18. Движение цветного сектора по синусоиде по середине экрана
справа налево и обратно.
19. Движение треугольника по синусоиде в середине экрана
справа налево и обратно.
20. Движение окружности по треугольному контуру с изменением цвета при изменении направления движения.
21. Движение закрашенного прямоугольника по полуокружности.
22. Движение закрашенного полукруга по треугольному контуру.
129
23. Движение окружности по синусоиде по середине экрана
справа налево и обратно.
24. Движение закрашенного круга по треугольному контуру.
Примеры программ
{Демонстрация работы с объектами.
Движение полуокружности заданного цвета по часовой стрелке
по эллиптической траектории. Динамическое выделение памяти.}
Program Din_Obj;
Uses Graph,Crt;
Type
TLocation=Object
{«Место»}
x,y:Integer; {Поля данных: координаты местоположения}
Constructor Init(initx,inity:Integer);{Метод «конструктор»}
Destructor Done;
{Метод «деструктор»}
End;
TPoint=Object(TLocation) {“Точка”. Наследник объекта “место”}
visible:Boolean; {Поле данного: светимость}
Procedure Show(color:Byte);Virtual;{Метод «рисование»}
Procedure Hide;Virtual;
{Метод «гашение»}
Procedure MoveTo(newx,newy:Integer;color:Byte);Virtual;{Метод
«перемещение»}
End;
TPolyCirc=Object(TPoint)
{«Полуокр». Наследник объекта “точка”}
radius:Integer; {Поле данного: радиус полуокружности}
Constructor Init(initx,inity,initradius:Integer);{Метод
«конструктор»}
Procedure Show(color:Byte); Virtual; {Метод «рисование»}
Procedure Hide; Virtual;
{Метод «гашение»}
End;
TGraph=Object
{«Графика»}
grdriver:Integer; {Поле данного: драйвер}
grmode:Integer; {Поле данного: мода}
Procedure Init(gb,gm:Integer;path:String);{Метод
“инициализация”}
Procedure Fin;
{Метод “закрытие графики”}
End;
TPPolyCirc=^TPolyCirc;
{Описание методов объекта “место”}
Constructor TLocation.Init(initx,inity:Integer);
130
Begin
x:=initx;
y:=inity;
End;
{текущие координаты}
Destructor TLocation.Done;
Begin
WriteLn;
End;
{Описание методов объекта “точка”}
Procedure TPoint.Show(color:Byte);
Begin
visible:=True;
{Светимость}
PutPixel(x,y,color);
{Рисование точки}
End;
Procedure TPoint.Hide;
Begin
visible:=False;
{Светимость}
PutPixel(x,y,GetBkColor); {Гашение}
End;
Procedure TPoint.MoveTo(newx,newy:Integer;color:Byte);
Begin
Hide;
{Гашение}
x:=newx;
{Новые координаты}
y:=newy;
Show(color); {Рисование}
End;
{Описание методов объекта “графика”}
Procedure TGraph.Init(gb,gm:Integer;path:String);
Begin
grdriver:=gb;
{Номера драйверов}
grmode:=gm;
IniTGraph(grdriver,grmode,path);
End;
Procedure TGraph.Fin;
Begin
CloseGraph;
End;
131
{Описание методов объекта “полуокружность”}
Constructor TPolyCirc.Init(initx,inity,initradius:Integer);
Begin
TPoint.Init(initx,inity);
radius:=InitRadius;
End;
Procedure TPolyCirc.Show(color:Byte);
Begin
SetColor(Color);
{Текущий цвет}
visible:=True;
{Светимость}
Arc(x,y,0,180,radius);
{Рисование}
Line(x-radius,y,x+radius,y);
End;
Procedure TPolyCirc.Hide;
Begin
SetColor(GetBkColor);
{Текущий цвет – это цвет фона}
visible:=False;
{Светимость}
Arc(x,y,0,180,radius);
{Гашение полуокружности}
Line(x-radius,y,x+radius,y);
SetColor(GetColor);
{Текущий цвет}
End;
Var
ppc:TPPolyCirc;
world:TGraph;
x,y,rad,r:Integer;
alf:Real;
col:Byte;
Begin
ClrScr;
WriteLn(‘ Движение полуокружности заданного радиуса со смещением’);
WriteLn(‘ центра по часовой стрелке по эллиптической траектории.’);
WriteLn(‘ Прекращение движения – нажатие ENTER’);
Write(‘ Введите радиус полуокружности->’);
ReadLn(r);
Write(‘ Введите цвет рисования полуокружности (от 1 до 15)->’);
ReadLn(col);
Write(‘Нажмите ENTER->’);
ReadLn;
World.Init(Detect,Detect,’C:\TP\BGI’);
Delay(10000);
132
alf:=0;
rad:=GetMaxY Div 2 – 100; {малый радиус траектории движения центра}
x:=Round((GetMaxX – rad + r) Div 2 + 1.5 * r * Sin(alf));
y:=Round((GetMaxY + r) Div 2 – rad * Cos(alf));
New(ppc,Init(x,y,r));
ppc^.Show(col);
Delay(10000);
Repeat
Delay(100);
alf:=alf + 2 * PI / 360;
x:=Round((GetMaxX – rad + r) Div 2 + 1.5 * r * Sin(alf));
y:=Round((GetMaxY + r) Div 2 – rad * Cos(alf));
ppc^.MoveTo(x,y,col);
Until KeyPressed;
Dispose(ppc,Done);
World.Fin;
End.
{Демонстрация работы с объектами.
Движение полуокружности заданного цвета по часовой стрелке
по эллиптической траектории. Статическое выделение памяти.}
Program Din_Obj;
Uses Graph,Crt;
Type
TLocation=Object
{«Место»}
x,y:Integer; {Поля данных: координаты местоположения}
Constructor Init(initx,inity:Integer);{Метод «конструктор»}
Destructor Done;
{Метод «деструктор»}
End;
TPoint=Object(TLocation) {“Точка”. Наследник объекта “место”}
visible:Boolean; {Поле данного: светимость}
Procedure Show(color:Byte);Virtual;{Метод «рисование»}
Procedure Hide;Virtual;
{Метод «гашение»}
Procedure MoveTo(newx,newy:Integer;color:Byte);Virtual;{Метод
«перемещение»}
End;
TPolyCirc=Object(TPoint)
{«Полуокр». Наследник объекта “точка”}
radius:Integer; {Поле данного: радиус полуокружности}
Constructor Init(initx,inity,initradius:Integer);{Метод
«конструктор»}
Procedure Show(color:Byte); Virtual; {Метод «рисование»}
133
Procedure Hide; Virtual;
{Метод «гашение»}
End;
TGraph=Object
{«Графика»}
grdriver:Integer; {Поле данного: драйвер}
grmode:Integer; {Поле данного: мода}
Procedure Init(gb,gm:Integer;path:String);{Метод
“инициализация”}
Procedure Fin;
{Метод “закрытие графики”}
End;
{Описание методов объекта “место”}
Constructor TLocation.Init(initx,inity:Integer);
Begin
x:=initx; {текущие координаты}
y:=inity;
End;
Destructor TLocation.Done;
Begin
WriteLn;
End;
{Описание методов объекта “точка”}
Procedure TPoint.Show(color:Byte);
Begin
visible:=True;
{Светимость}
PutPixel(x,y,color);
{Рисование точки}
End;
Procedure TPoint.Hide;
Begin
visible:=False;
{Светимость}
PutPixel(x,y,GetBkColor); {Гашение}
End;
Procedure TPoint.MoveTo(newx,newy:Integer;color:Byte);
Begin
Hide;
{Гашение}
x:=newx;
{Новые координаты}
y:=newy;
Show(color); {Рисование}
End;
{Описание методов объекта “графика”}
134
Procedure TGraph.Init(gb,gm:Integer;path:String);
Begin
grdriver:=gb;
{Номера драйверов}
grmode:=gm;
IniTGraph(grdriver,grmode,path);
End;
Procedure TGraph.Fin;
Begin
CloseGraph;
End;
{Описание методов объекта “полуокружность”}
Constructor TPolyCirc.Init(initx,inity,initradius:Integer);
Begin
TPoint.Init(initx,inity);
radius:=InitRadius;
End;
Procedure TPolyCirc.Show(color:Byte);
Begin
SetColor(Color);
{Текущий цвет}
visible:=True;
{Светимость}
Arc(x,y,0,180,radius);
{Рисование}
Line(x-radius,y,x+radius,y);
End;
Procedure TPolyCirc.Hide;
Begin
SetColor(GetBkColor);
{Текущий цвет – это цвет фона}
visible:=False;
{Светимость}
Arc(x,y,0,180,radius);
{Гашение полуокружности}
Line(x-radius,y,x+radius,y);
SetColor(GetColor);
{Текущий цвет}
End;
Var
ppc:TPolyCirc;
world:TGraph;
x,y,rad,r:Integer;
alf:Real;
col:Byte;
Begin
135
ClrScr;
WriteLn(‘ Движение полуокружности произвольного радиуса со смещением’);
WriteLn(‘ её центра по часовой стрелке по эллиптической траектории.’);
WriteLn(‘ Прекращение движения – нажатие ENTER’);
Write(‘ Введите радиус полуокружности->’);
ReadLn(r);
Write(‘ Введите цвет рисования полуокружности (от 1 до 15)->’);
ReadLn(col);
Write(‘Нажмите ENTER->’);
ReadLn;
World.Init(Detect,Detect,’C:\TP\BGI’);
Delay(10000);
alf:=0;
rad:=GetMaxY Div 2 – 100; {малый радиус траектории движения центра}
x:=Round((GetMaxX – rad + r) Div 2 + 1.5 * r * Sin(alf));
y:=Round((GetMaxY + r) Div 2 – rad * Cos(alf));
ppc.Init(x,y,r);
ppc.Show(col);
Delay(10000);
Repeat
Delay(100);
alf:=alf + 2 * PI / 360;
x:=Round((GetMaxX – rad + r) Div 2 + 1.5 * r * Sin(alf));
y:=Round((GetMaxY + r) Div 2 – rad * Cos(alf));
ppc.MoveTo(x,y,col);
Until KeyPressed;
World.Fin;
End.
136
Литература
Основная
1. Марченко А. И., Марченко Л. М. Программирование в среде
Turbo Pascal 7.0. Киев: ВЕК; М.: ДЕСС, 2000. 496 c.
2. Минакова Н. И. и др. Методы программирования: учеб. пособие. М.: Вузовская книга, 1999. 280 с.
3. Бариков Л. Н. Программирование. Программирование на языках высокого уровня: учеб. пособие. СПб.: ГУАП, 2014. 125 с.
4. Бондарев В. М., Рублинецкий В. И., Качко Е. Г. Основы программирования. Харьков: Фолио, 1997. 368 с.
5. ГОСТ 19.701–90 ЕСПД. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения.
6. ГОСТ 7.32–2001. Система стандартов по информации, библиотечному и издательскому делу. Отчет по научно-исследовательской работе. Структура и правила оформления.
7. Программирование на языке Паскаль: задачник; под ред.
О. Ф. Усковой. СПб.: Питер, 2002. 336 с.
8. Фаронов В. В. Турбо Паскаль 7.0. Начальный курс: учеб. пособие. М.: Нолидж, 2000. 616 с.
Дополнительная
1. Delphi 2006: справ. пособие / А. Я. Архангельский. М.: Бином, 2006. 1152 с.
2. Кормен Т. [и др.] Алгоритмы: построение и анализ. М.: Вильямс, 2005. 1290 с.
3. Крук Е. А., Овчинников А. А. Методы программирования и
прикладные алгоритмы: учеб. пособие. СПб.: ГУАП, 2007. 165 с.
137
СОДЕРЖАНИЕ
Введение........................................................................... 3
1. Цели и задачи дисциплины.............................................. 4
2. Содержание дисциплины................................................. 5
3. Методы и технологии разработки алгоритмов и программ.... 10
4. Методические указания к выполнению лабораторных
работ................................................................................ 20
Лабораторная работа №1. Работа с файлами
в интегрированной среде программирования...................... 20
Лабораторная работа №2. Отладка и тестирование
программы.................................................................... 21
Лабораторная работа №3. Управляющая структура
«Следование»................................................................. 22
Лабораторная работа №4. Поиск экстремума...................... 27
Лабораторная работа №5. Управляющая структура
«Развилка».................................................................... 31
Лабораторная работа №6. Управляющая структура
«Выбор варианта»........................................................... 39
Лабораторная работа №7. Управляющая структура
«Циклы»....................................................................... 42
Лабораторная работа №8. Рекуррентные вычисления.......... 51
Лабораторная работа №9. Суммирование рядов................... 61
Лабораторная работа №10. Обработка одномерных
массивов........................................................................ 68
Лабораторная работа №11. Обработка двумерных массивов.. 72
Лабораторная работа №12. Методы сортировки................... 78
Лабораторная работа №13. Текстовые файлы...................... 87
Лабораторная работа №14. Типизированные файлы............ 97
Лабораторная работа №15. Линейные списки..................... 112
Лабораторная работа №16. Динамические структуры
данных: стек, дек, очередь............................................... 119
Лабораторная работа №17. Статические и динамические
объекты......................................................................... 128
Литература....................................................................... 137
138
Учебное издание
Бариков Леонид Николаевич
БАЗОВЫЕ АЛГОРИТМЫ
ОБРАБОТКИ ИНФОРМАЦИИ
Учебное пособие
Редактор Л. А. Яковлева
Верстальщик С. Б. Мацапура
Сдано в набор 06.02.14. Подписано к печати 24.04.14.
Формат 60×84 1/16. Бумага офсетная. Усл. печ. л. 8,0.
Уч.-изд. л. 8,4. Тираж 100 экз. Заказ № 179.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
139
Для заметок
Документ
Категория
Без категории
Просмотров
4
Размер файла
2 227 Кб
Теги
barikov
1/--страниц
Пожаловаться на содержимое документа