Основы алгоритмизации и программирования

РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

Методические указания к занятию 3

Вопросы занятия:

1.Характеристика древовидных структур.

2.Действия с бинарными деревьями.

При изучении первого вопроса:

Ознакомьтесь с материалом раздела «Бинарные деревья» базового учебного пособия «Основы алгоритмизации и программирования» и книгой Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001, стр. 238239. Кроме понятия бинарного дерева существуют сильноветвящиеся деревья и лес. Дополнительную информацию можно почерпнуть из книги Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.

При изучении второго вопроса:

Ознакомьтесь с материалом разделов «Действия с бинарными деревьями» и «Решение задач работы с бинарным деревом» базового учебного пособия «Основы алгоритмизации и программирования» и книгой Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001, стр. 239-253. Приведенные алгоритмы могут помочь при решении задач и выполнении лабораторных работ. Обратите внимание, что для древовидных структур рекурсивные процедуры больше подходят, чем не рекурсивные. Это объясняется тем, что само определение древовидной структуры является рекурсивным.

Дополнительную информацию можно почерпнуть из книги Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.

Решите задачи из практикума «Задание для решения задач на деревья».

Контрольные вопросы для самооценки

1.Особенности использования статической и динамической памяти.

2.Описание динамических переменных.

3.Использование указателей и ссылочных переменных.

4.Основные процедуры и функции для выделения и освобождения памяти на логическом уровне.

5.Основные процедуры и функции для выделения и освобождения памяти на физическом уровне.

6.Особенности использования динамических переменных.

7.Особенности создания и обработки очередей.

8.Особенности создания и обработки стеков и деков.

9.Особенности создания и обработки однонаправленных списков.

10.Особенности создания и обработки двунаправленных списков.

11.Особенности создания и обработки кольцевых списков.

12.Особенности создания и обработки списков с головными элементами.

13.Особенности создания и обработки мультисписков.

14.Использование рекурсии при работе со списками.

15.Понятия дерева, двоичного дерева поиска.

16.Не рекурсивные способы создания и обработки двоичных деревьев.

17.Рекурсивные способы создания и обработки двоичных деревьев.

166

РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

При изучении темы необходимо

● Читать:

Основная литература:

Грибанов В.П., Калмыкова О.В., Сорока Р.И. «Основы алгоритмизации и программирования». – М.: МЭСИ. – 2004.

Дополнительная литература:

1.Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. – 392с.

2.Фаронов В.В. Turbo Pascal 7.0. Начальный курс. Учебное пособие. – М.: Нолидж, 1998.

– 616 с.

3.Турбо Паскаль 7.0. – К.: Издательская группа BHV, 2000.

4.Грызлов В.И., Грызлова Т.П. Турбо Паскаль 7.0. – М.: ДМК, 2000.

5.Культин Н. Turbo Pascal . Самоучитель+CD-ROM. – К.: BHV-Санкт-Петербург, 1997.

6.Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0. – М: Диалог–МИФИ, 1996

7.Немнюгин С.А. Turbo Pascal. – СПб: Питер, 2000.

8.Попов В.Б. Turbo Pascal для школьников. Версия 7.0. – Финансы и статистика, 1996.

9.Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.

10.Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.

11.Лэнгсам Й., Огенстайн М., Тэненбаум А Структуры данных для персональных ЭВМ. –

М.: Мир, 1989.

Посетить сайты Интернет: http://delphid.dax.ru/ http://www.coding.hostmos.ru/ http://www.cydsoft.com/vr-online/ http://www.freepascal.org/ http://www.lazarus.freepascal.org http://dcprograms.narod.ru/ http://adept.h1.ru

http://www.iatp.kharkov.ua/sites/program/index.htm http://delphi.chertenok.ru/ http://programmerts.by.ru/tpascal/ishod/mat/ http://pts.h10.ru

Тема 9. Работа с файлами

Содержание темы

Общие сведения о файлах. Описание файлов. Стандартные процедуры и функции для работы с файлами. Текстовые файлы.

Файлы с типом. Организация последовательного и прямого доступа. Блочный ввод-вывод.

Проектирование программ по структурам данных.

167

РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

Цели изучения темы

●Познакомить с организацией и приемами работы с файлами различных типов в Турбо Паскале.

