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

Подождите немного. Документ загружается.

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

166

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

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

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

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

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

Ознакомьтесь с материалом раздела «Бинарные деревья» базового учебного посо-

бия «Основы алгоритмизации и программирования» и книгой Иванова Г.С. Основы про-

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

239. Кроме понятия бинарного дерева существуют сильноветвящиеся деревья и лес. До-

полнительную информацию можно почерпнуть из книги Вирт Н. Алгоритмы и структуры

данных. – М.: Мир, 1989.

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

Ознакомьтесь с материалом разделов «Действия с бинарными деревьями» и «Ре-

шение задач работы с бинарным деревом» базового учебного пособия «Основы алгорит-

мизации и программирования» и книгой Иванова Г.С. Основы программирования: Учеб-

ник для вузов. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2001, стр. 239-253. Приведенные ал-

горитмы могут помочь при решении задач и выполнении лабораторных работ. Обратите

внимание, что для древовидных структур рекурсивные процедуры больше подходят, чем

не рекурсивные. Это объясняется тем, что само определение древовидной структуры яв-

ляется рекурсивным.

Дополнительную информацию можно почерпнуть из книги Вирт Н. Алгоритмы и

структуры данных. – М.: Мир, 1989.

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

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

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

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

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

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

ском уровне.

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

ском уровне.

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

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

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

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

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

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

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

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

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

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

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

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

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

167

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

● Читать:

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

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

мирования». – М.: МЭСИ. – 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. Работа с файлами

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

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

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

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

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

Блочный ввод-вывод.

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

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

168

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

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

Паскале.

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

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

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

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

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

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

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

файлами.

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

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

личных типов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предусмотрены теоретические и практические занятия:

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

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

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

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

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

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

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

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

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

169

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

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

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

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

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

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

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

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

Ознакомьтесь с материалом «Общие сведения о файлах» базового учебного посо-

бия «Основы алгоритмизации и программирования» и книгой Иванова Г.С. Основы про-

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

190. В некоторых литературных источниках (например, Дайитбегов Д.М., Черноусов Е.А.

Основы алгоритмизации и алгоритмические языки. Учебник. 2-е изд., М., Финансы и ста-

тистика, 1992) файл на носителе называется набором данных, в отличие от файла в про-

грамме, который называется просто файлом.

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

Ознакомьтесь с материалом раздела «Процедуры и функции для работы с файла-

ми» базового учебного пособия «Основы алгоритмизации и программирования» и кни-

гой Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ

им. Н.Э. Баумана, 2001, стр. 190-196. Здесь приводятся основные процедуры и функции

для работы с файлами. Другие процедуры описываются применительно к конкретным ор-

ганизациям файлов.

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

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

файлов» базового учебного пособия «Основы алгоритмизации и программирования» и

книгой Иванова Г.С. Основы программирования: Учебник для вузов. – М.: Изд-во МГТУ

им. Н.Э. Баумана, 2001, стр. 201-206. Обратите внимание на то, что организация типизи-

рованного файла допускает как последовательный, так и прямой доступ к записям файла,

что существенно ускоряет обработку такого файла. Кроме того, в программе на стр.71 по-

казана проверка существования файла, которую целесообразно делать при открытии фай-

ла. Особенно это важно при создании файла, т.к. в случае открытия файла для записи су-

ществующий файл будет уничтожен.

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

Ознакомьтесь с материалом раздела «Особенности обработки текстовых файлов» ба-

зового учебного пособия «Основы алгоритмизации и программирования» и книгой Иванова

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

2001, стр. 196-201. В теоретическом материале приводятся тексты программ, содержащие

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

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

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

Ознакомьтесь с материалом раздела «Файлы без типа» базового учебного пособия

«Основы алгоритмизации и программирования». Несмотря на наличие таких возможностей

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

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

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

170

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

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

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

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

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

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

Ознакомьтесь с материалом раздела «Проектирование программ по структурам

данных» базового учебного пособия «Основы алгоритмизации и программирования». Об-

ратите внимание, что одним из вариантов в подходе МЭСИД является следующая после-

довательность шагов с преобладающим направлением от выхода к входу и от физического

к логическому:

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

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

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

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

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

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

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

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

Ознакомьтесь с материалом раздела «Работа с файлами при обработке экономиче-

ской информации» пункты «Постановка задачи» и «Проектирование программы» базово-

го учебного пособия «Основы алгоритмизации и программирования». Здесь рассматрива-

ется достаточно большая экономическая задача с подведением нескольких уровней степе-

ней итогов. Демонстрируется применение рассмотренного ранее подхода.

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

Ознакомьтесь с материалом раздела «Работа с файлами при обработке экономиче-

ской информации» пункт «Кодирование программы» базового учебного пособия «Основы

алгоритмизации и программирования». Рассмотренный пример доведен до текста про-

граммы и может служить базой при разработке текста программ, связанных с получением

ведомостей в лабораторной работе.

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

менением рассмотренного подхода.

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

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

Примерная структура меню:

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

0. Выход.

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

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

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

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

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

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

171

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. Листинги.

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

172

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

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

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

173

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

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

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. Однонаправленные (линейные) списки. Модификация списка путем добавления и уда-

ления элементов.

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

174

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

удаления элементов.

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

ления и удаления элементов.

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

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

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

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

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

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

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

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

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

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

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

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

«ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ»

О.В. Калмыкова,

Р.И. Сорока

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

и программирования

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