Язык программирования. Типы данных. Реализация основных алгоритмических структур на языке программирования. Основные этапы разработки программ

Билет № 5

Решение

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

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

В формате RGB для представления каждого пикселя используется три байта (по одному на каждый базовый цвет).

Таким образом, получаем

1024 х 768 х 3 байта = 768 х 3 Кб = 2,25 Мб

При использовании формата со сжатием получаем

2,25 Мб х 0,8 = 1,8 Мб

Язык программирования — это набор правил для описания алгоритмов решения задачи с помощью ЭВМ.

Как известно (см. билет № 12), одним из базовых принципов архитектуры современных компьютеров до сих пор остается двоичный характер любой используемой информации, причем программа обработки также представляет собой двоичный код. Тем не менее программирование в двоичных кодах — занятие необычайно утомительное и требующее глубокого знания деталей архитектуры компьютера. Для облегчения данного процесса и предназначены языки программирования, используя которые человеку проще описать алгоритм решения задачи. Переход от языковых конструкций к машинным командам осуществляет специальная программа — транслятор языка.

В соответствии с устройством языка (точнее говоря, со степенью его близости машине или человеку) различают языки низкого и высокого уровня. Языки низкого уровня, называемые еще машинными (или машинно-ориентированными) языками, — это языки, которые компьютер воспринимает непосредственно, т.е. языки машинных команд данной модели компьютера. Языки высокого уровня, напротив, ближе к естественному (человеческому); они не зависят от конкретного типа машины. Языком низкого уровня является ассемблер, а языков высокого уровня существует множество: Фортран, Алгол, Бейсик, Паскаль, Си, Ада, Пролог, Лисп, Ява и др.

Один и тот же язык программирования может быть реализован по-разному даже на одном и том же компьютере (пример: GW Basic и QBasic). В синтаксисе различных реализаций допускаются некоторые второстепенные отличия.

Одна из книг выдающегося специалиста по разработке языков программирования Никлауса Вирта (кстати, создателя языков Паскаль, Модула, Эйлер и Оберон) очень емко и глубоко названа “Алгоритмы + структуры данных = программы”. Таким образом, в теории программирования налицо две взаимосвязанные составляющие процесса решения задачи: собственно данные и инструкции по их обработке, т.е. алгоритм.

Рассмотрение начнем с первой составляющей — данных. Одно из главных свойств алгоритма состоит в том, что он по определенным правилам преобразует исходные (входные) данные в выходные (чаще говорят — в результат). При этом в процессе выполнения алгоритма может потребоваться создать некоторые рабочие (промежуточные) данные, которые будут необходимы только в ходе обработки, а после ее завершения потеряют свое значение. Кроме того, для некоторых алгоритмов аргумент может одновременно являться и результатом (например: увеличить все элементы массива вдвое), что приводит к существованию еще одной разновидности данных. Специального термина для них в учебной литературе нет, поэтому приведенное на рисунке название несколько условно.

Описанное нами четкое функциональное разделение данных имеется в любом школьном учебнике, начиная с самого первого [1]. Перечисленные выше категории у А.Г. Кушниренко в [2] названы видами величин. Как определено в [2], “вид величины показывает ее информационную роль в алгоритме”. В конкретном языке программирования каждой величине соответствует своя переменная.

Помимо вида, каждая величина в алгоритме имеет свой тип. Процитируем еще раз учебник [2]: “Тип величины показывает, какие значения может принимать величина и какие операции можно с ней выполнять”.

Кратко перечислим основные типы данных, использующихся в алгоритмических языках. Для вычислений используются различные числовые типы данных. Этот тип возник в ЭВМ самым первым, поэтому неудивительно, что он включает в себя достаточное количество разновидностей. Прежде всего назовем вещественные и целые числа. Последние могут быть как содержащими знак, так и беззнаковыми. В качестве примера вспомним в Турбо Паскале типы integer (значения от –32 768 до 32 767) и word(от 0 до 65 535). Кроме того, конкретные реализации языков программирования чаще всего содержат несколько разновидностей целых и вещественных данных, что связано с различным объемом памяти, выделяемым для них. В качестве самого простого примера назовем вещественные числа обычной и двойной точности в языке Basic. Наконец, для иллюстрации многообразия числовых данных упомянем введенный в Delphi тип currency (валюта), специально предназначенный для максимально точного хранения значений денежных сумм и вычисления процентов от них.

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

