Министерство образования РФ

Тверской государственный университет

Кафедра информатики

А.В. Масюков

ЛЕКЦИИ ПО ИНФОРМАТИКЕ

(Краткий конспект)

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

«прикладная математика и информатика»,

«математические методы в экономике»

Тверь 2002 Настоящее пособие посвящено принципам программирования и базовым алгоритмам, а не конкретному языку или системе программирования (используется Borland Pascal для MS-DOS). Основное внимание в настоящем пособии уделяется вопросам, которые с трудом воспринимаются студентами. Для успешного прохождения курса необходимо запрограммировать и отладить решения упражнений настоящего пособия или 100 аналогичных задач.

СОДЕРЖАНИЕ

§1 ОСНОВНЫЕ ПОНЯТИЯ §2 СИНТАКСИС, ПРОСТЫЕ ТИПЫ, ОПЕРАТОРЫ §3 ПРОЦЕДУРЫ И ФУНКЦИИ

§4 СИСТЕМЫ СЧИСЛЕНИЯ, ФОРМАТЫ ДАННЫХ, БИТОВЫЕ ОПЕРАЦИИ

§5 ТИПЫ ARRAY, RECORD, STRING §6 ХЕШИРОВАНИЕ

§7 НЕТИПИРОВАННЫЕ ПАРАМЕТРЫ, ПРИВЕДЕНИЕ ТИПА, УКАЗАТЕЛИ,

ОПЕРАТОР ВЗЯТИЯ АДРЕСА, ДИНАМИЧЕСКИЕ МАССИВЫ

§8 СТЕК, ПОСТФИКСНАЯ ЗАПИСЬ, БЫСТРАЯ СОРТИРОВКА,

СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ, МЕТОД ВЕТВЕЙ И ГРАНИЦ, РЕКУРСИЯ

§9 ФАЙЛЫ. ВНЕШНИЕ СОРТИРОВКИ. HEAPSORT. §10 BMP-ФАЙЛЫ. ЭЛЕМЕНТЫ КОМПЬЮТЕРНОЙ ГРАФИКИ. §11 БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ §12 ДИНАМИЧЕСКИЕ СПИСКИ §13 ДИНАМИЧЕСКИЕ ДЕРЕВЬЯ §14 ПРОПЕДЕВТИЧЕСКИЙ ОБЗОР ЯЗЫКА СИ ЛИТЕРАТУРА §1 ОСНОВНЫЕ ПОНЯТИЯ Компьютер – это устройство для хранения, обработки и визуализации информации. Основные части компьютера: центральный процессор (CPU) и оперативная память (RAM – Random Access Memory – произвольного доступа).

Процессор имеет инструкции (команды) изменения значений ячеек памяти (арифметических операций, сравнения, и т.д.). Адрес (иначе, указатель) – это номер ячейки памяти (как правило, относительно некоторого стартового адреса). Процессор устроен так, что считывает и выполняет инструкцию, находящуюся по адресу, который хранится на специальном регистре процессора (instruction pointer). При этом значение instruction pointer увеличивается на размер инструкции, если очередная команда не является командой перехода (goto), изменяющей значение instruction pointer специально. Содержимое оперативной памяти теряется при выключении компьютера, для хранения информации используются внешние носители: магнитные и оптические диски. Чтение-запись диска означает копирование информации между диском и RAM.

Как правило, диски организованы иерархично – как деревья папок (folder, directory, catalogue), листьями являются файлы – именованные области данных диска. CPU способен посылать сообщения периферийным процессорам (диска, клавиатуры, и т.д.).

