Оригинал доступен по ссылке staff.um.edu.mt

Ханойская башня

Для наглядной демонстрации мощи динамического программирования может быть использована  игра Ханойская башня. Для получения дополнительной информации см. Документ на моей странице, в котором приведено число различных решений для игры. Чтобы проверить формулу, я написал программы в Turbo Pascal 7, которые генерируют решения в текстовом файле – проверьте, все ли решения различны и используйте имитационную модель, чтобы проверить, верны ли они. Если вы хотите, вы можете скачать эти программы. Все должно быть ясно из комментариев в исходных файлах и документа, упомянутого выше.

Error  200

Приложения, использующие модуль CRT, могут генерировать данное сообщение об ошибке при работе на очень быстрых машинах (например, Pentium 300). Причиной этой ошибки является цикл синхронизации, который совершается как часть инициализации модуля CRT. Этот цикл синхронизации подсчитывает, сколько тактов происходит в цикле, а затем это число делится на 55. Результатом этого деления является значение, которое слишком велико, чтобы поместиться в целочисленное значение. Сообщение об ошибке «Разделить на 0» – это универсальная ошибка, которая отображается при возникновении такого выхода за верхнюю границу.

Borland (сейчас называется INPRISE) на сегодня не предлагает никаких патчей для решения этой проблемы. К счастью, существуют программисты, которые их создают. Я скачал один, написанный Дэннисом Пассмором и работает он отлично. Патч содержит программу, которая преобразует исходные файлы TURBO.TPL (и TPP.TPL для защищенной цели) из \BP\BIN. В случае с Turbo Pascal изменяется только TURBO.TPL из \TP\BIN. Дэннис дал мне разрешение на его использование, так что вы можете загрузить два обновленных файла Pascal New TPP.TPL & TURBO.TPL.

Так что если у вас возникла та же проблема, загрузите новые файлы и следуйте этим инструкциям:

  • Создайте какой-нибудь каталог, скопируйте NEWTPLS.EXE в этот каталог и запустите его для расширения.
  • Если у вас Turbo Pascal, то создайте резервную копию TURBO.TPL (она находится в \TP\BIN) и скопируйте новый TURBO.TPL в \TP\BIN
  • Если у вас Borland Pascal, сделайте резервную копию TURBO.TPL и TPP.TPL (они находятся в \BP\BIN) и скопируйте новые TURBO.TPL и TPP.TPL в \BP\BIN

Программы Паскаль

Turbo Pascal не является приоритетным среди системных программистов, потому что в C и C++ вы можете писать, как правило, более быстрые и короткие программы. Тем не менее, разница невелика (преимущественно незначительна), поэтому для большинства из нас нет необходимости оставлять удобное программирование на Паскале. Компилятор Turbo Pascal невероятно быстр (на моем старом 486 Dx 33 MHz я строю (перекомпилирую) и связываю программу, состоящую из примерно 12 000 строк за 20 секунд). Четкая структура программ на языке Pascal без побочных эффектов и с прямым доступом ко всем компьютерным ресурсам делают его идеальным инструментом для всего: от введения в программирование, до расширенного системного программирования, где критические по времени разделы могут быть выражены инструкциями на языке ассемблера.

Чтобы сделать его еще более полезным, необходимо добавить управление мышью и некоторые часто используемые процедуры, такие как включение/выключение текстового курсора, псевдографики в текстовом видеорежиме, преобразование строк в верхний/нижний регистр и пр.

Если у вас имеется Turbo Pascal 7, вы можете скачать следующие файлы:

exdbase.zip – это простое приложение базы данных. Узнайте, как работать с типизированными файлами и о базовом управлении файлами.

showcloc.zip содержит процедуру, которая отображает на текстовом экране время при запуске программы. Это простая многозадачность (которая обычно не поддерживается в среде MS DOS). Программа показывает, как получить контроль над таймерным прерыванием и использовать его для обновления времени на экране.

mouse.zip – управление мышью.

others.zip – различные полезные средства, такие как общий фрейм для графики Turbo Pascal, некоторые общие процедуры, такие как преобразование строк в верхний/нижний регистр, рекурсия (Ханойская башня) и пр.

datastru.zip – примеры структур данных (A-level Computing).

search.zip – примеры поиска (A-level Computing).

sorting.zip – примеры сортировки (A-level Computing).

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

Установка

