Практика программирования

       

Практика программирования (Бейсик, Си, Паскаль)

Почти одновременно с появлением первых ЭВМ системные программисты стремились переложить на плечи ЭВМ наиболее рутинную работу, сопровождавшуюся многочисленными ошибками и описками. Первые элементы автоматизации процесса написания программ были связаны с заменой числовых кодов машинных операций их мнемоническими символьными обозначениями. Например, команда сложения содержимого двух ячеек памяти вместо сугубо числового кода 01 0100 0101 0102 превращалась в более осмысленное действие типа ADD 0100,0101,0102. Почти сразу же стало ясно, что использование естественной числовой нумерации ячеек памяти становится неразумной преградой между обозначениями переменных решаемой задачи и их эквивалентами в виде числовых адресов. Почему бы не возложить на специальную программу чисто механическую работу по замене символьных обозначений исходных и промежуточных данных задачи на их машинные адреса? И тогда очередной пункт алгоритма, выражавшийся простой формулой z = х + у, превращался в достаточно наглядную и близкую по смыслу команду ADD X,Y,Z. На первом этапе развитие этих идей сдерживало отсутствие устройств ввода/вывода, которые могли бы обрабатывать алфавитно-цифровую информацию. Как только аппаратные средства позволили преодолеть это препятствие, неотъемлемой частью программного обеспечения ЭВМ стали системы, получившие название Автокодов или Ассемблеров.

Введение
К числу первых алгоритмических языков, получивших достаточно широкое распространение, относятся Фортран (FORTRAN — от FORmula TRANslation, "трансляция формул") и Алгол (ALGOL — от ALGOrthmic Language, "алгоритмический язык"). Первый из них родился в недрах фирмы IBM в 1954 г. и активно поддерживался этим наиболее могущественным концерном по производству средств вычислительной техники.

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

Внешнее и внутреннее представление числовых данных
Под внешним представлением числовой информации подразумеваются способы записи данных, используемые в текстах программ, при наборе чисел, вводимых в ЭВМ по запросу программы, при отображении результатов на экране дисплея или на принтере. Кроме естественного представления числовых констант в виде целого или вещественного числа, языки программирования допускают различные добавки в начале ("префиксы") или конце ("суффиксы") числа, определяющие способы преобразования и хранения данных в памяти компьютера.



Символьные данные и их внутреннее представление
Символьная (текстовая) информация — самый простой тип данных с точки зрения его представления в памяти ЭВМ. Каждому символу текста в памяти соответствует байт с 8-разрядным кодом этого символа в том или ином стандарте. Буквам латинского алфавита, цифрам, знакам операций и различным разделителям (скобки, точки, запятые и т. п.) в некотором смысле повезло больше, т. к. их кодировка практически универсальна. Она предложена фирмой IBM и составляет первую половину большинства 8-разрядных кодировочных таблиц, используемых в разных странах.

Объявление массивов
В QBasic для объявления массивов и одновременного отведения памяти под хранение их элементов используется оператор DIM: DIM А(10),В(2 ТО 8,3 ТО 5),С(3,2,6) В простом объявлении указывается максимальный индекс и, поскольку минимальный индекс по умолчанию равен 0, то в массиве А, например, содержится не 10, а 11 элементов. Конструкция "qq то kk" позволяет одновременно задать и минимальный, и максимальный индексы.

Задачи,советы и ответы
В простейшем варианте процедура (функция) считается рекурсивной, если она пытается вызвать сама себя. Математики нередко прибегают к рекурсивному определению функций: n! = n*(n-1)! Естественно, что при таком хождении "по кругу" должно быть предусмотрено условие выхода, иначе вычислительный процесс может продолжаться бесконечно долго. В примере с факториалом тело процедуры на Паскале может выглядеть следующим образом: if n 2 then fact:=l else fact:=n*fact(n-1);

Оформление и вызов программных единиц в системе QBasic
Во входном языке системы QBasic нет специальных средств для выделения головной программы. Поэтому все, что не принадлежит специальным образом оформленным подпрограммам или функциям, относится к тексту головной программы. Дополнительной особенностью Бейсика является возможность использования как внешних, так и внутренних программных единиц. Тексты последних непосредственно входят в состав головной программы или тела любой другой программной единицы.

Основные типы файлов в системе QBasic
Система QBasic поддерживает работу с файлами трех типов — строковыми, записеориентированными и двоичными. Приведенные термины не являются общеупотребительными, однако они достаточно точно отражают формат хранения данных в дисковых файлах.