●Познакомить с технологией разработки программ по структурам данных.

Задачи изучения темы

●Формирование навыков программирования задач создания файлов.

●Формирование навыков программирования задач обработки файлов.

●Ознакомление с технологией разработки программ по структурам данных.

Успешно изучив тему, студент

Знает: способы описания файлов, стандартные процедуры и функции для работы с файлами.

Умеет: составлять программы решения задач обработки файлов.

Приобретает навыки: программирования задач создания и обработки файлов различных типов.

Изучая тему, необходимо акцентировать внимание на следующих понятиях

●физическая запись;

●логическая запись;

●связывание файла;

●открытие файла;

●закрытие файла;

●корректировка файла;

●последовательный доступ;

●прямой доступ;

●типизированный файл;

●текстовый файл;

●файл без типа.

Порядок изучения темы

Для изучения темы выделяется 18 часов самостоятельной работы. Предусмотрены теоретические и практические занятия:

1.Основные приемы работы с файлами.

2.Использование проектирования программ по структурам данных для обработки файлов.

Предусмотрена работа студентов в формах:

1.Изучение теоретического материала.

2.Выполнение практических заданий.

3.Решение задач.

4.Тестирование.

5.Изучение дополнительной литературы.

168

РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

Методические указания

Вопросы первого занятия:

1.Общие сведения о файлах.

2.Процедуры и функции для работы с файлами.

3.Особенности обработки типизированных файлов.

4.Особенности обработки текстовых файлов.

5.Файлы без типа.

При изучении первого вопроса:

Ознакомьтесь с материалом «Общие сведения о файлах» базового учебного пособия «Основы алгоритмизации и программирования» и книгой Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001, стр. 188190. В некоторых литературных источниках (например, Дайитбегов Д.М., Черноусов Е.А. Основы алгоритмизации и алгоритмические языки. Учебник. 2-е изд., М., Финансы и статистика, 1992) файл на носителе называется набором данных, в отличие от файла в программе, который называется просто файлом.

При изучении второго вопроса:

Ознакомьтесь с материалом раздела «Процедуры и функции для работы с файлами» базового учебного пособия «Основы алгоритмизации и программирования» и книгой Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001, стр. 190-196. Здесь приводятся основные процедуры и функции для работы с файлами. Другие процедуры описываются применительно к конкретным организациям файлов.

При изучении третьего вопроса:

Ознакомьтесь с материалом раздела «Особенности обработки типизированных файлов» базового учебного пособия «Основы алгоритмизации и программирования» и книгой Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001, стр. 201-206. Обратите внимание на то, что организация типизированного файла допускает как последовательный, так и прямой доступ к записям файла, что существенно ускоряет обработку такого файла. Кроме того, в программе на стр.71 показана проверка существования файла, которую целесообразно делать при открытии файла. Особенно это важно при создании файла, т.к. в случае открытия файла для записи существующий файл будет уничтожен.

При изучении четвертого вопроса:

Ознакомьтесь с материалом раздела «Особенности обработки текстовых файлов» базового учебного пособия «Основы алгоритмизации и программирования» и книгой Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001, стр. 196-201. В теоретическом материале приводятся тексты программ, содержащие примеры создания и обработки текстовых файлов, которые могут помочь при разработке программ практических заданий, лабораторных работ и группового проекта.

При изучении пятого вопроса:

Ознакомьтесь с материалом раздела «Файлы без типа» базового учебного пособия «Основы алгоритмизации и программирования». Несмотря на наличие таких возможностей в языке, обычно для копирования файлов используют средства операционной системы.

Решите задачи 1-6 из практикума «Задание для решения задач на файлы».

169

РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

Методические указания к занятию 2

Вопросы занятия:

1.Общий подход к проектированию программ по структурам данных.

2.Проектирование программы.

3.Кодирование программы.

При изучении первого вопроса:

Ознакомьтесь с материалом раздела «Проектирование программ по структурам данных» базового учебного пособия «Основы алгоритмизации и программирования». Обратите внимание, что одним из вариантов в подходе МЭСИД является следующая последовательность шагов с преобладающим направлением от выхода к входу и от физического к логическому:

1.Составление диаграммы структуры выходных данных.