Все программы Turbo Pascal, которые вы загружаете с этой страницы – это заархивированные каталоги. Чтобы их вытащить, вам понадобится программа pkunzip.exe. Она доступна в большинстве условно-бесплатных библиотек –  попробуйте, например, Garbo. Чтобы развернуть, скопируйте загруженный файл (например, файл mouse.zip) и файл pkunzip.exe в какой-либо каталог. Тогда у вас есть два варианта как их вытащить:

pkunzip -d mouse

создает в вашем каталоге подкаталог (в данном примере MOUSE) со всеми файлами.

pkunzip mouse

не создает никакого подкаталога, все файлы помещаются в текущий каталог. Большинство каталогов содержат файлы с именем readme.pas с более подробной информацией.

Не стесняйтесь обращаться ко мне в случае каких-либо затруднений.

Объектно-ориентированное программирование

A-level Computing и аналогичные учебные курсы имеют в своей основе традиционное структурное программирование. Некоторые из них (например, Международный бакалавриат и Программа Advanced Placement) содержат введение в объектно-ориентированное программирование (ООП), которое представляет собой альтернативу традиционным методам. Этот текст служит для первого простого ознакомления с основными принципами ООП для студентов A-level Computing и аналогичных курсов.

Вот наиболее распространенные понятия ООП:

1. Алгоритм или системная динамика выражается в понятиях объектов (агентов), которые существуют параллельно и которые взаимодействуют друг с другом. Каждый объект представлен:

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

Объекты могут взаимодействовать следующими способами:

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

Проще говоря: объект = данные + команды, что называется Инкапсуляцией. Очень часто данные объекта (или часть его) скрыты, а значения могут быть доступны и изменены только с помощью (четко определенных) методов. Эта концепция называется сокрытием.

2. Подобные объекты (агенты) группируются в так называемые классы, также называемые прототипами. Класс описывает объекты, которые имеют одинаковые атрибуты и методы. Объявление класса интерпретируется как шаблон. Можно создать любое количество отдельных объектов (агентов), которые называются экземплярами объектов. Экземпляры могут отличаться значениями своих атрибутов. Необходимо четко различать класс как таковой и экземпляры объекта, сгенерированные в соответствии с объявлением класса. Класс также может быть интерпретирован как знание определенного типа объектов. Такое знание представлено частью данных и операциями, которые могут быть выполнены с данными.
Примечание: В Turbo Pascal (и в некоторых других языках ООП) классы называются «объектами». К счастью, это было исправлено в Delphi, который использует корректный термин «класс» (кстати, этот термин впервые был использован в указанном контексте 30 лет назад в языке Simula).

3. Объекты могут быть классифицированы иерархически по, так называемому, наследованию (это, пожалуй, самый важный принцип ООП, поддерживающий создание библиотек объектов на основе повторного использования кода на более низких уровнях иерархии). Очень часто вводится термин подкласс. Подкласс Y класса X наследует все атрибуты и методы класса X. Его объявление может добавлять любое количество дополнительных атрибутов и методов. Подкласс может использоваться в качестве родительского класса для других подклассов и т. д. Подкласс может интерпретироваться как более подробное знание, чем то, которое определено родительским классом. Таким образом, родительский класс представляет общие знания, которые могут быть дополнительно специализированы объявлениями подклассов в неограниченном количестве шагов. Обычно можно объявить ссылочные переменные, которые могут ссылаться на экземпляр определенного класса и на экземпляры всех его подклассов. Может оказаться желательным, чтобы конкретные методы вели себя по-разному в соответствии с текущим экземпляром объекта, на который ссылаются, и который может динамически меняться во время выполнения программы. Данная концепция, называемая полиморфизмом, поддерживается механизмом, который называется динамическим связыванием, а используемые методы называются виртуальными методами, которые могут меняться на каждом уровне иерархии.

Загрузите следующие два файла, каждый из которых содержит блоки с объектами и демонстрационные примеры их использования. Прочтите комментарии в программах, чтобы узнать о принципах ООП. Вы можете найти оба блока полезными в своих проектах.

oopwint.zip – Windows в текстовом режиме.

oopwing.zip – Windows в графике.

Проблемы с графикой?

Слишком часто я слышал вопрос: «Моя программа с хорошей графикой в школе работает, а на другом компьютере — нет. Что не так?».

Существует два случая:

