Технологии программирования (стр. 4 )

ТЕМА 3.3. Динамические структуры данных: списки, стек, очередь, деревья.

Динамические структуры данных: список. Организация одно-, двусвязных, кольцевых списков. Добавление и удаления узла в список. Динамические структуры данных: стек. Организация стека в массиве, в куче. Операции PUSH, POP со стеком. Определение инфиксной и постфиксной записи выражений. Алгоритм вычисления постфиксных выражений на стеке. Динамические структуры данных: очередь. Организация очереди в массиве, в куче. Операции добавления и удаления элемента очереди. Динамические структуры данных: деревья. Бинарные деревья, способы построения и обхода. Реализация программ на языке программирования Паскаль.

8. Примерная тематика курсовых работ

1. Игра "Пятнадцать". На квадратном поле размером 4 х 4 с помощью датчика случайных чисел расставлены 15 фишек с номерами от 1 до 15. Имеется одна свободная позиция. Расставить фишки по возрастанию их номеров. Передвигать фишки можно только на соседнюю свободную позицию.

2. Игра "Расстановка 16 букв". В квадрате размером 4 х 4 клетки расставить 16 букв ( по четыре буквы а, b, c, d) так, чтобы в каждом горизонтальном и в каждом вертикальном ряду любая буква встречалась только один раз.

3. Игра "100 спичек". Из кучки, первоначально содержащей 100 спичек, двое играющих поочередно берут по несколько спичек: не менее одной и не более десяти. Выигрывает взявший последнюю спичку.

4. Игра "Вращающий квадрат". Дан квадрат размером 4 х 4 клетки, в которых с помощью датчика случайных чисел расставлены буквы от А до Р. Упорядочить буквы в квадрате по алфавиту. Квадрат имеет подквадраты, которые можно вращать по часовой стрелке на одну клетку. Подквадраты имеют размер 2 х 2 и указываются номером левой верхней клетки.

5. Имеется операция, которая может быть выполнена только один раз: обмен местами двух букв.

6. Игра "Ипподром". Играющий выбирает одну из трех лошадей, состязающихся на бегах, и выигрывает, если его лошадь приходит первой. Скорость передвижения лошадей на разных этапах выбирается программой с помощью датчика случайных чисел.

7. Игра "Ним". Имеется три кучки спичек. Двое играющих по очереди делают ходы. Каждый ход заключается в том, что из одной какой-то кучки берется произвольное ненулевое число спичек. Проигрывает взявший последнюю спичку.

8. Составить программу для обучения переводу чисел из двоичной системы счисления в восьмеричную и шестнадцатеричную и обратно. Программа должна предлагать двоичное число, выбранное с помощью датчика случайных чисел, обучающийся - назвать число в восьмеричной и шестнадцатеричной системе счисления.

9. Игра "в слова". Программа выбирает слово и рисует столько прочерков, сколько букв в этом слове. Отгадать, какое слово загадано программой. В каждый год играющий указывает одну букву. Если буква названа правильно, то она подставляется вместо соответствующего прочерка. В противном случае играющий теряет одно очко. В начале у играющего 15 очков.

10. Игра "Подбери ключи". Перед играющим четыре запертые двери. Открыть все двери, располагая десятью ключами, каждый из которых может открыть несколько дверей. Предоставляется 14 попыток.

11. Игра "Ним". Имеется три кучки спичек. Двое играющих по очереди делают ходы. Каждый ход заключается в том, что из одной какой-то кучки берется произвольное ненулевое число спичек. Проигрывает взявший последнюю спичку.

12. Игра "Мост". Дан мост с арками разной ширины, в нижней строке экрана расположен мяч, которым можно управлять: мяч можно перемещать по строке, останавливать в нужной позиции строки и катить к мосту. Очки начисляются, если мяч проходит через арку.

13. Игра "Сбей самолет". По экрану летят вражеские самолеты. Цель - их сбить. В нижней строке экрана находится пусковая установка, которую можно перемещать по строке вперед и назад.

14. Игра "100 спичек". Из кучки, первоначально содержащей 100 спичек, двое играющих поочередно берут по несколько спичек: не менее одной и не более десяти, Проигрывает взявший последнюю спичку.

15. Игра "Угадай число". Один из играющих задумывает число от 1 до 1000, другой пытается угадать его за 10 вопросов вида: верно ли, что задуманное число больше такого-то числа.

16. Игра "Крестики - нолики". Написать программу.

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

9. Учебно - методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины (модуля).

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

a) Текущей аттестации:

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

b) Промежуточной аттестации:

тестирование (письменное или компьютерное) по разделам дисциплины.

Экзамен в конце 2 семестра (к экзамену допускаются студенты после сдачи всех лабораторных работ, решения всех задач контрольных работ, выполнения самостоятельной работы, выполнения курсовой работы).

Текущий и промежуточный контроль освоения и усвоения материала дисциплины осуществляется в рамках рейтинговой (100-бальной) системы оценок.

Пример тестового задания по теме «Тип множество»:

1. Какие из следующих конструкций являются множествами (в смысле языка Паскаль), а какие нет?

1). [ 13, 11, 7, 0 ]

2). [ 1..2, 115, 101 ]

3). [ 7..15, 11..28 ]

4). [ '?', '?' ]

5). [ 0..0 ]

6). [ true..false ]

7). [ 2, sqrt(9) ]

8). [ '+', '=', '>=' ]

9). [ [ ], [ 5 ] ];

10). [ odd(9), 0<2 ]

Пример лабораторного задания