Контроллер диска может непосредственно читать-писать RAM. Графическую плату (карту) можно рассматривать, как самостоятельный (специализированный) компьютер со своим процессором (графический процессор может быть мощнее центрального) и своей памятью, содержимое которой отображается на экране монитора. Компьютер может иметь различную периферию и аксессуары (коврик для мыши, тапочки для таракана). Программа – это 1) файл, содержащий инструкции процессора, которые выполняются после загрузки в память, или 2) исходный текст на некотором языке программирования. Компилятор – это программа трансляции (перевода) исходного текста программы в выполняемый файл (инструкции процессора). Операционная система (ОС) – это программа, которая поддерживает файловую систему дисков и управляет процессами (загружает другие программы). Любая ОС имеет консоль, на которой отображается команда ОС, набираемая на клавиатуре. Имеются команды просмотра содержимого папки, копирования файлов, запуска программ. Некоторые юзеры могут пользоваться только графическим интерфейсом (надстройкой ОС) и никогда не видеть консоль.

Программа, скомпилированная для одной платформы, не может выполняться на другой: процессоры имеют различные наборы инструкций. На одном компьютере могут быть две ОС, но каждая имеет свою файловую систему и свой формат выполняемых файлов. Некоторая переносимость программ имеется только на уровне исходных текстов. Следует различать стандарт языка программирования (системнонезависимый) и его конкретную реализацию (компилятор). В курсе информатики мы используем Borland Pascal для MS-DOS (далее – BP), являющийся расширением стандарта языка Паскаль (автор – Н. Вирт). BP позволяет изучать основные принципы программирования не тратя много времени на изучение среды программирования (очень простой). Считается, что разработка программного продукта в незнакомой среде (и на новом языке программирования) требует от настоящего программиста всего на 10% больше времени.

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

(Разные компиляторы выдают различный код.) Операторы применяются к переменным, которые могут принимать числовые значения или быть более сложного типа. Например, файловые переменные являются системно-зависимыми структурами, которые могут оставаться неизвестными для программиста высокого уровня.

Переменными языков сверхвысокого уровня могут быть, например, системы дифференциальных уравнений (Maple, MatLab). Переменная суть адрес того места, где хранится ее значение. Точнее, программа-транслятор для каждой переменной должна хранить кортеж: (идентификатор, адрес, тип). Тип переменной определяет применимые к ней операции, и ее формат: сколько байтов, начиная с адреса переменной, занимает ее значение и как оно закодировано. Некоторые задачи можно решать на языках высокого уровня, не зная системно-зависимых форматов, или внутреннего представления данных. Однако, рассмотрение примеров форматов необходимо для понимания работы системных программ и компьютера в целом.

Идентификатор, или имя переменной, есть последовательность букв и цифр, начинающаяся с буквы. Это определение можно представить в виде синтаксической диаграммы:

Другим способом формализации синтаксиса являются формы Бэкуса-Наура (БНФ), например:

Здесь квадратные скобки означают то, что может повторяться (возможно, ноль раз), вертикальная черта – или. Компилятор Паскаля не различает строчные и прописные буквы. Рекомендуется давать переменным имена вроде IndexOfRow, IndexOfColumn вместо i и j, для ускорения разработки программ.

§2 СИНТАКСИС, ПРОСТЫЕ ТИПЫ, ОПЕРАТОРЫ

В языке Паскаль все переменные должны быть объявлены заранее в блоке описаний, который начинается с зарезервированного слова var (от слова variables – переменные) и вслед за каждым списком переменных, разделенных запятыми, следует двоеточие и тип этих переменных. Программа начинается с begin и заканчивается end с точкой, между begin и end программы находятся операторы, разделяемые точкой с запятой. Простейшая паскаль-программа представляется в виде синтаксической диаграммы:

Если двигаться в диаграмме по стрелкам (выбирая любой вариант разветвления), мы получим синтаксически правильную программу. Несколько десятков синтаксических диаграмм однозначно определяют грамматику языка программирования (и задачу компилятора). Синтаксически правильная программа может содержать ошибки, не обнаруживаемые компилятором. Считается, что тестирование (обнаружение ошибок) и отладка (их локализация и исправление) занимают половину времени разработки. При этом самые распространенные (107 копий) и самые дорогие (107 USD) программные продукты (ПП) не свободны от жучков (bugs). В приведенной выше диаграмме предполагается существование всего двух типов: integer (целые) и real (вещественные, или с плавающей точкой, могут хранить дробные числа). Синтаксис оператора присваивания:

подчеркивает, что это не математическое равенство – во время работы программы вычисляется выражение, стоящее в правой части (с использованием значений переменных, входящих в выражение), и результат вычислений записывается по адресу переменной, стоящей в левой части оператора. При этом тип выражения должен совпадать, или быть совместимым с типом этой переменной. В языке Паскаль целой переменной нельзя присвоить выражение типа real, и результат деления целых выражений имеет тип real. Для целочисленного деления имеется операция div (деление без остатка), mod – остаток от деления нацело. Рассмотрим пример программы с ошибками (фигурных скобки {} для комментариев):

var i,j : integer; {Блок описания переменных} x:real;

begin {Начало программы} i:=3.14; {ошибка несоответствия типов} readln(x); {программа будет продолжена после ввода числа} x:=3.14;

i:=trunc(x); {i получит значение 3, отбрасывание дробной части} i:=4/2; {ошибка, 4/2 есть 2.0 (в языке Паскаль)} i:=5 div 2;

j:=5 mod 2;

x:=i; x:=x*x;

i:=i+1;

{ в выражении может присутствовать переменная, стоящая слева от := } k:=1; {ошибка, переменная k не объявлена} writeln(‘i=’, i:2, ‘j=’, j:2, ‘x=’, x:5:2, ‘Press Enter’);

readln; {оператор ввода без списка ввода} end. {Конец программы} Текст, который в операторе вывода writeln находится в апострофах, просто копируется на экран (проверьте), а значения переменных списка вывода преобразуются в символьную десятичную запись.

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

Заметим, что else (иначе) может отсутствовать и перед else разделитель (точка с запятой) не ставится. В качестве логического выражения могут выступать пересечения (and) и объединения (or) равенств и неравенств. Например, if (i mod 2 0) or (ib then b:=a; writeln(a,b);

2) if i=j then if j>k then x:=2 else x:=3;

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

Структура программы отображается в исходном тексте отступами. Стиль отступов может быть различным, например, if ……. then или if …… then begin else begin Главное, отступы в исходном тексте показывают вложенность, которая может быть также изображена в виде дерева:

Если бы не было циклов, скорость процессора была бы бесполезна – мы не можем писать 106 операторов в секунду. А с помощью вложенных циклов лаймер (lame under the hat) может загрузить самый мощный процессор бессмысленными действиями надолго (если не навсегда). Основным оператором цикла является while (пока), его диаграмма такова:

Тело цикла (то есть оператор, стоящий после do; обычно это составной оператор) выполняется повторно, пока условие, стоящее после while, истинно. Например, while TRUE do;

есть бесконечный цикл (тело цикло – пустой оператор, а условие цикла – логическая константа ИСТИНА). Следующий цикл i:=0; {инициализация переменной (счетчика) цикла} while i2 do не будет выполняться ни разу. Условие while проверяется перед выполнением тела цикла.

Действие цикла можно изобразить с помощью следующей схемы:

Хотя в языке Паскаль имеется также цикл for, цикл while является основным (используется в 90% случаев). Поэтому я советую на этапе изучения языка пользоваться только while. Другая рекомендация состоит в отказе от использования операторов continue (возврат на проверку условие цикла) и break (выход из цикла), которые отсутствуют в стандарте языка и заимствованы в BP из Си. Конечно, в некоторых (простейших случаях) конструкция for удобнее, но надо научиться сочинять сложные условия цикла. Операторы continue и break очень сильны, но их лучше оставить на случай переструктурирования (усложнения) программы. Следующая программа находит наибольший общий делитель двух чисел, используя наивный алгоритм (вычитание 1 пока оба числа – и одно и другое – не разделятся без остатка):

var x,y,z: integer;

begin writeln(‘введи два числа’); readln(x,y);

if x1) and b;

Упражнение. Составьте синтаксические диаграммы арифметических и логических выражений. Проверьте, что диаграммы порождают только допустимые выражения и все допустимые выражения.

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

var i:integer;

begin writeln('Чтобы получить код символа, сложите числа строки и столбца');

i:=0; write(' ');