Наконец, очень важным типом данных для построения программ со сложной структурой являются логические величины. Их часто называют булевскими в честь ирландского математика Д.Буля, который был основоположником алгебры логики. Хотя логические переменные имеют всего два значения — “ложь” и “истина”, без них в языках программирования не было бы ни полноценной развилки, ни цикла.

В современных реализациях языков программирования появился особый тип данных — вариантный, который может принимать любые (числовые, символьные и т.д.) значения, причем тип текущего значения также хранится в самой переменной и может быть запрошен программистом. Подобный тип данных лежит в основе языка VBA (V isual B asic for A pplications); на его базе реализуется общий формат ячеек электронной таблицы Excel.

До сих пор мы говорили о том, какие значения могут принимать те или иные типы данных. Не стоит забывать и о второй части определения, а именно о том, какие действия можно совершать над каждым из них. Поскольку это довольно простая часть вопроса, ограничимся лишь парой примеров. Для целых и вещественных типов данных операции деления различны; они даже по-разному обозначаются: в языке Паскаль “div” и “ / ” соответственно. Или другой пример. Если для чисел вывести результат действия 123 + 45, то получится 168, в то время как для строковых значений “123” + “45” приведет к появлению на экране совсем другой результирующей строки: “12345”. Здесь, наоборот, операции с одинаковым обозначением производят над различными типами данных разные действия.

Все рассмотренные выше типы данных являются простыми. Языки программирования позволяют сконструировать и сложные типы данных, причем для этого можно объединять как несколько простых, так и другие сложные данные. Самым известным сложным типом является массив, объединяющий в себе набор данных одного типа, например, массив из целых чисел или массив из логических величин. Кстати, конструкция массив из массивов также является вполне допустимой. Более подробно сложные типы данных будут рассмотрены в билете № 7.

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

Зачем нужны типы данных? “Прежде всего они указывают, как кодировать данные в ЭВМ при их вводе и трансляции программ и как декодировать данные при их выводе и исполнении программ. …Благодаря этому кодированию становится возможным контроль над многими ошибками в программе. Зная тип переменной, транслятор может обнаружить, что переменной присваивается недопустимое значение, что к ней применяется неправильная операция… и выдать программисту сообщение об ошибке”. [3]

Для обработки данных используются различные алгоритмы. Любой алгоритм состоит из последовательности команд, которые часто по-другому называются операторами. Набор операторов в различных языках программирования, как ни странно, относительно невелик и примерно одинаков. Основу любого алгоритмического языка составляет оператор присваивания. Именно он позволяет изменять значения данных программы и тем самым получать результат решения задачи. Как метко сказано в [4], “удивительно, что в обычных языках программирования есть только один оператор, который фактически что-то делает, — оператор присваивания. Все другие операторы, такие, как условные операторы и вызовы процедур, существуют только для того, чтобы управлять последовательностью выполнения операторов присваивания”.

Чтобы получить простейшую законченную линейную программу, к операторам присваивания надо добавить какие-то средства ввода-вывода значений переменных. Ввод и вывод информации для различных языков отличаются наиболее сильно. Так, например, в языке Basic для ввода и вывода существуют особые операторы input и print, а в Паскале и Си для этой цели предусмотрены специальные системные процедуры.

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

В теории программирования строго доказывается, что для реализации любого алгоритма достаточно всего трех стандартных структур: следования (операторы выполняются в строгом соответствии с порядком написания), ветвления и цикла. Рассмотрим в качестве примера реализацию этих базовых структур в языке Паскаль.

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

Условный оператор, обеспечивающий реализацию ветвления в алгоритмах, в рассматриваемом языке программирования имеет вид:

IF < логическое выражение > THEN < оператор 1>

ELSE < оператор 2>