1. Дан фрагмент программы:

type река = record

название: string[20];

длина: word

end;

список: array [1..10] of река;

var C: список;

1). найдите самую длинную реку из списка С и напечатайте её название;

2). найдите количество рек с длиной между 2000 км и 5000 км.

Для решения задачи нужно написать:

· процедуру InputRiver для ввода информации о реках;

· функцию NMaxLenRiver, которая находит номер реки с максимальной длиной;

· функцию CountRiver для подсчёта числа рек с длиной между 2000 км и 5000 км.

Пример контрольной работы

1) Дан текстовый файл. Для каждой строки распечатайте слово наибольшей длины. Если их несколько, то распечатайте все.

2) В типизированном файле хранятся вещественные числа.

a) запишите их в новый файл в отсортированном порядке;

b) запишите в новый файл одинаковые;

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

Вопросы к экзамену

1. Тип множество. Операции со множествами: объединение, пересечение, разность, сравнение, вхождение.

2. Тип запись. Оператор присоединения With. Записи с вариантами.

3. Файловые типы. Процедуры и функции для работы с файлами любых типов: Assign, Reset, Rewrite, Close, Rename, Erase, Eof, IoResult. Обработка ошибок ввода-вывода. Опции компиляции {$I-} {$I+}

4. Файлы типизированные. Процедуры и функции для работы с типизированными файлами: Reset, Rewrite, Read, Write, Filesize, FilePos, Seek, Truncate

5. Файлы текстовые. Процедуры и функции для работы с текстовыми файлами: Reset, Rewrite, Append, Eoln, SeekEoln, SeekEof, Read, Readln, Write, Writeln, SetTextBuf. Cтандартные файлы ввода-вывода Input, Output.

6. Файлы нетипизированные. Процедуры для работы с нетипизированными файлами: Reset, Rewrite, BlockRead, BlockWrite. Особенности работы процедур BlockRead, BlockWrite с четвертым параметром. Логические устройства для стандартных аппаратных средств.

6. Модули Pascal. Структура модуля. Режимы компиляции Compile, Make, Build.

7. Понятие адреса памяти, сегмента, смещения, нормализованного адреса.
Распределение памяти CMA: cегмент кода программы, сегмент данных, стек, динамическая память (куча). Типы указатель (Pointer) и ссылка (^ тип).

8. Типы указатель (Pointer) и ссылка (^ тип). Операции, процедуры и функции для работы с адресами: @, Addr, Seg, Ofs, Ptr. Допустимые операции с указателями и ссылками. Процедуры для управления кучей: New, Dispose, GetMem, FreeMem.

9. Управление кучей. Процедуры и функции: Mark, Release, MaxAvail, MemAvail.

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

10. Организация односвязного списка, добавление и удаление узла в список.

11. Организация двусвязного списка, добавление и удаление узла в список.

12. Организация кольцевого списка, добавление и удаление узла в список.

13. Динамические структуры данных: стек. Организация стека в массиве, в куче. Операции со стеком.

14. Динамические структуры данных: очередь. Организация очереди в массиве, в куче. Операции добавление и удаление элемента очереди.

15. Динамические структуры данных: бинарные деревья. Деревья поиска.

10. Образовательные технологии

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

аудиторные занятия:

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

активные и интерактивные формы

компьютерное моделирование и анализ результатов при выполнении лабораторных работ

внеаудиторные занятия:

выполнение дополнительных заданий разного типа и уровня сложности при выполнении лабораторных работ, подготовка к аудиторным занятиям, изучение отдельных тем и вопросов учебной дисциплины в соответствии с учебно-тематическим планом, составлении конспектов. Подготовка индивидуальных заданий: выполнение самостоятельных и контрольных работ, подготовка ко всем видам контрольных испытаний: текущему контролю успеваемости и промежуточной аттестации; индивидуальные консультации.

11. Учебно-методическое и информационное обеспечение дисциплины

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

1) Немнюгин С. А. Turbo Pascal. Программирование на языке высокого уровня: Учебник для вузов. 2-е изд. Спб.: Питер, 20с.

2) Программирование на языке Паскаль: задачник / под ред. СПб: Питер, 20с.

3) Степанов . 3-е изд. Спб.: Питер, 20с.

4) Фаронов Паскаль 7.0. Начальный курс. Учебное пособие. М. Нолидж, 19с.

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

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

2) Учитесь программировать / Пер. с англ.; под ред. и с предисл. . М.: Финансы и статистика, 19с.

3) Могилев А. В. и др. Информатика: учебное пособие для студ. пед. вузов. М.: Изд. центр «Академия», 20с.

4) Программирование алгоритмов обработки данных / , , . – СПб: БХВ - Петербург, 20с.

5) Тимошевская по программированию на языке Pascal: Учеб. пособие. Томск: Том. гос. ун-т систем управления и радиоэлектроники, 20с.

6) Особенности программирования на Borland Pascal. Киев: Диалектика, 19с.

11.3. Программное обеспечение и Интернет – ресурсы:

1. Воробьева программирования (2008), режим доступа: http://study. *****/ по паролю.

2. Киприна программирования (2010), режим доступа: http://study. *****/ по паролю.

12. Технические средства и материально-техническое обеспечение дисциплины (модуля)

При освоении дисциплины для проведения лекционных занятий нужны учебные аудитории, оснащённые мультимедийным оборудованием, для выполнения лабораторных работ необходимы классы персональных компьютеров с набором базового программного обеспечения разработчика - системы программирования на языках Borland Delphi.