2.Составление диаграммы структуры входных данных.

3.Составление диаграммы структуры программы с матрицей операций.

4.Заполнение матрицы операций.

5.Составление текста программы на языке программирования

При таком подходе к разработке программ процесс кодирования, т.е. непосредственно написания на языке программирования, становится достаточно простой работой.

При изучении второго вопроса:

Ознакомьтесь с материалом раздела «Работа с файлами при обработке экономической информации» пункты «Постановка задачи» и «Проектирование программы» базового учебного пособия «Основы алгоритмизации и программирования». Здесь рассматривается достаточно большая экономическая задача с подведением нескольких уровней степеней итогов. Демонстрируется применение рассмотренного ранее подхода.

При изучении третьего вопроса:

Ознакомьтесь с материалом раздела «Работа с файлами при обработке экономической информации» пункт «Кодирование программы» базового учебного пособия «Основы алгоритмизации и программирования». Рассмотренный пример доведен до текста программы и может служить базой при разработке текста программ, связанных с получением ведомостей в лабораторной работе.

Решите задачи 7 и 8 из практикума «Задание для решения задач на файлы» с применением рассмотренного подхода.

Выполните лабораторную работу «Работа с файлами».

В лабораторной работе требуется создать многоуровневую диалоговую программу. Примерная структура меню:

Главное меню.

0.Выход.

1.Ведение основного файла.

2.Ведение справочников.

3.Формирование ведомостей.

4.Построение графика или диаграммы.

1.Ведение основного файла.

170

РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

1.1.Создание нового основного файла.

1.2.Корректировка основного файла.

1.3.Просмотр на экране основного файла.

1.4.Печать основного файла.

2.Ведение справочников.

2.1.Создание нового справочника.

2.2.Корректировка справочника.

2.3.Просмотр на экране справочника.

2.4.Печать справочника.

3.Формирование ведомостей.

3.1.Вывод ведомости в файл.

3.2.Просмотр ведомости на экране (движение по стрелкам).

3.3.Вывод ведомости на печать.

Вначале выполнения работы выдается заставка с указанием авторов работы.

Вкаждом варианте лабораторной работы создается основной файл – типизированный и два справочника: один – типизированный, другой – текстовый. Ведомости формируются тоже две: для одной используется один справочник и основной файл, для другой – два справочника и основной файл. В основном файле должно быть не менее 30 записей. Записи основного файла должны быть упорядочены в соответствии с условием при создании файла.

Корректировка файлов должна включать добавление записей (в конец файла, в произвольное место файла), удаление записей, корректировку отдельных полей записей.

Структура отчета по лабораторной работ.

1.Титульный лист.

2.Содержание.

3.Постановка задачи.

4.Сценарий диалога.

5.Схема взаимосвязей процедур.

6.Спецификация процедур.

6.1.Название процедуры и ее назначение.

6.2.Описание вызова процедуры.

6.3.Описание входных параметров.

6.4.Описание выходных параметров.

6.5.Описание внешних данных.

6.6.Описание используемых файлов.

6.7.Список процедур, вызываемых из данной процедуры.

6.8.Алгоритм (схема МЭСИД) для процедур формирования ведомостей.

7.Входные данные (основной файл и 2 справочника).

8.Результаты работы программ (2 ведомости и график или диаграмма).

9.Литература.

10.Листинги.

171

РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

Контрольные вопросы для самооценки

1.Что такое физическая запись и логическая запись?

2.Что такое файл?

3.В чем заключается последовательный доступ к записям файла?

4.В чем заключается прямой доступ к записям файла?

5.К записям файла, с какой организацией возможен и последовательный и прямой доступ?

6.Какой доступ возможен к записям текстового файла?

7.Со структуркаких данных начинается проектирование программ по структурам данных?

При изучении темы необходимо

● Читать:

Основная литература:

Грибанов В.П., Калмыкова О.В., Сорока Р.И. «Основы алгоритмизации и программирования». – М., МЭСИ. – 2004.

Дополнительная литература:

1.Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. – 392 с.

2.Фаронов В.В. Turbo Pascal 7.0. Начальный курс. Учебное пособие. – М.: Нолидж, 1998.

– 616 с.

3.Турбо Паскаль 7.0. – К.: Издательская группа BHV, 2000.