— причем ветвь с ELSE не является обязательной. Рассказывая о структуре условного оператора, стоит подчеркнуть два момента. Во-первых, логическое выражение совсем не обязательно представляет собой математическое неравенство типа x > 0 — оно вполне может содержать еще и булевские переменные, а также объединять несколько логических величин с помощью операций AND, OR и NOT. Во-вторых, согласно синтаксису языка в качестве операторов 1 и 2 может использоваться только один оператор. Когда для программиста этого недостаточно, разрешается создавать так называемый составной оператор, заключая необходимое количество операторов внутри служебных слов BEGIN…END.

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

IF x = 0 THEN WRITELN('Нулевое значение!')

ELSE y:= 1/x;

IF x <> 0 THEN y:= 1/x

ELSE WRITELN('Нулевое значение!');

IF n1 < n2 THEN

BEGIN

n1:= n1 + 1;

n2:= n2 - 1

END;

IF control AND (x1 > 0) AND (x2 > 0)

AND (dx > 0) THEN

WRITELN('Все параметры положительны')

(в последнем случае подразумевается, что переменная control является логической).

Рассмотрим теперь операторы цикла. Имеется их три основных вида: с предусловием, с постусловием и с параметром. Соответствующий синтаксис перечисленных разновидностей циклов приведен ниже.

WHILE < логическое выражение > DO < оператор >

REPEAT < операторы > UNTIL < логическое выражение >

FOR < параметр >:=< начальное значение >

TO < конечное значение > DO < оператор >

Правила записи логических выражений для циклов такие же самые, что и описанные выше для условного оператора. Заметим, что пара операторов REPEAT…UNTIL по смыслу эквивалентна “операторным скобкам” BEGIN…END, так что внутри данной конструкции допускается запись сразу нескольких операторов. Данная особенность цикла с постусловием является исключением из общего правила.

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

Несколько примеров операторов цикла.

WHILE dy > eps DO

BEGIN

n:= n + 1;

dy:= 1/(n * n);

y:= y + dy

END;

REPEAT READLN(s);

res:= res + s

UNTIL s = '.';

FOR i:= 1 TO n - 1 DO READLN(m[i]);

FOR s:= 'A' TO 'Z' DO WRITE(s);

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

Чаще всего при написании реальной прикладной программы (здесь речь не идет об учебных упражнениях типа “в массиве найти максимальный элемент”) требуется не только программирование. Дело в том, что взятая из жизни задача обычно не представлена в форме, немедленно готовой к решению на компьютере: приходится сначала получать ее, выбирая при этом подходящий метод. Кроме того, когда программа будет написана, введена и отлажена, потребуется провести анализ полученных числовых результатов и сделать выводы относительно исходной задачи.

В итоге можно выделить следующие основные этапы разработки программ.

1. Постановка задачи (выяснение наиболее существенных ее параметров и закономерностей, влияющих на изучаемую ситуацию; формулировка целей решения и определение необходимых для этого данных).

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

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

4. Построение алгоритма.

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

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

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

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

Проиллюстрируем описанную схему на примере некоторой конкретной задачи. Обратимся, например, к упражнению 7 на странице 77 в учебнике [1], которое формулируется следующим образом.

Найдите распределение температуры во внутренних точках тонкого однородного стержня, считая, что стержень разбит на 5 отрезков и что на концах стержня температура равна 10 и 20°. Начните с температуры 15° на всех отрезках. Выполните 5 шагов вычислений. Так же, как в случае пластины, исходите из предположения, что температура каждого отрезка равна среднему арифметическому температур соседних отрезков.

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

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

2. Процесс описывается одномерным уравнением теплопроводности с граничными условиями на концах стержня. Поскольку в физике его принято записывать в дифференциальном виде, то школьникам его представить затруднительно. К счастью, существует “облегченный” вариант, который даже с точки зрения физиков считается корректным: необходимо вместо дифференциального соотношения (для бесконечно малых величин) записать уравнение задачи в виде конечно-разностного аналога (для конечных, но малых разностей). Фактически это означает переход к следующему этапу. Поскольку данный этап в учебной задаче оказывается “свернутым”, в учебниках (см., например, [5]) его часто объединяют со следующим; подобный методический прием вполне допустим.

3. Задача формулируется в виде, пригодном для обработки на компьютере. Стержень разбивается на несколько отрезков, для каждого из которых записывается уравнение теплового баланса (подробности см. в [1]). В результате получается, что температура каждого отрезка равняется среднему арифметическому всех (в одномерном случае двух!) соседних, что описывается простой формулой

