[ «Учреждение образования Белорусский государственный университет информатики и радиоэлектроники Кафедра Вычислительные методы и программирование Шестакович В. П. Электронный учебно-методический комплекс по дисциплине ...»
Министерство образования Республики Беларусь
Учреждение образования
«Белорусский государственный университет информатики и радиоэлектроники»
Кафедра «Вычислительные методы и программирование»
Шестакович В. П.
Электронный учебно-методический комплекс
по дисциплине
«ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ»
Для студентов специальностей 36 04 01 «Электронно-оптические системы и технологии», 39 02 02 «Проектирование и производство радиоэлектронных средств», 39 02 03 «Медицинская электроника», 39 02 01 «Моделирование и компьютерное проектирование радиоэлектронных средств», 38 02 03 «Техническое обеспечение безопасности».Курс лекций Минск
СОДЕРЖАНИЕ
ЛЕКЦИЯ 1. КАК УСТРОЕНА ЭВМ И КАК ОНА РАБОТАЕТ................. 1.1. История создания ЭВМ1.2. Структура ПЭВМ
1.3. Размещение данных и программ в памяти ПЭВМ
1.4.Файловая система хранения информации
1.5.Операционная система
ЛЕКЦИЯ 2. КАК CОСТАВЛЯЮТСЯ И ВЫПОЛНЯЮТСЯ
ПРОГРАММЫ В СИСТЕМЕ DELPHI2.1. Понятие алгоритма и способы его записи
2.2. Общая характеристика языка Pascal
2.3. Как составляется программа в системе Delphi
2.4. Наша первая программа реализует линейный алгоритм............ ЛЕКЦИЯ 3. БАЗОВЫЕ ЭЛЕМЕНТЫ ЯЗЫКА ПАСКАЛЬ
3.1. Данные и их типы
3.2. Операции над переменными основных скалярных типов......... ЛЕКЦИЯ 4. ПРОГРАМИРОВАНИЕ РАЗВЕТВЛЯЮЩИХСЯ
4.1. Понятие разветвляющегося алгоритма
4.2. Оператор условия if
4.3. Оператор выбора Case
4.4. Некоторые возможности, предоставляемые Delphi для организации разветвлений
ЛЕКЦИЯ 5. СОСТАВЛЕНИЕ И ПРОГРАМИРОВАНИЕ
ЦИКЛИЧЕСКИХ АЛГОРИТМОВ5.1. Понятие цикла
5.2. Оператор Repeat...Until
5.3. Оператор While...do
5.4. Оператор For...do
5.5. Вложенные циклы
5.6. Примеры некоторых часто встречающихся циклических алгоритмов
ЛЕКЦИЯ 6. ОТЛАДКА ПРОГРАММ И ОБРАБОТКА
ИСКЛЮЧИТЕЛЬНЫХ СИТУАЦИЙ6.1. Ошибки на этапе компиляции
6.2. Ошибки на этапе выполнения
6.3. Понятие исключительной ситуации
6.4. Защищенные блоки
6.5. Некоторые стандартные типы исключительных ситуаций........ 6.6. Инициирование собственных исключительных ситуаций........ 6.7. Примеры фрагментов программ
ЛЕКЦИЯ 7. СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ
МАССИВОВ7.1. Понятие массива
7.2. Некоторые возможности ввода-вывода в Delphi
7.3. Примеры часто встречающихся алгоритмов работы с массивами
ЛЕКЦИЯ 8. ИСПОЛЬЗОВАНИЕ УКАЗАТЕЛЕЙ
8.1. Статическое и динамическое распределение оперативной памяти
8.2. Понятие указателя
8.3. Наложение переменных
8.4. Динамическое распределение памяти
8.5. Организация динамических массивов
ЛЕКЦИЯ 9. ПОДПРОГРАММЫ И БИБЛИОТЕКИ
9.1. Понятие подпрограммы
9.2. Описание подпрограмм
9.3. Передача данных между подпрограммой и вызывающей ее программой
9.4. Оформление подпрограмм в библиотечный модуль.................. 9.5. Примеры подпрограмм, оформленных в отдельные библиотечные модули
ЛЕКЦИЯ 10. ИСПОЛЬЗОВАНИЕ ПЕРЕМЕННЫХ ТИПА
МНОЖЕСТВА10.1. Понятие множества
10.2. Операции над множествами
10.3. Примеры работы с множествами
ЛЕКЦИЯ 11. ИСПОЛЬЗОВАНИЕ СТРОКОВЫХ ДАННЫХ.................. 11.1. Зачем нужны строки
11.2. Описание переменных строкового типа
11.3. Основные операции над переменными строкового типа......... 11.4. Некоторые процедуры и функции обработки строк................. 11.5. Примеры алгоритмов обработки строк
ЛЕКЦИЯ 12. ПРОГРАММИРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ
ЗАПИСЕЙ12.1. Понятие записи
12.2. Операции над записями
12.3. Использование записей для работы с комплексными числами ЛЕКЦИЯ 13. ИСПОЛЬЗОВАНИЕ ФАЙЛОВ
13.1. Понятие файла
13.2. Операции над файлами
13.2.1. Типизированные файлы
13.2.2. Текстовые файлы
13.2.3. Нетипизированные файлы
13.3. Подпрограммы работы с файлами
13.4. Компоненты OpenDialog и SaveDialog
ЛЕКЦИЯ 14. ПРОГРАММИРОВАНИЕ С ОТОБРАЖЕНИЕМ
ГРАФИЧЕСКОЙ ИНФОРМАЦИИ14.1. Как рисуются изображения
14.2. Построение графиков с помощью компонента Chart............. ЛЕКЦИЯ 15. ПРОГРАММИРОВАНИЕ С
ИСПОЛЬЗОВАНИЕМ
15.1. Понятие рекурсии
15.2. Примеры рекурсивных вычислений
ЛЕКЦИЯ 16. ПОИСК И СОРТИРОВКА МАССИВОВ
16.1. Организация работы с базами данных
16.2. Поиск в массиве записей
16.3. Сортировка массивов
16.3.1. Метод пузырька
16.3.2. Метод прямого выбора
16.3.3. Метод Шелла
16.3.4. Метод Хоара (Hoare)
ЛЕКЦИЯ 17. РАБОТА СО СПИСКАМИ НА ОСНОВЕ
ДИНАМИЧЕСКИХ МАССИВОВ17.1. Работа со списками
17.2. Добавление нового элемента в список на заданную позицию
17.3. Удаления элемента с заданным номером
17.4. Пример программы
ЛЕКЦИЯ 18. СВЯЗАННЫЕ СПИСКИ НА ОСНОВЕ РЕКУРСИВНЫХ
ДАННЫХ18.1. Что такое стек и очередь
18.2. Понятие рекурсивных данных и однонаправленные списки. 18.3. Процедуры для работы со стеками
18.4. Процедуры для работы с односвязными очередями.............. 18.5. Работа с двухсвязными очередями
18.6. Процедуры для работы с двусвязными очередями................. ЛЕКЦИЯ 19. АЛГОРИТМЫ РЕШЕНИЯ СИСТЕМ
ЛИНЕЙНЫХ
19.1. Основные понятия и определения
19.2. Прямые методы решения СЛАУ
19.2.1. Метод Гаусса
19.2.2. Метод прогонки
19.2.3. Метод квадратного корня
19.3. Итерационные методы решения СЛАУ
19.3.1. Метод простой итерации
19.3.2. Метод Зейделя
19.3.3. Понятие релаксации
ЛЕКЦИЯ 20. АППРОКСИМАЦИЯ ФУНКЦИЙ
20.1. Зачем нужна аппроксимация функций?
20.2. Что такое интерполяция
20.3. Многочлены и способы интерполяции
20.3.1. Интерполяционный многочлен Ньютона
20.3.2. Линейная и квадратичная интерполяция
20.3.3. Интерполяционный многочлен Лагранжа
20.3.4. Интерполяция общего вида, использующая прямое решение системы (20.2) методом Гаусса
20.4. Среднеквадратичная аппроксимация
20.4.1. Метод наименьших квадратов
ЛЕКЦИЯ 21. ВЫЧИСЛЕНИЕ ПРОИЗВОДНЫХ И ИНТЕГРАЛОВ..... 21.1. Формулы численного дифференцирования
21.2. Формулы численного интегрирования
21.2.1. Формула средних
21.2.2. Формула трапеций
21.2.3. Формула Симпсона
21.2.4. Формулы Гаусса
ЛЕКЦИЯ 22. МЕТОДЫ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.. 22.1. Как решаются нелинейные уравнения
22.2. Итерационные методы уточнения корней
22.2.1. Метод простой итерации
22.2.2. Метод Ньютона
22.2.3. Метод секущих
22.2.4. Метод Вегстейна
22.2.5. Метод парабол
22.2.6. Метод деления отрезка пополам
ЛЕКЦИЯ 23. МЕТОДЫ ОПТИМИЗАЦИИ
23.1. Постановка задач оптимизации, их классификация............... 23.2. Методы нахождения минимума функции одной переменной 23.2.1. Метод деления отрезка пополам
23.2.2. Метод золотого сечения
23.2.3. Метод Фибоначчи
23.2.4. Метод последовательного перебора
23.2.5. Метод квадратичной параболы
23.2.6. Метод кубической параболы
ЛЕКЦИЯ 24. РЕШЕНИЕ ЗАДАЧИ КОШИ ДЛЯ ОБЫКНОВЕННЫХ
ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ24.1. Задачи для обыкновенных дифференциальных уравнений... 24.2. Основные положения метода сеток для решения задачи Коши
24.2.1. Явная схема 1-го порядка (метод Эйлера)
24.2.2. Неявная схема 1-го порядка
24.2.3. Неявная схема 2-го порядка
24.2.4. Схема предиктор-корректор (Рунге-Кутта) 2-го порядка
24.2.5. Схема Рунге-Кутта 4-го порядка
24.3. Многошаговые схемы Адамса
24.3.1. Явная экстраполяционная схема Адамса 2-го порядка.. 24.3.2. Явная экстраполяционная схема Адамса 3-го порядка.. 24.3.3. Неявная схема Адамса 3-го порядка
ПРИЛОЖЕНИЕ 1. Процедуры и функции для преобразования строкового представления чисел
ПРИЛОЖЕНИЕ 2. Математические формулы
ПРИЛОЖЕНИЕ 3. Таблицы символов ASCII
ЛИТЕРАТУРА
ЛЕКЦИЯ 1. КАК УСТРОЕНА ЭВМ И КАК ОНА РАБОТАЕТ
Проблема вычислений сопровождает человечество на всем историческом отрезке его существования. Первый счетный инструмент абак был известен еще в Y веке до нашей эры в Египте, Финикии, Греции и представлял дощечку, покрытую слоем песка, на которой острой палочкой проводили линии и в получавшихся колонках по позиционному принципу размещали камешки. В древнем Риме абак назывался Calculi. От этого слова произошло в дальнейшем латинское calculatore (вычислять).С конца XY столетия в Западной Европе получил распространение тип абака, известный как «счет на линиях». На разлинованную таблицу накладывались специальные жетоны, горизонтальные линии таблицы соответствовали единицам, десяткам и т.д., вертикальные линии образовывали столбцы для отдельных слагаемых или множителей.
Первую счетную машину для выполнения сложений и вычитаний изобрел и сконструировал в 1623 году профессор математики и астрономии Тюбингенского университета В.Шинкард. Изготовленная в одном экземпляре машина Шинкарда сгорела во время пожара в 1624 году и не оказала влияния на развитие идей счетной техники.
Биография механических счетных машин ведется от арифметической машины французского математика, физика и философа Б.Паскаля, созданной в 1642 году. Над счетной машиной Б.Паскаль работал 12 лет и сделал около 50 действующих моделей. Первый арифмометр, выполняющий все четыре арифметических действия, был предложен в 1670 году немецким ученым Г.В.Лейбницем. В Беларуси первая суммирующая машина была изобретена и изготовлена в 1770 году Евной Якобсоном, часовым матером и механиком в г. Несвиже.
Идею универсальной вычислительной машины с программным управлением впервые предложил в своем неосуществленном проекте в 1834 году английский ученый Ч.Бэббедж. Ее структура совпадала по существу со структурой современных ЭВМ. Однако, большинство из современников ученого не поняли его идей и имя истинного «отца компьютеров» было на долгие годы забыто.
Отличительной особенностью электронных вычислительных машин (ЭВМ) от счетных машин является наличие устройства управления вычислениями и принцип хранения программы. Еще одной особенностью современных ЭВМ является применение двоичной системы счисления.
Двоичную арифметику разработал Г.В.Лейбниц. Он также предложил арифметизацию логики за 200 лет до создания алгебры Дж.Буля (1815). Так же как двоичная арифметика представляет все числа с помощью двух символов (0,1) так и Булева алгебра оперирует с двумя понятиями (истина, ложь) и тремя операциями (и, или, не).
С помощью этих понятий можно смоделировать любые логические цепочки и построить 16 логических функций. На этой основе строятся все современные логические схемы различной сложности, реализуемые в ЭВМ.
Первая ЭВМ была создана в 1945 году (США), представляла огромное сооружение, содержащее 18000 электронных ламп, 1500 реле и выполняла около 3000 умножений в секунду. Она использовалась для баллистических расчетов, предсказаний погоды и некоторых научно-технических расчетов для военных целей. Мировой парк ЭВМ к 1965 году насчитывал порядка тыс. компьютеров, к началу 1975 – более 200 тысяч.
Первые персональные ЭВМ (ПЭВМ) появились в начале 70 годов.
ПЭВМ содержат клавиатуру, близкую к клавиатуре печатной машинки, системный блок, реализованный на одной плате и графический дисплей. Все это при желании можно разместить в «дипломате». Скорость вычислений достигает 108 операций в секунду. За счет выпуска больших партий достигнута относительная дешевизна ПЭВМ и уже близко то время, когда электронный помощник будет в каждой квартире.
Схема ПЭВМ представлена на рис. 1.
ЖД ГД СД
Системный блок ПЭВМ содержит следующие блоки:– центральный процессор (ЦП), который осуществляет управление работой и выполнение расчетов по программе;
– блок «быстрой» оперативной памяти (ОЗУ), в которой во время работы компьютера располагаются выполняемые программы (заметим, что при выключении компьютера эта память очищается);
– блок постоянной памяти (ПЗУ), которая содержит программы, необходимые для запуска компьютера (эти программы не стираются при его выключении);
– жесткий магнитный диск (ЖД), получивший название винчестер;
– дисковод (ГД) для сменных, гибких магнитных дисков (дискет).
– сидиром (СД) – для чтения с компакт-дисков.
В системный блок встроены электронные схемы, управляющие работой различных устройств, входящих в состав компьютера. К системному блоку подключаются дисплей (монитор) для отображения информации, клавиатура для ввода данных и команд, устройство для визуального управления (мышь), печатающее устройство (принтер), устройство для считывания и ввода графической информации (сканер).
1.3. Размещение данных и программ в памяти ПЭВМ Данные и программы во время работы ПЭВМ размещаются в оперативной памяти, которая представляет собой последовательность пронумерованных ячеек. По указанному номеру процессор находит нужную ячейку, поэтому номер ячейки называется ее адресом. Минимальная адресованная ячейка (согласно стандарту IBM), с точки зрения программиста, состоит из 8 двоичных позиций, т.е. в каждую позицию могут быть записаны либо 0, либо 1.
Объем информации, который помещается в одну двоичную позицию, называется бит. Объем информации равный 8 бит называется байтом.
Таким образом, в одной ячейке из 8 двоичных разрядов помещается объем информации в один байт. Поэтому объем памяти принято оценивать количеством байт (1024 Байт = 1 Килобайт, 1024 Килобайт = 1048576 Байт = 1 Мегабайт, 1024 Мегабайт = 1073741824 Байт = 1 Гигабайт,).
Для помещения данных в такие ячейки производится их запись с помощью нулей и единиц (кодирование). При кодировании каждый символ, допускаемый на клавиатуре, заменяется последовательностью из 8 двоичных разрядов в соответствии со стандартной кодовой таблицей. (т.е. один символ размещается в одном байте). Например, в соответствии с таблицей кодов ASCII D=(01000100); F=(00100110); 4=(00110100).
При кодировании чисел они предварительно преобразуются в двоичное представление. Например 2=121+020=102; 5=122+021+120=1012; 256=128=1000000002.
Заметим, что с увеличением числа количество разрядов для его представления в двоичной системе резко возрастает. Поэтому для размещения большого числа выделяется несколько подряд расположенных однобайтных ячеек. В этом случае адресом такой расширенной ячейки является адрес первого байта. Один бит такой ячейки выделяется под знак числа. Числа, размещенные таким естественным образом, называются числами с фиксированной запятой, или просто целыми.
Для хранения дробных чисел, или слишком больших, их предварительно приводят к нормализованному виду. Например, -35,6 = -0.35610+2, где – мантисса, +2 – порядок. После этого переводят порядок и мантиссу в двоичную систему. Такое число запоминается в комбинированной ячейке, один байт которой содержит порядок, несколько других содержат мантиссу.
Числа, размещенные таким образом, называются числами с плавающей запятой или просто действительными.
Программа – это последовательность команд, которые помещаются в памяти и выполняются процессором в указанном порядке.
Команда размещается в комбинированной ячейке следующим образом.
Первый байт содержит код операции (КОП), (например + или – или *), которую необходимо выполнить над содержимым ячеек памяти. В одной, двух или трех ячейках (операндах команды) по 2 или 4 байта содержатся адреса ячеек (А1, А2, А3 над которыми нужно выполнить указанную операцию. Номер первого байта команды называется ее адресом. Последовательность из этих команд называется программой в машинных кодах.
Составление программ в современных компьютерах автоматизировано.
Программист пишет программу на специальном языке высокого уровня, т.е.
наиболее удобном для записи алгоритма решения определенного класса задач. С помощью символов клавиатуры вводит ее текст в память компьютера.
Далее происходит перевод алгоритма в команды машины (трансляция) подключение необходимых стандартных программ (компоновка) и лишь после этого выполнение. Заметим, что полученная программа в кодах машины может быть записана на диск и для ее многоразового выполнения уже не требуется этапов трансляции и компоновки.
1.4.Файловая система хранения информации Для размещения программ и всевозможных наборов данных на различных устройствах компьютера и последующей работы с этими данными была разработана концепция файлов.
Под файлом понимается поименованное место на некотором устройстве ПЭВМ (память, диск, принтер, сканер…), отведенное для помещения и (или) чтения некоторой информации. При этом файл может быть пуст, т.е.
место отведено, поименовано, но какая-либо другая информация отсутствует.
Информация, помещенная в файл, приобретает имя этого файла. Поэтому файлом часто называют эту информацию.
За работу с файлами в компьютере отвечают специальные программы, набор которых называется файловой системой, основные функции которой заключаются в том, чтобы предоставить программисту удобные средства для работы с данными на всевозможных носителях.
Имя, которое присваивается файлу, может иметь тип. Имя и тип разделяются точкой. При отсутствии типа, точка необязательна. Например, имена могут быть такими:
Prog.pas, prog.dat, prog.out, prog, A, statya.doc В компьютере обычно хранится несколько тысяч имен файлов. Для их более удобного размещения введены каталоги.
Каталог – это группа файлов на одном носителе. Каталог имеет свое имя. Он может быть вложен внутрь другого каталога. В этом случае он является подкаталогом. Такая вложенность может быть многократной и образуется иерархическая (древовидная ) структура хранения данных.
Для удобства хранения внешним носителям присваиваются имена. Для дисков, например, имена обозначаются одной буквой a:, b:, c:,…. При этом на одном винчестере для удобства размещения файлов может быть организовано несколько логических дисков с разными именами.
Маршрут (путь) файла. При сложной структуре хранения файлов может возникать такая ситуация, когда имеются разные файлы с одинаковым именем, но расположенные в разных каталогах или дисках. Для точной идентификации (указания) файла необходимо кроме имени указать на каком диске, и в какой цепочке подкаталогов он находится. Такая цепочка и называется путем к файлу.
Примеры имен с указанием пути:
C:/sin/doc/lec.doc D:/delphi/prog.pas Для работы с файлами обычно используют специальные программы, наибольшее распространение получили Total Commander, FAR, Проводник.
Вся работа компьютера осуществляется под управлением большого набора специальных программ называемых операционной системой (ОС). С точки зрения пользователя ОС представляет широкий набор системных команд, задавая которые, он может потребовать от ЭВМ выполнения многих полезных для него процедур и действий.
ОС поддерживает целый спектр языков программирования. Файловая система является одной из составных частей ОС.
Часть программ ОС предназначена для управления процессом прохождения задач. Имеется группа программ, так называемого администратора системы, позволяющая следить за работой группы пользователей в рамках системы. В последних системах важное место занимает блок программ, обеспечивающих обмен сообщениями, между пользователями сети, в том числе через интернет.
Удобства, предоставляемые пользователю, существенно зависят от качества ОС, которые по мере совершенствования компьютеров постоянно развиваются. В настоящее время наибольшее распространение на ПЭВМ получили OC WINDOWS 98, WINDOWS 2000, WINDOWS XP, обеспечивающие визуальный доступ (с помощью мыши) пользователя к набору своих программ.
ЛЕКЦИЯ 2. КАК CОСТАВЛЯЮТСЯ И ВЫПОЛНЯЮТСЯ
ПРОГРАММЫ В СИСТЕМЕ DELPHI
2.1. Понятие алгоритма и способы его записи Фундаментальным понятием при программировании является алгоритм. Написанию программы предшествует разработка алгоритма решения задачи.Алгоритм – это последовательность действий, в результате выполнения которых получается решение поставленной задачи.
Алгоритмы можно классифицировать по виду выполняемых действий.
Например, правила ГАИ – это набор алгоритмов описывающих действия водителей и пешеходов, поваренная книга – набор алгоритмов приготовления пищи.
Назовем вычислительными – алгоритмы, последовательность действий которых «умеет» выполнять компьютер.
Программа представляет запись вычислительного алгоритма на языке, который умеет читать компьютер.
Мы уже знаем, что основными действиями, которые умеет выполнять компьютер, являются операции над содержимым ячеек памяти. Составление программы в командах машины крайне сложно и неудобно. И после того, как был накоплен опыт применения ЭВМ для решения различных классов задач, было осознано, что компьютер – это универсальный инструмент, который может выполнять любую формализованную работу по переработке информации. Именно такой задачей является перевод программы с одного формального языка на другой. Возникли первые языки программирования, которые сейчас принято называть языками высокого уровня, удобные для записи тех или иных классов алгоритмов.
В языках программирования вместо номеров ячейкам принято давать имена (идентификаторы), а содержимое ячеек называть переменными или константами, в зависимости от того изменяется оно или нет в процессе работы.
Во всех языках фундаментальным понятием является оператор, который представляет описание определенного набора действий ЭВМ. Программа, написанная на языке программирования, состоит из последовательности операторов.
Одним из распространенных операторов является оператор присваивания ячейке памяти результата арифметических операций над содержимым других ячеек. Последовательность таких операций записывается, например, следующим образом:
Здесь := означает присвоить; a, b, c, f – имена ячеек (переменных); каждый оператор в Паскале заканчивается точкой с запятой.
Во всех языках программирования имеется набор операторов, реализующих следующие основные действия:
В 1970 году появилось сообщение еще об одном языке программирования, названного Pascal, в честь знаменитого французского математика Блеза Паскаля. Автор языка Никлаус Вирт, профессор, директор института информатики Швейцарской высшей политехнической школы. Этот язык создавался для целей начального обучения студентов языкам программирования. К тому времени были в распространении такие известные языки как Бейсик, Фортран, Алгол, СИ. Уже проявились как достоинства, так и недостатки этих языков. Поэтому концепция нового языка оказалась настолько удачной, что он быстро завоевал прочные позиции в мире программирования. Как правило, практически во всех учебных заведениях мира изучение языков программирования начинают с Pascal.
Pascal – язык программирования высокого уровня, позволяющий значительно облегчить подготовку программ. Его синтаксис максимально приближен к обычному математическому языку.
В концепции Паскаля заложены следующие основные понятия:
а) принцип структурирования, который позволяет автоматизировать проверку правильности программ. Грубо говоря, это значит, что возможности языка позволяют записать алгоритм любой сложности без использования меток и операторов GOTO. Оператор GOTO в Pascal оставлен для программистов низкого уровня;
б) принцип надежности. В отличие от всех других языков, в Pascal все переменные, которые используются, должны быть описаны в заголовке программы, т.е. указаны их типы, границы изменения;
в) простота реализации транслятора позволяет его адаптацию практически на любом типе компьютера и высокую скорость компиляции.
г) развитая структура данных делает этот язык универсальным языком многоцелевого назначения, позволяющим реализовать как обычные программы, так и современные технологии объектно-ориентированного программирования.
В процессе совершенствования вычислительной техники Pascal прошел ряд этапов в своем развитии. Начиная с простейшего языка обучения, имелось очень большое число версий наиболее известные из которых: Microsoft Pascal Compiler, Quick Pascal, Pascal-2, Professional Pascal, USCD Pascal, одна из самых популярных версий - Pascal-5.5, Pascal-7, Object Pascal.
В 1996 году появилась современная высокопроизводительная система визуального программирования Delphi на основе языка Object Pascal. По своим возможностям она не уступает системе VisualС++ (которая появилась немного позже Delphi), а по удобству языка и простоте обучения Delphi значительно привлекательнее.
Система Delphi реализует технологию объектно-ориентированного визуального программирования (ООП). В ООП главным элементом является объект. Объектно-ориентированная программа – это совокупность объектов и способов их взаимодействия. Пользователь программы является главным (управляющим) объектом. Обмен между объектами происходит посредством сообщений. Пользователь посылает свои сообщения посредством нажатия кнопок на панели программы. Когда сообщение поступило некоторому объекту (произошло определенное событие), он начинает выполнять свои определенные действия и сообщает результаты пользователю визуально через окна на панели программы.
Объект представляет собой объединение под одним именем (имя объекта) данных и методов работы с ними. Методы чтения и записи данных называются свойствами. Вызов метода производится указанием имени объекта и через точку имени метода, например, Memo.Clear.
2.3. Как составляется программа в системе Delphi Среда разработки программ Delphi визуально реализуется в виде нескольких одновременно раскрытых на экране монитора окон. Количество, расположение, размер и вид окон может меняться программистом в зависимости от его текущих нужд, что значительно повышает производительность работы. При запуске Delphi вы можете увидеть на экране картинку, подобную представленной на рис. 2.1.
1- главное окно; 2 – основное меню, 3 – пиктограммы основного меню, 4 - окно инспектора объектов; 5 – окно текста программы, Главное окно всегда присутствует на экране и предназначено для управления процессом создания программы. Основное меню содержит все необходимые средства для управления проектом. Пиктограммы облегчают доступ к наиболее часто применяемым командам основного меню. Через меню компонентов осуществляется доступ к набору стандартных сервисных программ среды Delphi, которые описывают некоторый визуальный элемент (компонент), помещаемый программистом в окно формы. Каждый компонент имеет определенный набор свойств (параметров), которые программист может задавать. Например, цвет, заголовок окна, надпись на кнопке, размер и тип шрифта и др.
Окно инспектора объектов (вызывается c помощью клавиши F11) предназначено для изменения свойств выбранных компонентов и состоит из двух страниц. Страница Properties (Свойства) предназначена для изменения необходимых свойств компонента. Страница Events (События) – для определения реакции компонента на то или иное событие (например, нажатие определенной клавиши или щелчок «мышью» по кнопке).
Окно формы представляет собой проект рабочей панели Windows-окна программы. В это окно в процессе написания программы помещаются необходимые компоненты. Причем при выполнении программы помещенные компоненты будут иметь тот же вид, что и на этапе проектирования.
Окно текста программы предназначено для просмотра, написания и редактирования текста программы. В системе Delphi используется язык программирования Object Pascal. При первоначальной загрузке в окне текста программы находится исходный текст программного модуля (Unit), содержащий минимальный набор операторов для нормального функционирования пустой формы в качестве Windows-окна. При помещении некоторого компонента в окно формы, текст программы автоматически дополняется описанием необходимых для его работы библиотек стандартных программ (раздел uses) и типов переменных (раздел type).
Переключение между окном формы и окном текста программы осуществляется с помощью клавиши F12.
Программа в Delphi состоит из файла проекта (файл с расширением.dpr), одного или нескольких файлов исходного текста (с расширением.pas), файлов с описанием окон формы (с расширением.dfm).
В файле проекта находится информация о модулях, составляющих данный проект. Файл проекта автоматически создается и редактируется средой Delphi и не предназначен для редактирования.
Файл исходного текста – программный модуль (Unit) предназначен для размещения текстов программ. В этом файле программист размещает текст программы, написанный на языке Pascal. В разделе объявлений описываются типы, переменные, заголовки процедур и функций, которые могут быть использованы другими модулями, через операторы подключения библиотек (Uses). В разделе реализации располагаются тела процедур и функций, описанных в разделе объявлений, а также типы переменных, процедуры и функции, которые будут функционировать только в пределах данного модуля. Раздел инициализации используется редко и его можно пропустить.
Mодуль имеет следующую структуру:
Программа в среде Delphi составляется как описание алгоритмов, которые необходимо выполнить, если возникает определённое событие, связанное с формой (например щелчок «мышки»—событие, называемое OnClick, создание объекта—OnCreate). Для каждого обрабатываемого в форме события с помощью страницы Events инспектора объектов (или двойного щелчка мыши), в разделе реализации организуется процедура (Procedure), между ключевыми словами begin и end которой программист записывает на языке Object Pascal требуемый алгоритм.
Детальное описание действий при создании Windows-окна программы, написании и отладке текстов процедур, а также её выполнении содержится в лабораторной работе №1.
При компиляции программы Delphi создает файл с расширением.dcu, содержащий в себе результат перевода в машинные коды содержимого файлов с расширением.pas и.dfm. Компоновщик преобразует файлы с расширением.dcu в единый загружаемый файл с расширением.exe. В файлах, имеющих расширение.~df,.~dp,.~pa хранятся резервные копии файлов с образом формы, проекта, и исходного текста соответственно.
2.4. Наша первая программа реализует линейный алгоритм Наиболее часто в практике программирования требуется организовать расчет некоторого арифметического выражения при различных исходных данных. Например, такого Разработка алгоритма обычно начинается с написания схемы. Продумывается оптимальная стратегия вычислений, при которой, например, отсутствуют повторения. При написании алгоритма рекомендуется также переменным присваивать по возможности те же имена, которые фигурируют в заданном арифметическом выражении. Для того, чтобы не было «длинных»
операторов исходное выражение полезно разбить на ряд более простых. В нашем случае предлагается схема вычислений, представленная на рис. 2.2.
Она содержит ввод и вывод исходных данных, линейный вычислительный процесс, вывод полученного результата. Заметим, что выражение x 2 + m вычисляется только один раз. Введя переменные a,b,c мы разбили сложное выражение на ряд простых.
При разработке программы, реализующей этот алгоритм, кроме уже известного нам оператора присваивания необходимо знать, как записать операторы ввода и вывода данных. В языке Pascal эти операторы выглядят таким образом:
Read(Lr,x,m);
Writeln(Lw,’x=’,x:6:2,’ m=’,m:2);
Writeln(Lw,’z=’,z:8:3);
начало Lw - логическое имя файла, на который помещается результат. Набор символов, заключенных в апострофы (например, ’x=’), c=xm+1 последнего оператора будет z= -25.400. Заметим, что при такой организации ввода, File.
В Delphi чаще всего ввод (вывод) небольшого количества данных производят из так называемых окон однострочных редакторов ( компонент Edit) или табличных строчных редакторов ( компонент StringGrid).
Вывод большого числа данных обычно осуществляется в окно многострочного редактора (компонент Memo). Окна этих редакторов и пояснения к ним размещаются на Window-окно программы по усмотрению программиста.
В окна строчных редакторов во время активности программы может помещаться любой набор символов, в частности запись чисел, которые необходимо ввести. Каждому окну редакторов Edit и StringGrid, помещенному на форму в программе в разделе Type вводится ячейка памяти типа String, в которой содержится строка символов, отражаемая в окне.
Для того, чтобы, например, в окне редактора Edit1 было помещено число 28.64 в программе достаточно написать Edit1.Text:=’28,64’. И обратно, если во время активности программы в окно TEdit1 с помощью клавиатуры, будет помещено число 3,14, то оно окажется в ячейке Edit1.Text (вместо предыдущего 28.64).
Для реализации нашей программы на форму поместим два окна Edit (под x), Edit2 (под m). Ввиду того, что ввод данных происходит в виде строки, а переменные x, m представляют числа необходимо воспользоваться функциями перевода строковой записи числа в действительное или целое его представление:
x:=StrToFloat(Edit1.Text);
m:=StrToInt(Edit2.Text);
Для вывода результатов поместим на форму окно многострочного редактора Memo1. Окно многострочного редактора (компонент Memo) в данном случае предназначено для вывода и представляет собой отображение в окне последовательности строк. Для того, чтобы отобразить новую строку, ее необходимо добавить в окно с помощью оператора Memo1.Lines.Add(’строка’). Если нужно вывести содержимое действительных или целых переменных их необходимо предварительно преобразовать в строковое представление. Для этого используются функции FloatToStrF(х,fffixed,6,2); // 6 позиций под все число, 2 десятичных знака IntToStr(m); // все цифры числа m Теперь мы готовы написать нашу первую программу. Для этого поместим на форму кнопку, описываемую компонентом Button1 и сделаем на ней двойной щелчок «мышью». После этого в открывшемся окне текстов наберем следующую программу:
Procedure TForm1.Button1Click(Sender:Tobject);
// Этот заголовок среда Delphi вставляет автоматически после //двойного щелчка «мышью» по кнопке Button Var х,z,a,b,c:extended; // описание типов х:=StrToFloat(Edit1.Text);
m:=StrToInt(Edit2.Text);
Memo1.Lines.Add(’х=’+FloatTostrF(x,fffixed,6,2) +’ m=’+IntTostr(m));
a:=sqrt(sqr(x)+m*m);
b:=sqr(sin(x)/cos(x));
c:=exp((m+1)*ln(x));
z:=b/a+c*a;
Memo1.Lines.Add(’полученный результат’);
Memo1.Lines.Add(’z=’+FloatTostrF(z,fffixed,8,3));
Заметим, что в строке после сдвоенного // пишется произвольный комментарий, который служит для облегчения понимания программы.
После набора программы ее необходимо записать в свою папку. Для создания новой папки можно воспользоваться одной из программ для работы с файлами. Например, войдем в программу Total Commander, выберем рабочий диск, нажмем клавишу F7 и в появившемся окне наберем имя папки «Lab1_5» (Лаб.№1, вариант 5). В меню «File» Delphi выберем «Save Project As». После открытия своей папки нажмем «Save Project As» и сохраним с указанием имени предлагаемые файлы Project1 и Unit1. После сохранения сделаем запуск программы, для чего в меню «Run» выберем команду «Run». Если все сделано верно, после компиляции на экране высветится Window - окно вашей первой программы, готовой к выполнению расчетов. В окнах Edit1, Edit2 наберите исходные данные (х, m), после чего щелкните мышью на кнопке Button1. В окне Memo1 появятся результаты расчета вашей программы.
При обнаружении ошибок, в процессе выполнения, переведите программу из режима выполнения Running в режим редактирования, для чего выберите «Run Reset» в меню «Run». Исправьте ошибки, запишите исправленный вариант, нажав «Save» в меню «File» и запустите программу снова.
Для получения распечатки программы в меню «File» выберите «Print», установите запрaшиваемые параметры и нажмите «OK».
ЛЕКЦИЯ 3. БАЗОВЫЕ ЭЛЕМЕНТЫ ЯЗЫКА ПАСКАЛЬ
Любой язык начинается с алфавита. Алфавит Object Pascal оперирует следующим набором символов:1) прописные и строчные буквы латинского алфавита 2) десятичные арабские цифры от 0 до 9;
3) _ - символ «подчеркивание», 4) специальные символы Комбинации специальных символов могут образовывать составные символы:
(..) альтернатива квадратных скобок (* *) альтернатива фигурных скобок 5) ключевые (зарезервированные) слова. Например: Begin, End;
6) стандартные идентификаторы. Например: Sin, Cos;
7) идентификаторы пользователя.
Величины, с которыми должна работать программа принято называть данными. Все данные при работе программы размещаются в различные ячейки памяти, им присваиваются оригинальные имена (идентификаторы) и указываются их типы.
Идентификаторы образуются из латинских букв, символа _ и арабских цифр и могут иметь произвольную длину, но значимыми будут только первые 63 символа. Первым символом должна быть буква или символ _. Пробелы, точки и другие специальные символы не могут входить в имя.
Данные могут быть константами и переменными.
Константы - это те данные, значения которых известны заранее и в процессе выполнения программы не изменяются.
В качестве констант в Object Pascal могут использоваться целые, вещественные и шестнадцатеричные числа, логические константы, символы, строки символов, конструкторы множеств и признак неопределенного указателя nil.
Целые константы - это целые числа со знаком или без в диапазоне от до 263-1.
Можно использовать целую константу в шестнадцатеричном виде.
Шестнадцатеричное число состоит из шестнадцатеричных цифр ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F ), которым предшествует знак доллара $ ( код символа 36 ) Вещественные константы могут быть представлены в двух видах: с фиксированной и плавающей точкой.
Константа с фиксированной точкой - это число, содержащее точку, разделяющую целую и дробную часть (наличие целой и дробной части обязательно).
Константа с плавающей точкой - это число, представленное с десятичным порядком: mEp (без пробелов).
Здесь m - мантисса (как целые, так и вещественные числа с фиксированной точкой), E - признак записи числа с десятичным порядком, p - порядок числа (только целые числа).
-7.78Е-3; -0.785Е02; 4.9Е Логические константы могут принимать только одно из двух значений:
True (истина) и False (ложь).
Символьная константа - это любой символ, заключенный в апострофы.
Допускается использование записи символа путем указания его внутреннего кода, которому предшествует символ #.
Строковые константы - это последовательность символов, заключенная в апострофы.
Конструктор множества – это список элементов множества, обрамленный квадратными скобками.
Константы могут иметь свои собственные имена. Этот вариант предпочтительней при многократном использовании константы.
Форма описания констант:
Const Min = 1; // Описание констант Переменная - это именованный объект, который в процессе выполнения программы может принимать различные значения. Форма описания переменных:
Тип переменных определяет, какие значения они могут иметь, какая структура ячеек для их размещения используется, и какие операции над ними можно выполнять. В Object Pascal имеется развитая система типов данных.
Их можно разделить на две группы: скалярные (простые) и структурированные (составные).
К скалярному типу относятся данные, представляемые одним значением (числом, символом) и размещаемые в одной ячейке из нескольких байтов.
Структурированные типы определяются пользователем через скалярные и описанные ранее структурированные с помощью оператора Type следующим образом В языке Object Pascal имеется 7 скалярных типов (целые, вещественные, логические, символьные, перечисляемые, интервальные, дата-время) и 10 основных структурированных типов (строки, массивы, множества, записи, файлы, указатели, процедуры, объекты, варианты, классы). В Pascal предусмотрено создания программистом новых типов данных, поэтому общее количество типов, использующихся в программе, может быть сколь угодно большим. По мере изучения языка мы будем детально знакомиться с различными типами.
Характеристики двух основных скалярных типов представлены в следующих таблицах.
Для экономии памяти следует пользоваться более «короткими» типами, a для повышения точности более «длинными». Следует помнить, что арифметический сопроцессор всегда обрабатывает числа в формате Extended, а три других вещественных типа (Double, Real, Single) получаются простым усечением результата до нужных размеров и применяются, как правило, для экономии памяти. Следует так же учесть что тип Real оптимизирован для работы без сопроцессоров, однако его использование на ПК с сопроцессором приводит к дополнительным затратам (в 2-5 раз) времени на преобразование формата. Если ваш компьютер оснащен сопроцессором, то не рекомендуется использовать тип Real.
Из логических типов наиболее часто используется тип Boolean (1 байт), другие логические типы ByteBool (1 байт), Bool (2 байта), WordBool (2 байта) и LongBool (4 байта) введены для совместимости с Windows.
К ним относятся переменные перечисляемого и интервального типов.
Переменная типа перечисление задается перечислением значений, которые она может принимать.
Форма описания этих переменных:
Type Sezon = (Zima, Vesna, Leto, Osen);
Var S1, S2 : (Zima, Vesna, Leto, Osen);
Здесь S1,S2 - переменные типа перечисление, которые могут принимать любое из заданных значений.
Следует отметить, что описание типа перечисляемой переменной одновременно вводит упорядочение ее значений. Так, для данного примера Zima < Vesna < Leto < Osen (в операциях сравнения).
Для переменных интервального типа указывается некоторое подмножество значений, которые они могут принимать.
Форма описания этих переменных:
Здесь, - соответственно константы, определяющие левую и правую границы значений, которые может принимать интервальная переменная. Значение первой константы должно быть обязательно меньше значения второй. Эти константы могут быть целого, символьного или перечисляемого типов.
В этом примере переменные D1 и D2 имеют тип Dni и могут принимать любые значения из диапазона 1..31. Выход из диапазона вызывает программное прерывание.
Можно определять интервальный тип и более универсальным способом, задав границы диапазона не значениями констант, а их именами.
Const Min=1; Max=31;
Type Dni = Min..Max;
3.2. Операции над переменными основных скалярных типов Во-первых, следует всегда помнить, что в операторе присваивания результат выражения (арифметического, логического) должен соответствовать типу переменной а, т.е. здесь нельзя смешивать типы. Исключение составляет возможность присваивать переменной вещественного типа результат целого типа.
Арифметические выражения строятся из числовых констант, переменных, стандартных функций и операций над ними. Для обозначения операций используются символы: + сложение, - вычитание, * умножение, и / деление.
В арифметическом выражении принят следующий приоритет операций:
1) вычисление значений стандартных функций;
2) умножение и деление;
3) сложение и вычитание.
Порядок выполнения операций изменяется с помощью скобок.
Вызов Тип аргумента Тип резуль- Назначение функции Exp(x) В логических выражениях операции выполняются слева направо с соблюдением следующего приоритета:
2) *, /, Div, Mod, And, Shr, Shl ;
К переменным символьного типа, определенным, например, как:
кроме операции присваивания, применима функция Ord(сh), которая возвращает порядковый номер символа в кодовой таблице. Обратная к ней функция Chr() возвращает символ по его порядковому номеру. Для кодировки в Windows используется кодировка ANSI (American National Standart Institute). Функция Pred(сh) возвращает символ, предшествующий символу ch в кодовой таблице. Функция Succ(ch) возвращает символ, следующий за символом ch в кодовой таблице.
В виду такой упорядоченности над символами допустимы логические операции отношения, например: ch > ’a’, ‘ф’ ch, ‘!’ A[j+1] then Задача 3. Посчитать количество цифр в строке.
Function Kol(s:string): byte;
var i:word;
begin result:=0;
for i:=1 to length(s) do if s[i] in [‘0’..’9’] then inc(result);
end;
Задача 4. Подсчитать количество различных символов в строке.
Function Kol(S:string):Word;
m:=0; a:=[];
for i:=1 to Length(S) do Result:=m;
ЛЕКЦИЯ 12. ПРОГРАММИРОВАНИЕ С
ИСПОЛЬЗОВАНИЕМ ЗАПИСЕЙ
Удобство использования структурированных типов, когда под одним именем объединяется целый набор данных, было продемонстрировано ранее на примере массивов, строк и множеств. Указанные типы объединяют под одним именем одинаковые данные. В отличие от них записи позволяют объединить под одним именем разнотипные данные, что открывает более широкие возможности для составления программ.Запись – это структура данных, в которой под одним именем объединены переменные, в общем случае разного типа, которые называются полями.
Запись в Delphi описывается в общем случае, следующим образом:
Var Z1,Z2:Tzap;
Здесь Z1, Z2 – записи, a, b,.., p, q – поля этих записей. Все поля в одной записи должны иметь различные имена. Записи в общем случае имеют фиксированную и вариантную части. Вариантная часть открывается предложением case of, и всегда последняя. В ней указывается несколько вариантов полей, каждый из которых заключен в скобки, перед которыми стоит значение константы, имеющей тип, указанный в предложении case. Всем вариантам отводится одна и та же область памяти, объем которой равен максимальному из объемов вариантов полей. Возможны записи, имеющие только фиксированную часть (отсутствует вариантная часть) или имеющие только вариантную часть (отсутствует фиксированная часть).
Запись - константа вводится следующим образом:
Type Point=Record x,y:real; end;
Const w:Point=(x:1.5; y:8.4);
Для однотипных записей допускается оператор присваивания:
при выполнении которого всем полям записи Z1 присваиваются значения соответствующих полей записи Z2.
К каждому полю записи можно получить доступ через составное имя, представляющее собой разделенные точкой имя записи и имя поля (составное имя), например: если Typ1=real:
Z1.a:=25.86; Z2.b:=Z1.a;
Если поле, в свою очередь, имеет тип записи (вложенность записей), тогда для конкретизации потребуется составное имя с двумя точками. Например, если Typ2 определяется как то, полям re и im можно присвоить некоторое значение следующим образом:
Чтобы упростить доступ к полям, используется оператор присоединения Например, присвоить значения полям re и im можно и так:
With Z1.e do begin re:=5.1; im:=0.8; end;
То обстоятельство, что все варианты записи помещены в одном месте памяти позволяет использовать эффект наложения друг на друга переменных различных типов.
В нижеприведенном примере происходит наложение одномерного массива на двумерный:
Type zap=record false:(b:array[1..2,1..2] of integer);
Writeln(z.b[2,1]); // Будет выведено число 3.
12.3. Использование записей для работы с комплексными числами Комплексные числа представляют собой расширенное понятие действительных чисел. Исторически они возникли при решении алгебраических уравнений. Например, решение уравнения x2 – x +1=0:
приводит к выражению вида u+ 1 *v. Оказывается, к аналогичным выражениям приводит решение многих задач.
Обозначив 1 = i, получим i2 = – 1 < 0. Но мы знаем, что квадрат обычного числа >0. Выход из этой ситуации нашли, введя понятие «мнимая единица» и обозначив ее i = 1. В результате выражение а =u+ 1 *v принимает вид а = u+iv = are+iaim и называется комплексным числом (числом, имеющим действительную (are) и мнимую (aim) части). Точка сверху отличает его от действительного.
Геометрическая интерпретация комплексного числа - точка с координатами (are, aim) на комплексной плоскости позволяет также однозначно определить комплексное число через модуль (расстояние от начала координат до точки) и фазу комплексного числа (угол между радиус – вектором точки и положительным направлением оси абцисс). Таким образом, комплексное число можно записать двумя способами:
= are+iaim=aej=a(cos+isin), a= аre + aim, =arctg(aim / are)+2k, are = a*cos, aim = a*sin.
Рассмотрим два числа и :
± =(аre±cre)+i(aim±cim) * =(are+iaim)(cre+icim)=(arecre–aimcim)+i(arecim+aimcre) / =((arecre+aimcim)+i(aimcre – arecim))/(c2re+ c2im) В языке Pascal отсутствуют специальные встроенные операции с комплексными числами. Однако этот недостаток легко можно компенсировать, если дополнить свою библиотеку специальным модулем (Unit Cmplx) в котором все операции под комплексными числами и функциями комплексной переменной оформлены в виде набора функций и процедур. Начальный фрагмент такого модуля приведен ниже. При желании, его легко дополнить всеми необходимыми для решения задач функциями. В этом модуле тип комплексных чисел – complex вводится, как запись, имеющая два поля с именами re и im. Первое поле трактуется как действительная часть комплексного числа, второе - как мнимая часть.
Unit Cmplx;
Type Complex=record re,im:extended; end;
function Addc(x,y:Complex):Complex;
function Mulc(x,y:Complex):Complex;
function Divc(x,y:Complex):Complex;
function Addc; // x+y Addc.re:=x.re+y.re;
Addc.im:=x.im+y.im;
function Mulc; // x*y Mulc.re:=x.rey.re-x.imy.im;
Mulc.im:=x.rey.im+x.imy.re;
z:=sgr(y.re)+sgr(y.im);
Divc.re:=(x.rey.re+x.imy.im)/z;
Divc.im:=(x.imy.re-x.rey.im)/z;
Предположим, что требуется ввести два комплексных числа а, b и рассчитать u=(a+b)/(ab).
Фрагмент вычислений с комплексными числами при использовании этого модуля выглядит следующим образом:
Var a,b,u:Complex;
u:=Divc(Addc(a,b),Mulc(a,b));
ЛЕКЦИЯ 13. ИСПОЛЬЗОВАНИЕ ФАЙЛОВ
В программировании слово файл встречается очень часто. Вы с этим понятием познакомились уже на первой лекции и знаете, что файлы предназначены для размещения данных на внешних носителях (обычно магнитных дисках), и последующей работы с этими размещенными данными. В языке Pascal для организации и последующей работы с файлами предусмотрен специальный файловый тип переменных. Операциями над переменными файлового типа соответствуют определенные действия над внешними носителями (дисками, магнитными лентами, принтерами).Переменная файлового типа, или коротко файл, в языке Pascal представляет последовательность однотипных компонент, соответствующих последовательности записей на внешнем носителе. В отличие от массива, количество компонент заранее не оговаривается, и компоненты файла не имеют индексов. Файловые переменные в Delphi вводятся следующим образом:
Объясняя принципы работы с файлами, можно для наглядности считать, что каждый файл записан на некоторой магнитной ленте, как это показано на следующем рисунке:
n – количество записанных компонент.
Указатель определяет положение магнитной головки магнитофона, с помощью которой осуществляется покомпонентная запись или чтение информации. В начале файла записана информация о файле BOF (Begin of File), его имя, тип, длина и т.д., в конце файла помещается признак конца файла EOF (End of File). Если файл пуст, то BOF и EOF совмещены, а указатель установлен в нуль. Если файл не пуст, то указатель совмещен либо с началом некоторой компоненты и его значение равно номеру этой компоненты (нумерация начинается с нуля), либо указатель совмещен с признаком конца и его значение равно количеству компонент.
Пусть f – имя типизированного файла, а переменные x, y, z имеют тот же тип, что и его компоненты.
Начинается работа над файлами с процедур открытия файла:
AssignFile(f, :String);
Reset(f); или Rewrite(f);
Процедура AssignFile() устанавливает соответствие между файловой переменной f и на внешнем носителе. Процедуры Reset(f) и Rewrite(f) инициируют (подготавливают) файл для работы. При этом, если файл на внешнем носителе отсутствует, то следует использовать оператор Rewrite(f), который создает новый файл с именем. Если требуется работать с уже существующим файлом, то необходимо использовать оператор Reset(f). После выполнения процедур открытия файла указатель всегда установлен в начало файла (на компонент с номером 0). Если открытие производится оператором Rewrite(f), то признак конца файла совмещен с началом (т.е. файл пуст). Если перед этим в файле имелась некоторая информация, то она стирается. Запись значений переменных в файл производится покомпонентно с помощью оператора Write(f,x);
Write(f,y,z);
После записи каждой переменной значения указатель увеличивается на единицу, что соответствует его перемещению к следующему компоненту файла. Если перед записью указатель находился напротив признака конца файла, то при записи каждой переменной признак конца смещается на длину этой записи и количество компонентов в файле возрастает на единицу.
Количество компонентов, записанных в файле, можно определить с помощью функции FileSize(f).
Чтение значений переменных из компонентов файла производится с помощью оператора Read(f,x);
Read(f,y,z);
При чтении каждой переменной указатель увеличивается на единицу.
Если производится попытка чтения при указателе, установленном на конец файла, то происходит останов программы по ошибке чтения.
Распознать ситуацию, когда указатель установлен на конец файла, можно с помощью функции Eof(f), возвращающей значение True, если достигнут конец файла, и False, в противном случае.
Организовать чтение с проверкой этого условия можно, например, следующим образом:
if not Eof(f) then Read(f,x);
При необходимости чтения или записи заданного компонента файла нужно предварительно указатель установить на номер этого компонента. Это делается с помощью процедуры Seek(f,).
Например, при выполнении следующей группы операторов Seek(f,2);
Read(f,x);
Write(f,y);
Переменная x будет прочитана из компонента с номером 2 (третьего), а переменная y запишется в компонент с номером 3 (четвертый).
Текущее положение указателя можно узнать с помощью функции FilePos(f).
После окончания работы с файлом его следует обязательно закрыть с помощью процедуры CloseFile(f).
Если этот оператор отсутствует, то из-за специфики обмена данными с файлом, часть информации, помещенной в файл, может быть утеряна.
Для удобства хранения текстовой информации, т.е. представленной последовательностью строк символов, в языке Паскаль введены файловые переменные текстового типа (см. выше Lw, Lr) или просто текстовые файлы.
Текстовые файлы можно представлять эквивалентным типизированным файлом, компонентами которого являются символы. Однако в текстовом файле последовательность символов разбита на строки различной длины, т.е. в конце каждой строки ставится специальный признак EOLN (End of LiNe), а в конце файла признак конца файла EOF. При просмотре такого файла текстовым редактором на экране возникает естественная «книжная» страница текста, которую затем можно отредактировать. При работе с текстовым файлом следует помнить, что в отличие от типизированного, после открытия файла процедурой Reset (Lr) разрешается только чтение Read(Lr,a,b);
Readln(Lr,c);
Readln(Lr);
После открытия файла процедурой Rewrite (Lw) разрешается только запись в него, при этом предыдущий файл стирается. Для сохранения предыдущей информации в текстовом файле его следует открывать процедурой Append (Lw). В этом случае указатель устанавливается на конец файла и последующие записи добавляют новые строки в конец файла.
Для записи используются операторы:
Write(Lw,a,b);
Writeln(Lw,c:8,’переменная d=’,d:10:2);
Для текстовых файлов введены модификации операторов ввода/вывода Readln, Writeln, которые осуществляют переход на следующую строку после чтения или записи указанных в операторе переменных, при этом оператор Writeln записывает символ конца строки EOLN.
Заметим, что тип переменных a, b, c здесь может быть любого скалярного типа. При выводе широко используются форматирование и автоматически происходит преобразование чисел в их строковые представления. При вводе, строковые представления чисел, разделенные пробелами автоматически преобразуются в числовые представления в соответствии с типом переменных.
Описываются: var f:File;
Тип компонентов этих файлов заранее не оговорен и считается последовательностью байт. Поэтому их можно использовать для обработки файлов любого типа, а так же для организации высокоскоростного обмена между дисками и памятью.
AssignFile(var F; FileName: string) - связывает файловую переменную F и файл с именем FileName.
Reset(var F[: File; RecSize: word]) - открывает существующий файл. При открытии нетипизированного файла RecSize задает размер элемента файла.
Rewrite(var F[: File; RecSize: word]) - создает и открывает новый файл.
Append(var F: TextFile) - открывает текстовой файл для дописывания текста в конец файла.
Read(F,v1[,v2,…vn]) - чтение значений переменных начиная с текущей позиции для типизированных файлов и строк для текстовых.
Write(F,v1[,v2,…vn]) - запись значений переменных начиная с текущей позиции для типизированных файлов и строк для текстовых.
CloseFile(F) - закрывает ранее открытый файл.
Rename(var F; NewName: string) - переименовывает неоткрытый файл любого типа.
Erase(var F) - удаляет неоткрытый файл любого типа.
Seek(var F; NumRec: Longint) - для нетекстового файла устанавливает указатель на элемент с номером NumRec.
Truncate(var F) - урезает файл, начиная с текущей позиции.
IoResult: integer - код результата последней операции вводавывода.
FilePos(var F): longint - для нетекстовых файлов возвращает номер текущей позиции. Отсчет ведется от нуля.
FileSize(var F): longint - для нетекстовых файлов возвращает количество компонентов в файле.
Eoln(var F: TextFile): boolean - возвращает True, если достигнут конец строки.
Eof(var F) ): boolean - возвращает True, если достигнут конец файла.
SeekEoln(var F: TextFile): boolean – возвращает True, если пройден последний значимый символ в строке или файле, отличный от пробела или знака табуляции.
SeekEof(var F: TextFile): boolean - то же, что и SeekEoln, но для всего файла.
13.4. Компоненты OpenDialog и SaveDialog Для удобства работы с файлами в Delphi имеются два специальных компонента, предназначенных для выбора требуемого файла на диске через удобное окно просмотра. Результатом этого выбора является имя и маршрут к файлу, помещаемому в переменную строкового типа OpenDialog1.FileName или SaveDialog1.FileName которые затем используются в процедуре AssignFile().
Компоненты OpenDialog и SaveDialog находятся на странице DIALOGS.
Все компоненты этой страницы являются невизуальными, т.е. не видны в момент работы программы. Поэтому их можно разместить в любом удобном месте формы. Оба рассматриваемых компонента имеют идентичные свойства и отличаются только внешним видом. После вызова компонента появляется диалоговое окно, с помощью которого выбирается имя программы и путь к ней. В случае успешного завершения диалога имя выбранного файла и маршрут поиска содержaтся в свойстве FileName. Для фильтрации файлов, отображаемых в окне просмотра, используется свойство Filter, а для задания расширения файла, в случае, если оно не задано пользователем, – свойство DefaultExt. Для того, чтобы файл автоматически записывался, например, с расширением dat, в свойстве DefaultExt компонета SaveDialog запишем требуемое расширение –.dat (для текстового файла –.txt). Если необходимо изменить заголовок диалогового окна, используется свойство Title.
Пример: Создать файл, содержащий список книг. Предусмотреть возможность сортировки книг по алфавиту по фамилии автора и вывод, как всего списка, так и списка книг заданного автора.
Вид формы после нажатия кнопки «Создать».
Вид формы после задания имени файла.
Вид формы после нажатия кнопки «Закончить».
Вид формы после нажатия кнопки «Просмотреть».
Вид формы после нажатия кнопки «Выбрать», задании фамилии интересующего автора и нажатия кнопки «Вывести».
uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,StdCtrls, ExtCtrls, Buttons;
type TForm1 = class(TForm) Button1: TButton;
Button2: TButton;
BitBtn1: TBitBtn;
Panel1: TPanel;
Edit1: TEdit;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
Button3: TButton;
Button4: TButton;
OpenDialog1: TOpenDialog;
SaveDialog1: TSaveDialog;
Panel2: TPanel;
Button5: TButton;
Button6: TButton;
Button7: TButton;
Button8: TButton;
Panel3: TPanel;
Button9: TButton;
Button10: TButton;
Edit3: TEdit;
Label3: TLabel;
Panel4: TPanel;
Label4: TLabel;
Label5: TLabel;
Memo1: TMemo;
Memo2: TMemo;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
procedure Button5Click(Sender: TObject);
procedure Button6Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button8Click(Sender: TObject);
procedure Button7Click(Sender: TObject);
procedure Button9Click(Sender: TObject);
procedure Button10Click(Sender: TObject);
private { Private declarations } public { Public declarations } end;
type book=record avt:string[20];
naz:string[30];
var Form1: TForm1;
f:file of book;
w:book;
a:array[1..100] of book;
fname:string;
n,i,k:integer;
implementation {$R *.DFM} procedure TForm1.FormCreate(Sender: TObject);
begin panel1.Hide; panel2.Hide;
panel3.Hide; panel4.Hide;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin // Создать SaveDialog1.Title:='Создать файл';
if SaveDialog1.Execute then fname:=SaveDialog1.FileName;
AssignFile(f,fname);
Rewrite(f);
Panel1.Show;
Button1.Hide; Button2.Hide; BitBtn1.Hide;
end;
procedure TForm1.Button3Click(Sender: TObject);
w.avt:=edit1.text;
w.naz:=edit2.text;
write(f,w);
edit1.clear; edit2.clear;
end;
procedure TForm1.Button4Click(Sender: TObject);
CloseFile(f);
panel1.Hide;
panel2.show;
BitBtn1.show;
end;
procedure TForm1.Button5Click(Sender: TObject);
begin // Сортировать reset(f); n:=0;
while not eof(f) do read(f,a[n]);
closeFile(f);
for i:=1 to n-1 do if a[k].avt > a[k+1].avt then begin w:=a[k]; a[k]:=a[k+1]; a[k+1]:=w; end;
rewrite(f);
for i:=1 to n do write(f,a[i]);
closeFile(f);
end;
procedure TForm1.Button6Click(Sender: TObject);
begin // Просмотреть panel4.Show; memo1.clear; memo2.clear;
reset(f);
while not eof(f) do read(f,w);
memo1.lines.add(w.avt);
memo2.lines.add(w.naz);
closeFile(f);
end;
procedure TForm1.Button2Click(Sender: TObject);
begin // Открыть OpenDialog1.Title:='Открыть файл';
if OpenDialog1.Execute then fname:=OpenDialog1.FileName;
AssignFile(f,fname);
Panel2.Show;
Button1.Hide; Button2.Hide; BitBtn1.Hide;
end;
procedure TForm1.Button8Click(Sender: TObject);
begin // Выход из panel Button1.show; Button2.show; BitBtn1.show;
panel2.Hide;
end;
procedure TForm1.Button7Click(Sender: TObject);
begin // Выбрать panel2.Hide; panel3.Show; bitbtn1.Hide;
memo1.clear; memo2.clear;
end;
procedure TForm1.Button9Click(Sender: TObject);
memo1.clear; memo2.clear;
reset(f);
while not eof(f) do read(f,w);
if w.avt=edit3.text then memo1.lines.add(w.avt);
memo2.lines.add(w.naz);
closeFile(f);
end;
procedure TForm1.Button10Click(Sender: TObject);
begin // Выход из panel panel3.Hide; panel4.Hide;
Button1.show; Button2.show; BitBtn1.show;
end;
end.
ЛЕКЦИЯ 14. ПРОГРАММИРОВАНИЕ С ОТОБРАЖЕНИЕМ
ГРАФИЧЕСКОЙ ИНФОРМАЦИИ
Экран дисплея устроен таким образом, что любое изображение формируется из набора светящихся точек, получивших название пиксель.Этот процесс отображения осуществляется с помощью специальной, довольно сложной микросхемы, называемой графическим адаптером. Современные компьютеры комплектуются цветным графическим адаптером.
Работа графического адаптера осуществляется под управлением специальной программы - драйвера. Адаптер содержит порты ввода-вывода информации, оперативную память, в которой помещается таблица, содержащая информацию о каждом светящемся на экране пикселе (его координате, цвете, яркости). Левый верхний угол экрана имеет нулевые координаты пикселя. Разрешающая возможность графического адаптера определяется размерами одного пикселя (обычно 800х600), но может быть и больше. В результате рисование осуществляется по клеткам. Такое поле из клеточек, называется канва или холст. В Windows пользователю для рисования предоставляется окно, в котором он осуществляет рисование с помощью средств, предоставляемых системой Delphi.
Нарисовать картинку в среде Delphi можно на многих компонентах (например на форме, на TPaintBox), однако наиболее удобно использовать компонент TImage (страница Additional). Нарисованную в Image1 картинку можно ClipBoard.Assign(Image1.Picture) (модуль Clipbrd). Для рисования используют класс TСanvas, который является свойством многих компонентов, и представляет собой прямоугольный холст в виде матрицы из пикселей и набор инструментов для рисования на нем. Каждый пиксель имеет координату (x, y), где x – порядковый номер пикселя, начиная от левой границы холста, а y – порядковый номер пикселя, начиная от верхней границы холста. Левый верхний угол холста имеет координату (0, 0), а нижний правый (Image1.Width-1, Image1.Height-1).
Property Pen : TPen; – карандаш. В свою очередь, имеет свойства Color - цвет, Width - толщина и Style – стиль ( psSolid – сплошной, psDash – штриховой, psDot – пунктирный, psClear – отсутствие линии и др.).
Property Brush : TBrush; – кистью. Это свойство определяет фон заполнения замкнутых фигур. В свою очередь, имеет свойства Color цвет и Style – стиль ( bsSolid – сплошной, bsCross – сетка, bsClear – отсутствие фона и др.).
Property Font : TFont; – шрифт. В свою очередь, имеет свойства Color - цвет, Size - размер и Style – стиль ( fsBold – жирный, fsitalic – курсив и др.).
Pгосеdure Еlliрsе(Х1, Y1, Х2, Y2: Integer) – рисует эллипс в охватывающем прямоугольнике (X1, Y1), (Х2, Y2) и заполняет внутреннее пространство эллипса текущей кистью.
Pгосedure LineТо (X, У: Integer) – рисует линию от текущего положения пера до точки (X. У).
Procedure МоvеТо(Х, У: Integer) – перемещает карандаш в точку (X, У) без вычерчивания линий.
Pгосedure Роlуgоn (Роints: аrrау оf ТРоint) – рисует многоугольник по точкам, заданным в массиве Роints.
Например: Canvas.Polygon([Point(x1, y1), Point(x2, y2), Point(x3, y3]); Конечная точка соединяется с начальной и многоугольник заполняется кистью. Для вычерчивания без заполнения используется метод Роlуline.
Pгосedure Rectangle (X1, У1, Х2, У2: Integer) – рисует и заполняет прямоугольник (X1, У1), (Х2, У2). Для вычерчивания без заполнения используется FrameRect или РоlуLine.
Procedure ТехtОut (Х, У: Integer; const Техt: String) – выводит текстовую строку Техt так, чтобы левый верхний угол прямоугольника, охватывающего текст, располагался в точке (X, У).
14.2. Построение графиков с помощью компонента Chart Обычно результаты расчетов представляются в виде графиков и диаграмм. Среда Delphi имеет мощный пакет стандартных программ вывода на экран и редактирования графической информации, который реализуется с помощью визуально отображаемого на форме компонента Chart.
Построение графика (диаграммы) производится после вычисления таблицы значений функции y=f(x). Полученная таблица передается в специальный двумерный массив ChartI.SeriesList[k] (k – номер графика (0,1,2,...)) компонента Сhart с помощью метода AddXY. Компонент Chart осуществляет всю работу по отображению графиков, переданных в объект ChartI.SeriesList[k]:
строит и размечает оси, рисует координатную сетку, подписывает название осей и самого графика, отображает переданную таблицу в виде всевозможных графиков или диаграмм. При необходимости, с помощью встроенного редактора EditingChart компоненту Сhart передаются данные о толщине, стиле и цвете линий, параметрах шрифта подписей, шагах разметки координатной сетки и другие настройки. В процессе работы программы изменение параметров возможно через обращение к соответствующим свойствам компонента Chart. Так, например, свойство Chart1.BottomAxis содержит значение максимального предела нижней оси графика. Перенести график в отчет можно через буфер обмена, используя процедуру ChartI.CopyToClipboardMetafile(True).
Примеры. Построить графики функций sin(x) и cos(x) с помощью компонента Chart. Текст и форма проекта приведены ниже.
uses Windows,Messages,SysUtils,Variants,Classes, Graphics,Controls,Forms,Dialogs,StdCtrls,TeEngine, Series, ExtCtrls, TeeProcs, Chart, Buttons;
type TForm1 = class(TForm) Chart1: TChart;
Series1: TLineSeries;
Series2: TLineSeries;
Button1: TButton;
BitBtn1: TBitBtn;
procedure Button1Click(Sender: TObject);
private { Private declarations } public { Public declarations } end;
var Form1: TForm1;
f:file of extended;
implementation {$R *.dfm} procedure TForm1.Button1Click(Sender: TObject);
var k:integer; // Нарисовать x,y,z:extended;
begin for k:=0 to 100 do begin x:=0.02*pi*k; y:=sin(x); z:=cos(x);
series1.AddXY(x,y,'',clRed);
series2.AddXY(x,z,'',clGreen);
end;
end.
текст.
uses Windows,Messages,SysUtils,Variants,Classes,Graphics, Controls,Forms,Dialogs,StdCtrls,Buttons;
type TForm1 = class(TForm) Button1: TButton;
Button2: TButton;
BitBtn1: TBitBtn;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private { Private declarations } public { Public declarations } end;
var Form1: TForm1;
implementation {$R *.dfm} procedure TForm1.Button1Click(Sender: TObject);
begin with form1.Canvas do begin pen.Width:=3;
pen.color:=clred;
brush.style:=bsCross;
brush.Color:=clgreen;
polygon([point(190,30), point(240,60), point(170,40)]);
polyline([point(290,30), point(340,60), point(270,40)]);
rectangle(200,100,280,140);
ellipse(20,150,220,220);
font.color:=clblue;
font.Size:=50;
textout(350,120,'test');
end;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin // Очистить refresh;
end;
end.
ЛЕКЦИЯ 15. ПРОГРАММИРОВАНИЕ С
ИСПОЛЬЗОВАНИЕМ РЕКУРСИИ
Рекурсивным называется описание объекта, частично состоящее и определяемое с помощью самого описываемого объекта. Рекурсия – это такой способ организации вычислительного процесса, при котором подпрограмма в ходе выполнения обращается сама к себе.Классический пример: вычисление факториала n! = 1*2*3…(n-1)*n.
Рекурсивное описание: n! = (n-1)! * n, 0! = 1.
Рекурсивная функция:
Function fak(n:word):extended;
Примечание: Тип результата вычислений (extended) выбран из-за большего диапазона допустимых значений быстрорастущей функции n!.
Нерекурсивная функция:
Function fak(n:word):extended;
При выполнении рекурсивной подпрограммы осуществляется многократный переход от текущего уровня организации алгоритма к нижнему уровню последовательно, до тех пор, пока не будет получено тривиальное решение задачи (в вышеприведенном примере, n=0). Рекурсивная форма записи алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении работает медленнее и может вызвать переполнение программного стека (исключительная ситуация EStackOverFlow), т. к. при каждом переходе к следующему уровню (рекурсивной активации подпрограммы) происходит создание и запоминание всех ее локальных и формальных параметров. В результате, после n-й активации в памяти будет находиться список из n+1 комплектов таких параметров.
Рекурсивный вызов может быть прямым, как в вышеприведенном примере, и косвенным. В этом случае подпрограмма обращается к себе опосредованно, путем вызова другой подпрограммы, в которой содержится обращение к первой.
Procedure rex(); Forward;
Procedure fox();
Procedure rex;
В этом примере обращение к процедуре rex() записано раньше, чем ее описание, что недопустимо в Pascal. Для разрешения этой ситуации используется опережающее описание с помощью стандартной директивы Forward.
Внимание. Для предотвращения зацикливания рекурсивной подпрограммы необходимо предусмотреть обязательный выход на тривиальное решение, т. е. на ветвь, не содержащую обращение подпрограммы к самой себе.
Найти максимальный элемент в массиве используя метод деления массива пополам max (a1…an) = max ( max ( a1…an/2 ), max ( an/2+1…an ) ) type vek=array[1..50] of extended;
function maxR(x:vek; m,n:integer):extended ;
var k:integer;
begin if m=n then result:=x[m] if maxR(x,m,k)>maxR(x,k+1,n) then result:=maxR(x,m,k) else result:=maxR(x,k+1,n);
end;
end;
Найти максимальный элемент в массиве используя очевидное соотношение max (a1…an) = max ( max(a1…an-1), an) function maxRn(x:vek; n:integer):extended;
begin if n=1 then result:=x[1] else if maxRn(x,n-1)>x[n] then result:=maxRn(x,n-1) end;
ЛЕКЦИЯ 16. ПОИСК И СОРТИРОВКА МАССИВОВ
Для создания и обработки всевозможных баз данных широко применяются массивы записей. Обычно база данных накапливается и хранится на магнитном диске. К ней часто приходится обращаться, обновлять, перегруппировывать. Работа с базой может быть организована двумя способами:1. Вносить изменения и осуществлять поиск можно прямо на диске, используя специфическую технику работы с записями на файлах, при этом временные затраты на обработку данных (поиск, сортировку) значительно возрастают, но нет ограничений на оперативную память.
2. В начале работы вся база (или ее необходимая часть) считывается в массивы записей и обработка производится в оперативной памяти, что значительно сокращает ее время, однако требует затрат оперативной памяти. Наиболее частыми операциями при работе с базами данных являются «поиск» и «сортировка».
При этом алгоритмы решения этих задач существенно зависят от того, организованы записи в массивы или размещены на диске. Обычно запись содержит некое ключевое поле (ключ), по которому ее находят среди множества других аналогичных записей. В зависимости от решаемой задачи ключом может служить, например, фамилия, номер расчетного счета или адрес. Основное требование к ключу в задачах поиска состоит в том, чтобы операция проверки на равенство была корректной. Поэтому, например, в качестве ключа не следует выбирать действительное число, т.к. из-за всегда возможной ошибки округления поиск нужного ключа может оказаться безрезультатным, хотя этот ключ в массиве имеется.
Задача поиска требуемого элемента в массиве записей a[i], i = 1..n заключается в нахождении индекса i, удовлетворяющего условию a[i].k = isk. Здесь поле записи k выступает в качестве ключа, isk – искомый ключ. После нахождения i обеспечивается доступ ко всем другим полям найденной записи a[i].
Линейный (последовательный) поиск используется, когда нет никакой дополнительной информации о разыскиваемых данных. Он представляет собой последовательный перебор массива до обнаружения требуемого ключа или до конца, если ключ не обнаружен:
if a[m].k100 наихудшим является метод пузырька, метод QuickSort в 2- раза лучше, чем HeapSort, и в 3-7 раз, чем метод Шелла.
Рассмотрим алгоритмы и реализацию некоторых методов.
В алгоритме сортировки методом пузырька сравниваются два соседних элемента. Если они расположены в неправильной последовательности, то выполняется перестановка этих элементов. Сортировка осуществляется путем многократного прохождения по списку элементов. При сортировке по возрастанию элементы с малыми значениями поднимаются вверх в начало списка, подобно пузырькам воздуха в воде. Процедура пузырьковой сортировки имеет вид type vec = array[1..100] of extended;
ind = array[1..100] of integer;
Procedure PuzSort(var a:vec; n:integer);
var k,kol:integer; // Метод Пузырька В общем случае для сортировки требуется n–1 проход по массиву. Чтобы исключить ненужные проходы, если массив уже полностью или частично отсортирован, используется не цикл с заданным количеством повторений (for kol := 1 to n – 1 do), а оператор repeat с флажком p.
Сортировка осуществляется путем многократного прохождения по списку элементов. На каждом (k-ом) проходе находится минимальный элемент с к-го по n- ый элементы, который затем переставляется с к-ым элементом.
Процедура этой сортировки имеет вид Procedure PramSort(var a:vec; n:integer);
var k,i,m:integer;
Полезный совет: перестановка элементов со сложными типами данных – довольно длительный процесс. Поэтому рекомендуется вместо перестановки самих данных переставлять индексы. Такой прием используется практически во всех коммерческих приложениях. В этом случае процедура сортировки Шелла имеет вид type ind=array[1..100] of integer;
Procedure ShellSortInd(a:vec; n:integer; var nom:ind);
var k,kol,w:integer;
begin for k:=1 to n do nom[k]:=k;
kol:=n div 2; // Зазор if a[nom[k]]>a[nom[k+kol]] then until kol=0;
end;
В алгоритме Хоара сначала выбирается так называемое опорное значение. Затем элементы со значением, меньше опорного, переносятся влево, а со значением, большим или равным ему, - вправо. Таким образом, на первом шаге алгоритм Хоара делит элементы на два раздела: со значениями, меньшими опорного, и со значениями, большими или равными ему. Затем подпрограмма, рекурсивно вызывая сама себя, продолжает разбивку разделов.
В каждом разделе выбирается новое опорное значение, и элементы раздела переставляются влево и вправо. Процесс разбивки на разделы рекурсивно продолжается до тех пор, пока размер раздела достигнет одного или двух элементов. Эффективность метода зависит от объема данных и выбора метода опорного сечения. В приведенном ниже алгоритме в качестве опорного выбирается средний элемент раздела. Процедура сортировки Хоара имеет вид Procedure QuickSort(var a:vec; low,high:integer);
var l,r:integer; // Метод Хоара op,w:extended;
begin op:=a[(low+high) div 2]; // Опорный элемент // Перенос элементов, меньших опорного, влево, а больших - вправо l:=low; r:=high;
while (lop) do dec(r);
if r>low then QuickSort(a,low,r);
if l0 then inc(kol);
t:=t^.a; // Задаем адрес следующего элемента label1.Caption:='Кол. полож. элементов стека = ' end;
Для работы с односвязными списками необходимо создать, например, модуль List1S, содержащий описание рекурсивного типа и набор специализированных процедур.
Добавить новый элемент в стек procedure AddStek(var w:TSel; inf:Tinf);
begin New(t); // Создать новый элемент t^.inf:=inf; // Запись информационной части t^.a:=w; // В адресную часть заносим прежнюю вершину w:=t; // Задаем новую вершину end;
Прочитать n-й элемент стека ( от вершины ) procedure ReadStek(w:TSel; n:integer; var inf:Tinf);
var i:integer;
begin if w=nil then exit;
t:=w; // Текущий адрес=вершине for i:=1 to n do inf:=t^.inf;
t:=t^.a; // Задаем адрес следующего элемента end;
Прочитать и удалить последний элемент стека ( 1-й от вершины ) procedure DelLast(var w:TSel; var inf:Tinf);
var t:TSel;
begin inf:=w^.inf;
w:=w^.a;//За новую вершину стека берем адрес след элем dispose(t); // Освобождаем память end;
Удалить стек procedure DelStek(var w:TSel);
var inf:Tinf;
begin while wnil do DelLast(w,inf);
end;
Вывод стека в ListBox procedure WrtStek(w:Tsel; LS:TListBox);
var t:Tsel;
begin LS.clear;
t:=w; // Текущий адрес = вершине стека while tnil do LS.Items.Add(intToStr(t^.inf));
end;
Перестановка адресов двух соседних элементов, следующих за элементом с адресом sp procedure RevAfter(sp:TSel);
begin t:=sp^.a^.a;
sp^.a^.a:=t^.a;
t^.a:=sp^.a;
sp^.a:=t;
end;
Обмен информации между элементом с адресом sp и следующим за ним Procedure Revinf(sp:TSel);
var inf:Tinf;
begin inf:=sp^.inf;
sp^.inf:=sp^.a^.inf;
sp^.a^.inf:=inf;
end;
Пузырьковая сортировка стека перестановкой адресов procedure SortAfter(var w:TSel);
var p,t:Tsel;
begin if (w=nil)or(w^.a=nil) then exit;//Пуст или 1 элемент AddStek(w,0); // Добавляем пустой элемент t:=nil;
repeat while p^.a^.at do if p^.a^.inf>p^.a^.a^.inf then RevAfter(p);
until w^.a^.a=t;
DelLast(w,inf); // Удаляем пустой элемент end;
Пузырьковая сортировка стека обменом информации procedure Sortinf(w:TSel);
var p,t:Tsel;
begin if (w=nil)or(w^.a=nil) then exit;//Пуст или 1 элемент t:=nil;
repeat if p^.inf>p^.a^.inf then Revinf(p);
until w^.a=t;
end;
18.4. Процедуры для работы с односвязными очередями Добавление нового элемента в начало очереди procedure AddBeg(var w1,wk:TSel; inf:Tinf);
begin if w1=nil then begin // Если очередь пуста end;
Добавление нового элемента в конец очереди procedure AddEnd(var w1,wk:TSel; inf:Tinf);
var t:TSel;
begin if wk=nil then begin // Если очередь пуста end;
Добавление нового элемента в середину стека или очереди после элемента с адресом sp procedure AddAfter(sp:TSel; inf:Tinf);
begin if sp^.a=nil then exit; //Нельзя вставлять в конец new(t);
t^.inf:=inf;
t^.a:=sp^.a;
sp^.a:=t;
end;
Чтение и удаление элемента из начала очереди procedure DelBeg(var w1,wk:TSel; var inf:Tinf);
var t:tsel;
begin if w1=nil then exit; // Если очередь пуста inf:=w1^.inf;
w1:=w1^.a; // новое начало - адрес след элемента dispose(t); // Освобождаем память if w1=nil then wk:=nil;
end;
Чтение и удаление элемента из середины стека или очереди после элемента с адресом sp procedure DelAfter(sp:TSel; var inf:Tinf);
var t:tsel;
begin // Нельзя удалять последний элемент if (sp^.a=nil) or (sp^.a^.a=nil) then exit;
inf:=t^.inf; // Читаем информацию sp^.a:=t^.a;//Задаем адрес эл. стоящего за удаляемым dispose(t); // Освобождаем память end;
Удалить очередь procedure DelSpis(var w1,wk:TSel);
var a:Tinf;
begin while w1nil do DelBeg(w1,wk,a);
end;
Процедура сортировки очереди слиянием двух отсортированных очередей SortSl() требует двух вспомогательных процедур: слияния двух отсортированных очередей в одну ( отсортированную ) slip() и разбиения очереди на две div1s():
procedure slip (var sq1,sqk,sr1,srk,sp1,spk:TSel);
var infq,infr:Tinf;
begin sp1:=nil; spk:=nil;
while (sq1nil) and (sr1nil) do DelBeg(sq1,sqk,infq);
DelBeg(sr1,srk,infr);
begin//Удаление элем. между min и max в 1-м списке DelD(t,inf);
AddEndD(w13,wk3,inf); //Вставка их в 3-й список WrtBegD(w11,memo3); // вывод промежуточного 1-го списка WrtBegD(w13,memo4); // вывод вырезанного списка t:=tmin;
while w12nil do DelBegD(w12,wk2,inf); // Вставка 2-го списка AddAfterD(t,inf); // между min и max 1-го списка WrtBegD(w11,memo5); // вывод итогового списка button4.enabled:=true;
end;
procedure TForm1.Button4Click(Sender: TObject);
sortslD(w11,wk1);
WrtBegD(w11,memo6);
procedure TForm1.Button5Click(Sender: TObject);
begin // Очистить memo1.Clear; memo2.Clear; memo3.Clear;
memo4.Clear; memo5.Clear; memo6.Clear;
DelSpisD(w11,wk1); // Удаление очереди DelSpisD(w12,wk2); // Удаление очереди DelSpisD(w13,wk3); // Удаление очереди end;
procedure TForm1.BitBtn1Click(Sender: TObject);
begin // Close DelSpisD(w11,wk1); // Удаление очереди DelSpisD(w12,wk2); // Удаление очереди DelSpisD(w13,wk3); // Удаление очереди end.
ЛЕКЦИЯ 19. АЛГОРИТМЫ РЕШЕНИЯ СИСТЕМ
ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ
Выделяют четыре основные задачи линейной алгебры: решение СЛАУ, вычисление определителя матрицы, нахождение обратной матрицы, определение собственных значений и собственных векторов матрицы.Задача отыскания решения СЛАУ с n неизвестными - одна из наиболее часто встречающихся в практике вычислительных задач, так как большинство методов решения сложных задач основано на сведении их к решению некоторой последовательности СЛАУ.
Обычно СЛАУ записывается в виде Известно, что если определитель матрицы A 0, то СЛАУ имеет единственное решение. В противном случае решение либо отРис.19. важно чтобы задача была корректной, т.е. чтобы при малых погрешностях правой части b и (или) коэффициентов aij погрешность решения x * также оставалась малой. Признаком некорректности, или плохой обусловленности, является близость к нулю определителя матрицы.
Плохо обусловленная система двух уравнений геометрически соответствует почти параллельным прямым (рис.19.1). Точка пересечения таких прямых (решение) при малейшей погрешности коэффициентов резко сдвигается.
Обусловленность (корректность) СЛАУ характеризуется числом = A A 1. Чем дальше от 1, тем хуже обусловлена система. Обычно при > 103 система некорректна и требует специальных методов решения методов регуляризации. Приведенные ниже методы применимы только для корректных систем.
Методы решения СЛАУ делятся на прямые и итерационные.
Прямые методы дают в принципе точное решение (если не учитывать ошибок округления) за конечное число арифметических операций. Для хорошо обусловленных СЛАУ небольшого порядка n 200 применяются практически только прямые методы.
Наибольшее распространение среди прямых методов получили метод Гаусса для СЛАУ общего вида, его модификация для трехдиагональной матрицы - метод прогонки и метод квадратного корня для СЛАУ с симметричной матрицей.
Итерационные методы основаны на построении сходящейся к точному решению x* рекуррентной последовательности векторов ( x, x, x,..., x x. Итерации выполняют до тех пор, пока норма разности k = x x Итерационные методы выгодны для систем большого порядка n>100, а также для решения плохо обусловленных систем. Многообразие итерационных методов решения СЛАУ объясняется возможностью большого выбора рекуррентных последовательностей, определяющих метод. Наибольшее распространение среди итерационных методов получили одношаговые методы простой итерации и Зейделя с использованием релаксации.
Для контроля полезно найти невязку полученного решения x :
если велико, то это указывает на грубую ошибку в расчете.
Ниже приведено описание алгоритмов указанных методов решения СЛАУ.
Метод основан на приведении с помощью преобразований, не меняющих решение, исходной СЛАУ (19.1) с произвольной матрицей к СЛАУ с верхней треугольной матрицей вида
Этап приведения к системе с треугольной матрицей называется прямым ходом метода Гаусса.
Решение системы с верхней треугольной матрицей (19.2), как легко видеть, находится по формулам, называемым обратным ходом метода Гаусса:
Прямой ход метода Гаусса осуществляется следующим образом: вычтем из каждого m-го уравнения (m=2,3,..,n) первое уравнение, умноженное на am1 / a11, и вместо m-го уравнения подставим полученное. В результате в матрице системы исключаются все коэффициенты 1-го столбца ниже диагонального. Затем, используя 2-е полученное уравнение, аналогично исключим элементы второго столбца (m=3,4,..,n) ниже диагонального и т.д. Такое исключение называется циклом метода Гаусса. Проделывая последовательно эту операцию с расположенными ниже k-го уравнениями (k=1, 2,..., n-1), мы приходим к системе вида (19.2). При указанных операциях решение СЛАУ не изменяется.
На каждом k-м шаге преобразований прямого хода элементы матриц изменяются по формулам прямого хода метода Гаусса:
Элементы akk называются главными. Заметим, что если в ходе расчетов по данному алгоритму на главной диагонали окажется нулевой элемент akk = 0, то произойдет сбой в ЭВМ. Для того чтобы избежать этого, следует каждый цикл по k начинать с перестановки строк: среди элементов k-го столбца amk, k m n находят номер p главного, т.е. наибольшего по модулю, и меняют местами строки k и p. Такой выбор главного элемента значительно повышает устойчивость алгоритма к ошибкам округления, т.к. в формулах (19.4) при этом производится умножение на числа amk / akk меньшие единицы и ошибка, возникшая ранее, уменьшается.
Многие задачи (например, решение дифференциальных уравнений 2-го порядка) приводят к необходимости решения СЛАУ с трехдиагональной матрицей:
или коротко эту систему записывают в виде В этом случае расчетные формулы метода Гаусса значительно упрощаются. После исключения поддиагональных элементов в результате прямого хода метода Гаусса и последующего деления каждого уравнения на диагональный элемент систему (19.5) можно привести к виду При этом формулы прямого хода для вычисления i, i, как нетрудно получить, имеют вид Когда такое преобразование (прямой ход) сделано, формулы обратного хода метода Гаусса получаются в виде Расчетные формулы (19.8), (19.9) получили название «метод прогонки». Достаточным условием того, что в формулах метода прогонки не произойдет деления на нуль и расчет будет устойчив относительно погрешностей округления, является выполнение неравенства qi pi + ri (хотя бы для одного i должно быть строгое неравенство).
Предназначен для решения СЛАУ с симметричной матрицей. Этот метод основан на представлении такой матрицы в виде произведения трех матриц: A = S T D S, где D - диагональная с элементами di=±1; S - верхняя треугольная ( sik = 0, если i>k, причем sii > 0 ), S T - транспонированная нижняя треугольная. Матрицу S можно по аналогии с числами трактовать как корень квадратный из матрицы A, отсюда и название метода.
Если S и D известны, то решение исходной системы A x = S T D S x = b сводится к последовательному решению трех систем двух треугольных и одной диагональной:
Решение систем (19.10) ввиду треугольности матрицы S осуществляется по формулам, аналогичным обратному ходу метода Гаусса:
Нахождение элементов матрицы S (извлечение корня из А) осуществляется по рекуррентным формулам:
В этих формулах сначала полагаем k=1 и последовательно вычисляем d 1 = sig n ( a11 ); s11 = a11 и все элементы первой строки матрицы S ( s1 j, j > 1), затем полагаем k=2, вычисляем s22 и вторую строку s1 j для j> и т.д.
Метод квадратного корня почти вдвое эффективнее метода Гаусса, т.к.
«