МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
Южно-Российский государственный технический университет (НПИ)
____________________________________________
Кафедра «Aвтоматикa и телемеханикa»
Малашенко А.Г., Малашенко Л.И., Дереча С.В , Онышко Д.А., Левшин А.Г..
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к практическим занятиям по дисциплине
ПРОГРАММИРОВАНИЕ И ОСНОВЫ АЛГОРИТМИЗАЦИИ
Часть 2
НОВОЧЕРКАССК 2011
УДК 519.6 (076.3)
Методические указания к практическим занятиям по дисциплине «Программирование и основы алгоритмизации. Часть 2»
Методические указания содержат цель, программу выполнения лабораторных работ, контрольные вопросы, указания по выполнению лабораторной работы, требования к содержанию отчета, сведения о литературе, необходимой для подготовки к выполнению работы.
Методические указания предназначены для студентов второго курса специальности «Управление в технических системах» всех форм обучения.
Объем 30 стр., тираж 15 экз.
Методические указания обсуждены и одобрены
на заседании кафедры
Автоматика и телемеханика
ФАУ ЮРГТУ(НПИ)
протокол № ___
Южно-Российский государственный технический
университет (НПИ), 2011
Введение
Для проведения лабораторных работ необходимы любые IBM РС-совместимые компьютеры. В качестве системного программного обеспечения (ПО) требуется операционная среда Windows XP и выше, а в качестве инструментального ПО–любая интегрированная среда для работы с программами на языке Паскаль и Delphi а также среда для работы на языке С++.
При подготовке к работе рекомендуется ознакомиться с методическими указаниями, а после выполнения работы для самоконтроля следует использовать контрольные вопросы.
Каждый студент приобретает практические навыки разработки программ, выполняя индивидуальное заданиt и производит отладку с помощью инструментального ПОдо получения правильного решения контрольных вариантов.
Целькаждого занятия заключается не только в получении работоспособной программы, но, прежде всего, в приобретении навыков программирования путем применения в программах возможно большего количества конструкций языка.Поэтому в индивидуальных заданиях должен быть сделан акцент на обязательное использование в разрабатываемых программах определенных типов, операторов и структур данных. Кроме того, в программах должны быть предусмотрены содержательный ввод и вывод данных в терминах постановки задачи.
Занятие №1
Программирование прикладных задач
Продолжительность занятия 2 часа.
Цель занятия: приобрести умения и навыки программирования прикладных задач.
Подготовка к работе: самостоятельное повторение материалов первого семестра.
Программа занятия
1. Ознакомиться с индивидуальным заданием и сделать математическую постановку задачи.
2. Подготовить тестовый (контрольный) вариант решения задачи.
3. Разработать алгоритм и изобразить его схему.
4. Составить программу основной программы и модуля пользователя по индивидуальному заданию с обязательным использованием подпрограммы-функции и подпрограммы-процедуры.
5. В рамках самостоятельной работы отладить составленную программу.
Контрольные вопросы
1. Какова структура основной программы?
2. Какова структура модуля пользователя?
3. Какова структура подпрограммы-функции?
4. Какова структура подпрограммы-процедуры?
5. Каковы требования к соответствию формальных и фактических параметров?
6. В чем заключается суть алгоритма нахождения суммы (произведения) элементов массива?
7. В чем заключается суть алгоритма нахождения минимального (максимального) элемента массива?
8. В чем заключается суть алгоритма нахождения стандартного значения?
9. В чем заключается суть алгоритма нахождения суммы элементов ряда?
10. Что является исходными данными и результатом задачи сортировки?
Методические указания
К п.1. Исходную задачу нужно представить в математической форме. Например, для получения точек траектории движения объекта нужно составить и решить дифференциальное уравнение. Для определения распределения токов в электрической цепи необходимо составить и решить систему линейных алгебраических уравнений.
К п.2.Для решаемой задачи нужно приготовить тестовый вариант решения. Данные должны быть такими, чтобы можно было проверить большинство ветвей будущего алгоритма. Например, тестовым вариантом для сортировки одномерного массива по возрастанию может быть небольшого размера массив с неупорядоченными элементами 2,7,5,1 а результат массив с упорядоченными элементами 1,2,5,7. Для проверки разветвляющегося алгоритма нужно выбрать такое количество набора исходных данных, чтобы были проверены все ветви алгоритма.
К п.2.Перед разработкой нового алгоритма необходимо вначале ознакомиться с известными алгоритмами, вероятно, их можно использовать для решения задачи. Если таких алгоритмов несколько, то следует сделать обоснованный выбор такого, который лучше применим для данной задачи. Можно внести коррективы в известный алгоритм, чтобы он был более эффективен для решаемой задачи. И только убедившись трудности применения известного, следует заняться разработкой нового алгоритма.
Для изображения схем алгоритма следует повторить материал прошлого семестра.
К п.3 и 4.Для написания программы и ее отладки достаточно знаний и умений, полученных в первом семестре, поэтому отладка выполняется в рамках самостоятельной работы. Наличие в структуре программы основной программы, модуля и подпрограмм является обязательным.
Занятие №2
Программирование списков
Продолжительность занятия 4часов.
Цель занятия: приобрести умения и навыки программирования списков с использованием динамических переменных.
Подготовка к работе: самостоятельное изучение сведений об указателях, динамических переменных, списках.
Программа работы
1. Рассмотреть примеры использования указателей.
2. Изобразить структуры списков: односвязного, стека, очереди и двухсвязного.
3. Составить фрагменты подпрограмм, реализующих обработку элементов списка индивидуального задания.
4. Составить программу основной программы и модуля по индивидуальному заданию.
5. В рамках самостоятельной работы отладить составленную программу.
Контрольные вопросы
1. Что такое указатель и как он описывается?
2. Где размещаются динамические переменные?
3. Как создается динамическая переменная?
4. Как удаляется динамическая переменная?
5. Что такое односвязный список?
6. Что такое стек?
7. Что такое очередь?
8. Что такое кольцо?
9. Что такое двухсвязный список?
10. Как были Вами реализованы процедуры для обработки списка?
Варианты индивидуальных заданий
— Варианты формируются из таблиц 1…3.
Таблица 1- Варианты задания структуры односвязного списка
Вариант списка | ||
Структура односвязного списка | Очередь | Стек |
Таблица 2- Варианты задания типа информационного поля односвязного списка
Вариант поля | |||||
Тип информационного поля | Целый | Вещественный | Символьный | Диапазон (интервальный) | Строковый |
Таблица 3- Варианты задания обработки односвязного списка
Действие 1 | П Р О С М О Т Р | ||||
Вариант просмотра | |||||
Условие | Всех элементов | Первой половины списка | Второй половины списка | До первого заданного | После первого заданного |
Действие 2 | П О И С К | ||||
Вариант поиска | |||||
Условие | минимального элемента списка | максимального элемента списка | среднего по положению элемента списка | среднего по значению элемента списка | 1-го элемента, имеющего значение минимального |
Вариант поиска | |||||
Условие | 1-го элемента, имеющего значение заданного | 1-го элемента, имеющего значение заданного | 1-го элемента, имеющего значение максимального | 1-го элемента, принадлежащего заданному интервалу значений | 1-го элемента, значение которого вне заданного интервала значений |
Действие 3 | У Д А Л Е Н И Е | ||||
Вариант удаления | |||||
Условие | элемента, расположенного за найденным | элемента перед найденным | последнего элемента | первого элемента | найденного элемента, |
Вариант удаления | |||||
Условие | второго элемента, | предпоследнего элемента | элемента, расположенного на два элемента влево от найденного | элемента, расположенного на два элемента вправо от найденного | среднего по положению элемента |
Таблица 4. — Индивидуальные задания к практическому занятию №2.
№ задания | ||||||||||||||||
Вариант списка | ||||||||||||||||
Вариант поля | ||||||||||||||||
Вариант просмотра | ||||||||||||||||
Вариант поиска | ||||||||||||||||
Вариант удаления |
№ задания | ||||||||||||||||
Вариант списка | ||||||||||||||||
Вариант поля | ||||||||||||||||
Вариант просмотра | ||||||||||||||||
Вариант поиска | ||||||||||||||||
Вариант удаления |
Методические указания
К п.1.
Оставшаяся свободной область памяти частично или полностью может быть занятадинамической памятью. В ней размещаются динамические переменные. Эта часть памяти называется “heap” (“куча”)
Динамические переменные создаются и уничтожаются во время выполнения программы в отличие от статических переменных, память под которые резервируется в сегменте данных еще на этапе компиляции.
Динамические переменные не имеют имени. Для работы с ними введены специальные ссылочные типы, или указатели. По существу указатель — это адрес, начиная с которого динамическая переменная размещена в памяти.
Указатель связывается не с конкретной переменной, а с определенным типом данных. Для описания указателя используется знак “^”.
Пример описания
Type
IP = ^Integer; {тип указателя на целое}
P = ^Zap; {тип указателя на запись Zap}
Zap = record
…
end;
Var
Pointer1 : ^Char; {указатель на Char}
Pointer2 : ^Real; {указатель на Real}
В Паскале определена лишь одна операция над указателями — присваивание. Можно присвоить значение одного указателя другому указателю на тот же тип данных. Существуют также нетипизированные указатели, которые совместимы с указателями на любой тип. Для объявления переменной нетипизированным указателем нужно употреблять ключевое слово Pointer
Var
TypePointer: Pointer;
Значением указателя может являться либо адрес, либо значение NIL. NIL-специальное значение, обозначающее пустой указатель, который ни на что не указывает.
Для того, чтобы выделить место в куче под динамическую переменную, используется процедура NEW.
Type
PE = ^integer;
Begin
…
New(PE);
…
End.
В приведенном примере в куче выделяется 4 байтf (в соответствии с размером типа integer) и адрес начала этой области возвращается в указателе PE. Для обращения к полученной динамической переменной используется конструкция вида ^:
PE^:=3.1415;
PE^:=sqr(PE^);
Для освобождения динамической памяти используется процедура Dispose —
Dispose(PE); {освобождает 4 байта в куче}