О мониторах и графических системах
В графическом режиме экран напоминает миллиметровку, т. е. разбит на довольно много мелких клеток (сторона клетки порядка 0,3—0,4 мм для мониторов с 14—15-дюймовыми экранами). Такие клетки называют пикселами (pixel — от picture's element, "элемент рисунка") и каждый из них может быть окрашен в тот или иной цвет. Самый высокий графический режим, поддерживаемый нашими системами программирования, соответствует стандарту VGA — 640 точек по горизонтали, 480 — по вертикали, 16 цветов из довольно большого числа (256 К) возможных цветовых оттенков.

Немного истории
Наиболее стабильным длительным промежутком времени с точки зрения ученых, ведущих астрономические наблюдения, является тропический год — интервал между моментами прохождения центра солнца через так называемую точку весеннего или осеннего равноденствия. Наблюдается это явление 21 марта и 23 сентября в обычный год и со смещением на один день — в високосный год. В этот момент лучи солнца падают на экватор отвесно и продолжительности ночи и дня совпадают.

Управление мышью
В составе штатных поставок систем ТС, ТР и QBasic отсутствуют средства управления мышью, а без этого манипулятора на порядок снижается ценность игровых и диалоговых программ. Непосредственную работу с мышью осуществляет системная программа — драйвер мыши, — загружаемая одновременно с загрузкой операционной системы MS-DOS или входящая в состав Windows.

Программирование на языке Pascal

Наш курс посвящен изучению не только языка Pascal, но и некоторых алгоритмов, решающих наиболее известные задачи программирования, поэтому начнем мы со знакомства с некоторыми основополагающими понятиями.
Алгоритм - это последовательность действий, которые необходимо выполнить, чтобы решить поставленную задачу.
Программа же представляет собой набор команд на языке, понятном исполнителю, реализующий некоторый алгоритм. В нашем случае исполнителем является компьютер, а языком программирования будет язык высокого уровня Pascal. К сожалению, любой язык высокого уровня удобен только человеку, пишущему или отлаживающему программу, но совершенно непонятен компьютеру. Программа на таком языке называется исходным текстом и хранится во внешнем файле с расширением .pas.

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

Типы данных языка Pascal
Компиляторы языка Pascal требуют, чтобы сведения об объеме памяти, необходимой для работы программы, были предоставлены до начала ее работы. Для этого в разделе описания переменных (var) нужно перечислить все переменные, используемые в программе. Кроме того, необходимо также сообщить компилятору, сколько памяти каждая из этих переменных будет занимать. А еще было бы неплохо заранее условиться о различных операциях, применимых к тем или иным переменным

Операторы ветвления
К операторам, позволяющим из нескольких возможных вариантов выполнения программы (ветвей) выбрать только один, относятся if и case.

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

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

Ввод и вывод: файлы
В первой лекции мы уже рассматривали ввод информации с клавиатуры и вывод ее на экран1). Однако процесс ввода с консоли весьма трудоемок, а результат вывода на консоль - недолговечен. К счастью, существует более удобный способ записывать, хранить, пересылать и по необходимости считывать информацию из постоянной памяти компьютера. Для этого применяются файлы.

Записи
Продолжая изучение структурированных типов данных, переходим к записям. Как и массивы, записи являются структурами прямого доступа, однако, в отличие от массивов, могут хранить элементы, относящиеся к разным типам данных. Таким образом, запись - это вектор, компоненты которого (поля) могут относиться к разным типам данных.

Подпрограммы
Весьма поэтичное объяснение понятия подпрограмма дал В.Ф. Очков: "Подпрограмма - это припев песни, который поют несколько раз, а в текстах песен печатают только один раз"1). В самом деле, если есть необходимость многократно совершать одни и те же действия, то вполне логично описать их единожды, а потом лишь ставить на них ссылку. Именно такой смысл имеет использование подпрограмм.

Динамические структуры данных
Динамические структуры данных служат полезным дополнением к стандартным структурам, уже определенным в языке Pascal. Динамическими они называются потому, что их элементы создаются и уничтожаются "на ходу" - в процессе работы программы.

Статически выделяемая память
Для того, чтобы лучше понять специфику динамически выделяемой памяти, рассмотрим сначала ее "антипод" - память, распределяемую статически. Такое выделение памяти используется всякий раз при объявлении "обычных" переменных в разделе var. Каждая переменная обладает двумя атрибутами: именем и описанием.

Чуть-чуть истории
Теория графов - довольно молодая наука (по сравнению, скажем, с геометрией). В 1736 году Санкт-Петербургская академия наук опубликовала труд Леонарда Эйлера, где рассматривалась задача о кенигсбергских мостах ("Можно ли, пройдя все городские мосты ровно по одному разу, вернуться в исходную точку?"). Это была первая работа по будущей теории графов.

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

Модульность программ
Простейшая модульность программы может достигаться за счет применения процедур и функций, однако этого не всегда достаточно. Если все подпрограммы содержатся в одном файле, то исправление единственной ошибки в какой-либо подпрограмме приведет к неизбежной перекомпиляции всего кода. А при современных размерах программ компиляция может длиться даже не минуты, а часы.

Текстовый режим
В текстовом режиме единицей вывода информации служит символ. На экране каждый символ занимает одно знакоместо - прямоугольный участок размером 8х8 пикселей (зерен экрана). Во весь экран помещается 80х25 знакомест.

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