T_i = (T_{i -1} + T_{i +1}) / 2

где i — это номер отрезка, изменяющийся от 1 до некоторого значения n. Последнее является “вычислительным” параметром задачи: в исходной формулировке его нет, но, поскольку результаты от него зависят, это влияние также необходимо проанализировать.

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

Заметим, что при практической реализации метода удобно ввести два “фиктивных” граничных отрезка с номерами 0 и n + 1, в которые записать постоянные значения, взятые из условия задачи. Расчетные формулы применяются только для внутренних узлов с номерами от 1 до n.

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

5. Написать программу по готовой блок-схеме, как правило, особого труда уже не представляет. Вот как, например, она может выглядеть на языке Паскаль.

PROGRAM temp(INPUT,OUTPUT);

CONST n = 5; {количество отрезков}

t0 = 10; tn = 20; tbeg = 15;

VAR t: ARRAY [0..n + 1] OF REAL;

i, j,k: INTEGER;

BEGIN t[0]:= t0; t[n + 1]:= tn;

FOR i:= 1 TO n DO t[i]:= tbeg;

READLN(k); {количество итераций}

WRITELN('n=',n);

FOR j:= 1 TO k DO

BEGIN FOR i:= 1 TO n DO

t[i]:= (t[i - 1] + t[i + 1])/2;

WRITE(j:2);

FOR i:= 0 TO n + 1 DO

WRITE(t[i]:9:4);

WRITELN

END

END.

6. Приведем теперь несколько рекомендаций по отладке и тестированию программы. Как только очевидные ошибки синтаксиса будут устранены и программа начнет считать, выдавая на экран необходимое количество чисел, можно заняться проверкой правильности проводимых расчетов. Для этого необходимо тщательно проверить выведенные на экран значения температуры: на границах стержня она должна равняться в точности 10 и 20 градусам, а значения во внутренних точках должны заключаться в интервале между ними. Интуитивно кажется (и расчет подтверждает это), что значения ti должны нарастать слева направо. Для проверки правильности вычислений можно без компьютера провести 1–2 итерации при небольших значениях n ¹. Заметим, что для отладки вполне годятся даже весьма неразумные с физической точки зрения значения вроде n = 1.

Когда все числа будут тщательно проверены, появится некоторая уверенность в том, что получаются правильные результаты. Остается дополнительно выяснить, как на них влияют “счетные” параметры n и k. Их следует подбирать не очень большими, но такими, чтобы изменение значения в 1,5–2 раза меняло результирующие температуры в пределах практически требуемой точности (1% для учебной задачи вполне достаточно).

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

Подчеркнем, что без подобного анализа, о котором идет речь в данном пункте, решение задачи на компьютере особого смысла не имеет.

Если читателей интересует реализация описанной общей схемы на более содержательных физических примерах, советуем заглянуть в подшивку газеты и в серии “Жаркое лето” этого года найти публикацию [6].

Литература

1. Основы информатики и вычислительной техники: Пробное учебное пособие для средних учебных заведений. Ч. 1 / А.П. Ершов, В.М. Монахов, С.А. Бешенков и др.; под ред. А.П. Ершова и В.М. Монахова. М.: Просвещение, 1985, 96 с.

2. Кушниренко А.Г., Лебедев Г.В., Зайдельман Я.Н. Информатика. 7–9-е классы: Учебник для общеобразовательных учебных заведений. М.: Дрофа, 2000, 336 с.

3. Информатика: Энциклопедический словарь для начинающих / Сост. Д.А. Поспелов. М.: Педагогика-Пресс, 1994, 352 с.

4. Бен-Ари М. Языки программирования. Практический сравнительный анализ. М.: Мир, 2000, 366 с.

5. Семакин И.Г. Информатика. Базовый курс. 7–9-е классы / И.Г. Семакин, Л.А. Залогова, С.В. Русаков, Л.В. Шестакова. М.: БИНОМ, 2004, 390 с.

6. Бирих Р.В., Еремин Е.А., Чернатынский В.И. Компьютерные модели в школьном курсе физики. Информатика, 2006, № 14, с. 3–45; № 15, с. 3–13.

Дата добавления: 2015-04-23