І. Сначала давайте предположим, что на другом компьютере установлен Turbo Pascal 7 (версия играет роль – если у вас старые программы, то перекомпилируйте их в среде TP7). Тут могут быть три момента, которые пошли не так:

  1. Поврежденные файлы BGI и/или CHR.
  2. Неправильный параметр каталога процедуры InitGraph. Обратите внимание, что Turbo Pascal может быть установлен не в каталог \TP (а, к примеру, в \TP7), а также обратите внимание на различие между C:\TP и C:TP.
  3. Недостаточно памяти для загрузки файлов BGI и CHR – убедитесь, что емкость кучи при инициализации графики и загрузке файла векторного шрифта является достаточной.

ІІ. На другом компьютере нет Turbo Pascal. Есть два способа заставить работать файл .EXE с графикой:

  1. Переместите файл .EXE вместе с файлом .BGI и файлами .CHR и убедитесь, что они находятся в нужном каталоге – том же, что используется при вызове InitGraph.
  2. Преобразуйте файл .BGI и файлы .CHR в формат .OBJ и свяжите их с вашей программой. После этого ваш файл .EXE будет работать на любом ПК с видеокартой, совместимой с вашим файлом .BGI (практически на всех компьютерах в случае с файлом EGAVGA.BGI). Вы можете скачать linkgr.zip, содержащий блок с процедурами, которые загружают и инициализируют графику вкупе со всеми стандартными файлами OBJ, которые вам понадобятся.

Не стесняйтесь обращаться ко мне, если вышеизложенное так и не помогает.

Студенческий уголок

Это место предназначено для студентов, которые написали интересные программы и которые хотят поделиться своим опытом с другими. Все программы, содержащиеся здесь, бесплатны. Загрузите их, чтобы изучить слегка менее обыденное  программирование на Turbo Pascal. Если у вас есть интересная программа(ы) и вы готовы предложить ее(их) другим, обратитесь к автору страницы. За Ваш вклад Вам будут признательны. Итак, вот студенты, которые уже внесли свой вклад в этот «банк программ»:

Мой друг Тамер Фахури написал блок, демонстрирующий использование объектно-ориентированного программирования при решении задач управления растровыми изображениями. Особенности включают в себя следующее:

  • Поддержку сжатых/несжатых растровых изображений Windows
  • Поддержку 4,8 и 24-битных растровых изображений Windows
  • Поддержку извлечения растровых палитр
  • Стохастическое выравнивание

Ограничения (будут удалены в ближайшее время):

  • Размер изображения должен быть менее 65K

Загрузите файл bitmaps.zip, содержащий исходный файл блока.

Свен Нейман (KILLROY) – блестящий программист, особенно заинтересованный в очень быстрой графике и анимации (для этого он писал свои собственные блоки на языке ассемблера). Здесь вы можете скачать несколько программ, демонстрирующих приятную анимацию и управление с клавиатуры в текстовом режиме (hanoi.pas) и впечатляюще быструю 3D-анимацию, основанную на прямом доступе к видеопамяти (при компиляции файлов .PAS отключите проверку диапазона). Не стесняйтесь обращаться к Свену за дополнительной информацией.

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

Бесплатный Lisp-интерпретатор

Эндрю Дункан (ныне студент Мальтийского университета) разработал Lisp-интерпретатор в Turbo Pascal под названием Quicklisp в качестве своего A-level проекта и готов сделать его бесплатным. Он убежден – и он прав – что чем больше пользователей, тем быстрее будут найдены ошибки.

Quicklisp – это простой Lisp-интерпретатор, идеально подходящий для изучения языка Lisp, основ искусственного интеллекта, символьных вычислений и функционального программирования в целом. Например, он может быть подходящим инструментом для преподавателей уровня A. К его особенностям относятся:

  • Простота использования интерфейса GUI
  • Управление файлами
  • Онлайн помощь
  • Учебные пособия и примеры программ
  • Простые средства трассировки для отладки
  • Почти стандартная поддержка Lisp

Включен полный исходный код с комментариями в Pascal, который будет компилироваться на TP7 (реальный режим) или BP7 (DPMI – разрешает программы большего размера). Пожалуйста, отправьте описание каких-либо багов на adun001@um.edu.mt для того, чтобы их можно было исправить в следующей версии. Конечно же, свяжитесь с Дунканом, если у вас есть какие-либо проблемы и/или вопросы.

Вы можете скачать Quicklisp сейчас.