4.Грызлов В.И.,Грызлова Т.П. Турбо Паскаль 7.0. – М.: ДМК, 2000.

5.Культин Н. Turbo Pascal . Самоучитель+CD-ROM. – К.: BHV-Санкт-Петербург, 1997.

6.Епанешников А.М., Епанешников В.А. Программирование в среде Turbo Pascal 7.0. – М: Диалог–МИФИ, 1996.

7.Немнюгин С.А. Turbo Pascal. – СПб: Питер, 2000.

8.Попов В.Б. Turbo Pascal для школьников. Версия 7.0. – Финансы и статистика, 1996.

Посетить сайты Интернет: http://clubprogrammers.netfirms.com http://delphid.dax.ru/ http://www.coding.hostmos.ru/ http://www.cydsoft.com/vr-online/ http://www.freepascal.org/ http://www.lazarus.freepascal.org http://dcprograms.narod.ru/ http://adept.h1.ru

http://www.iatp.kharkov.ua/sites/program/index.htm http://delphi.chertenok.ru/ http://programmerts.by.ru/tpascal/ishod/mat/ http://pts.h10.ru

172

РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

Теоретические вопросы экзамена по дисциплине «Основы алгоритмизации и программирования»

1.Основные определения и понятия курса.

2.Изобразительные средства алгоритмов.

3.Базовые канонические структуры алгоритмов.

4.Основные понятия языка Турбо-Паскаль (алфавит, элементарные конструкции, типы данных).

5.Арифметические и логические выражения. Действия над данными и оператор присваивания.

6.Управляющие операторы языка.

7.Операторы цикла в Турбо-Паскале.

8.Составной оператор и особенности его использования.

9.Структура программы на языке Паскаль.

10.Область действия имен в Паскаль-программе.

11.Процедуры и функции преобразования.

12.Особенности описания и вызова процедур.

13.Особенности описания и вызова функций.

14.Рекурсивные процедуры и функции.

15.Понятие модуля, его описание и подключение.

16.Структура и описание модуля.

17.Стандартные модули Турбо-Паскаля.

18.Процедуры и функции модуля CRT.

19.Функции и процедуры порядкового типа.

20.Процедуры и функции для обработки строк.

21.Процедуры ввода-вывода.

22.Работа с множествами (описание, свойства).

23.Операции над множествами.

24.Работа с записями (описание записи, оператор присоединения).

25.Запись с вариантами.

26.Структура памяти Турбо-Паскаль программы.

27.Общие сведения о динамических переменных.

28.Управление памятью с помощью стандартных процедур и функций.

29.Общие сведения о файлах, описание файлов.

30.Стандартные процедуры и функции для работы с файлами.

31.Типизированные файлы.

32.Текстовые файлы.

33.Файлы без типа.

34.Общий подход к разработке программ при проектировании программ по структурам данных.

35.Алгоритм подведения итогов различного уровня при отсортированных данных.

36.Динамические структуры данных.

37.Динамические массивы. Алгоритмы обработки динамических массивов.

38.Основные виды списков. Способы их описания.

39.Однонаправленные (линейные) списки. Описание, создание и просмотр списка.

40.Однонаправленные (линейные) списки. Модификация списка путем добавления и удаления элементов.

173

РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

41.Двунаправленные (симметричные) списки. Модификация списка путем добавления и удаления элементов.

42.Кольцевые списки. Просмотр кольцевого списка. Модификация списка путем добавления и удаления элементов.

43.Списки с кратными связями.

44.Упорядоченные списки и реорганизация списков.

45.Алгоритм топологической сортировки.

46.Древовидные структуры. Основные определения и понятия.

47.Основные операции с бинарными деревьями.

48.Бинарное дерево. Способы обхода бинарного дерева.

49.Представление арифметических выражений в виде дерева.

50.Двоичное дерево поиска. Поиск по дереву с включением.

51.Двоичное дерево поиска. Удаление из дерева.

52.Сбалансированные деревья.

53.Примеры использования деревьев. Дерево Хаффмена.

174

ПРАКТИКУМ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ «ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ»

О.В. Калмыкова, Р.И. Сорока

Основы алгоритмизации и программирования

Практикум по дисциплине