Программирование на ЭВМ

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

2000 г.

    Под программированием в настоящее  время понимается теория и практика создания программ для ЭВМ. Появившись всего около 50 лет назад, ЭВМ проникают весьма активно во все стороны жизни человечества – от управления космическими кораблями и целыми отраслями промышленности до настольных игр.

    Сам принцип программного управления открыл еще в 1823 г. профессор Кембриджского университета Ч. Бэббидж в проекте своей “Аналитической машины”, а первым программистом была дочь Байрона, леди Лавлейс. Однако впервые ЭВМ с хранимой в памяти программой появилась в 1949 г. в Англии (машина EDSAC), затем в США, в СССР (МЭСМ) – в 1952 г.

    Созданию  универсальных ЭВМ предшествовали изобретения  в области  механических счетных устройств, начиная с  Паскаля (1645 г.) и Лейбница (1694 г.); открытия в математике: “двоичная арифметика” Лейбница, математическая логика Джорджа Буля (1847 г.), теория алгоритмов (сложилась к 40-м годам 20-го века). Кроме того, появление ЭВМ было бы невозможно и без развития средств электросвязи, радиотехники и электротехники.

    За  время существования профессии  программиста сущность его труда изменилась коренным образом. В 50-х годах программы писали в командах ЭВМ (в “машинных кодах”). При этом вся информация переводилась в двоичную систему счисления. Это очень тяжелый и напряженный труд, требующий от человека особой аккуратности. Облегченно вздохнули программисты при появлении в 1956 г. специального языка для решения вычислительных задач. Это был FORTRAN (Formula Translator). С тех пор были разработаны другие, более совершенные языки, или специализированные применительно к какой-то конкретной области: КОБОЛ, АЛГОЛ, ПЛ/1, ЛИСП, СИМУЛА, ПАСКАЛЬ, СИ, АДА, ПРОЛОГ и др.

    Неузнаваемо изменилась и вычислительная техника: от первых ЭВМ на радиолампах, затем  – на транзисторах, до современных  машин на интегральных схемах. Уже выпускаются ЭВМ на одном кристалле кремния 6х6 мм, схема которых эквивалентна сотням тысяч радиодеталей.

    Меняется  в последние годы и методика обучения программированию. Если раньше основное внимание уделялось изучению систем команд ЭВМ, то сейчас главным  становится освоение наиболее прогрессивных методов разработки алгоритмов решения задач и их проверки на ЭВМ. Наиболее перспективной является методология (технология) структурного программирования.

 

1. ОСНОВЫ АЛГОРИТМИЗАЦИИ

    1.1. Понятие алгоритма

    Очевидно, знания, полученные при изучении курса “Информатика” в школе, позволяют ответить на вопрос: “Что такое алгоритм?”

    Понятие алгоритма является одним из основных понятий современной математики. Слово происходит от имени узбекского математика IX в. Мухаммеда из Хорезма (по-арабски – “Аль-Хорезми”). Его работы по арифметике и алгебре были переведены на латинский язык в XII в. и оказали большое влияние на развитие математики в Европе. Сформулированные им правила выполнения четырех арифметических действий получили название “алгоризм”, которое впоследствии трансформировалось в “алгоритмус”, затем в “алгорифм” и “алгоритм”. Однако еще раньше Евклид открыл правило нахождения наибольшего общего делителя (НОД) двух целых чисел, явившееся первым алгоритмом.

    Интуитивное понятие алгоритма, которым люди пользуются уже много лет (но есть еще и строгое), можно выразить следующим образом:

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

    Здесь мы ввели понятие действия. В дальнейшем будем считать тождественными понятия

    действие  ≡ инструкция ≡  оператор.

    Действия (инструкции, операторы) выполняются  некоторым исполнителем. Для нас

    исполнитель ≡ процессор.

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

  1. действия должны быть понятны исполнителю;
  2. разные исполнители должны одинаково понимать одни и те же  действия.

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

    Алгоритм  перехода улицы со светофором:

         1) ждать, пока не загорится  зеленый свет;

         2) перейти половину улицы и  при этом смотреть налево;

  1. перейти вторую половину улицы и при этом смотреть направо.

    Алгоритм  не очень точен. Очевидно, п.п. 2) и 3) содержат еще и подразумеваемые действия на случай, если вдруг появится машина. Следовательно, алгоритм будет по-разному выполняться разными исполнителями.

    Богатым сборником алгоритмов является кулинарная книга. Например, следующий алгоритм.

    Как варить кашу:

         1)  поставить на огонь воду;

        2)  ждать, пока не закипит;

         3)  посолить;

        4)  насыпать крупу;

         5)  ждать, пока не закипит;

        6)  убавить огонь;

  1. ждать 20 минут.

    Нас пока будут интересовать в основном алгоритмы для производства вычислений или вычислительные алгоритмы. Будем в дальнейших рассуждениях иметь в виду именно их. Для таких алгоритмов действие – это действие над численными величинами.

    Один  и тот же алгоритм может быть записан  несколькими способами. В практике программирования распространены:

  • словесная запись на естественном языке;
  • схемы алгоритмов, блок-диаграммы;
  • решающие таблицы;
  • алгоритмические языки (формальные языки).

    Первый, второй и третий способы предназначены  для человека, последний – для исполнителя-машины. Такая  запись называется программой.

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

    1.2. Элементы структурного  программирования

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

    Рассмотрим  эти конструкции на примерах алгоритмов для вычислений по формулам. 

    Пример 1. Х = А2-1.      вход – А,

                                                                выход – Х

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

  1. Задать значение для А.
  2. Умножить А на А, запомнить результат.
  3. Из результата п.2 вычесть 1, запомнить результат в переменной Х.

    Здесь у нас появилось важное действие – запоминание. Будем называть его  присваиванием. Это фундаментальное понятие. Оно связано с понятием память. Любой исполнитель имеет память: человек – лист бумаги или клетки головного мозга, ЭВМ – ячейки памяти.

            Чтобы  различать разные значения, их  располагают в разных участках  памяти. Под переменные значения отводится свободное место в памяти. Следовательно, можно сказать: ”Результат присвоить переменной Х”.

    Этот  пример определяет нам первую базовую  конструкцию структурного программирования – следование: если в записи алгоритма друг за другом написаны несколько действий, то они будут выполняться последовательно.

    Последовательный  алгоритм – такой, в котором действия выполняются в том порядке, в каком они написаны (в естественном порядке).

    Однако  такой последовательности не всегда достаточно для выполнения алгоритма. Рассмотрим следующий пример.

    Пример 2.

       0, x ≤ 0 вход - x,

          f =   выход – f.

                x2, x > 0 

    Записать  алгоритм вычисления f можно следующим образом.

  1. Задать значение х.
  2. Если х ≤ 0

    то  2.1. задать f = 0

    иначе  2.2. задать f = x * x.

    Получили  новую конструкцию, которая задает разветвление в порядке выполнения действий. Такая конструкция называется условной (соответственно алгоритм – условным) или конструкцией ЕСЛИ – ТО – ИНАЧЕ, по-английски IF – THEN – ELSE. Запись в общем виде:

    ЕСЛИ  условие

          ТО последовательность действий 1

          ИНАЧЕ последовательность действий 2. 

    Упрощенная  или усеченная форма:

    ЕСЛИ  условие

          ТО последовательность действий. 

    Пример 3. Подсчитать сумму нечетных чисел от 1 до 25. 

      вход –  пустой,

      выход – S. 

    Алгоритм  вычисления S .

  1. Задать S равным 0.
  2. Задать n равным 0.
  3. Пока n ≤ 12 выполнять

          3.1.  к S добавить 2*n + 1

          3.2.  увеличить n на 1

      Алгоритм будет работать до  тех пор, пока выполняется условие  п.3.

    Здесь мы получили третью базовую конструкцию  – циклическую. Она означает следующее: пока истинно некоторое условие, – делай то-то и то-то.  Называется она конструкцией ПОКА – ДЕЛАЙ, по-английски WHILE – DO. Соответствующий алгоритм называется циклическим алгоритмом.  Он задает многократное выполнение одних и тех же действий. Запись в общем виде:

    ПОКА  условие ВЫПОЛНИТЬ

          последовательность  действий.

    Последовательность  может выполняться 0,1,…,∞ раз.

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

    С появлением ЭВМ появилась возможность реализовывать алгоритмы очень больших размеров. В этих случаях прибегают к такому приему: вначале записывают алгоритм не с помощью простейших действий, а более крупными блоками, а затем каждый из блоков постепенно расписывают на более мелкие, доходя в конце концов до элементарных действий. Такой метод называется методом пошаговой детализации.

    Блочная структура программы – тоже принцип  структурного программирования.

     Рассмотрим  алгоритм еще с одной точки  зрения. Если не вдаваться в его  структуру, то любой алгоритм можно представить в виде “черного ящика”:

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

    Выход – совокупность переменных и значений, которые получены после вычислений.

    Укажем  входы и выходы наших примеров (см.с. 8,9).

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

    Правила, описывающие алгоритмический язык, распадаются на две части: семантику и синтаксис.

    Семантика – смысловая часть описания языка. Она определяет, как понимать (человеку) и выполнять (машине) алгоритмы.

    Синтаксис – набор формальных правил написания алгоритмов на алгоритмическом языке.

    1.3. Основы алгоритмического  языка Паскаль

    Рассмотрим  только самые основы языка Паскаль, т.к. литература, описывающая его детали, вполне доступна. Язык назван в честь Блеза Паскаля, известного французского философа, математика и физика. Разработан профессором Института Информатики Швейцарской высшей политехнической школы Никлаусом Виртом. Первое сообщение  о нем поступило в 1971 г. Окончательный стандарт – в 1979 г. Паскаль -  современный язык, он содержит все базовые конструкции структурного программирования. Язык прост и очень удобен для обучения программистов. Вместе с тем он обладает большими возможностями при обработке данных разных типов.

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

    1.3.1. Допустимые символы (алфавит)

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

    Цифры – только арабские.

    Знаки арифметических операций: +, -, *, /. Дополнительными  являются две операции для целых  данных (операндов):

    DIV – деление нацело с отбрасыванием остатка (нахождение целой части результата);

    MOD – нахождение остатка от деления.

      Знаки логических отношений и логических операций: <, <=, =, <>, >=, >, AND, OR, NOT.

     Специальные символы: (  ) [  ]  .  :  ,  ;  ..      и т.д.

    При записи алгоритма следует помнить правило: вся программа есть одна длинная строка. Разбиение ее на части необходимо лишь для нашего удобства. Многоэтажные формулы или переменные с индексами должны быть записаны в одну строку:

    

    Это ограничение также связано с  тем, что машина может “читать” только последовательность знаков.

    1.3.2. Объекты программы  на Паскале

    Любой алгоритм оперирует некоторыми объектами (например, числами, переменными). Переменная обозначается  идентификатором – это ее имя.

    Правила записи идентификатора: он начинается с буквы и содержит одну букву или несколько букв и цифр: X, A1B28, ELENA.

    В Паскале длина идентификатора не ограничивается, но при этом значимыми являются первые 63 символа.

    В ходе вычислений переменная изменяет свое значение. Поэтому можно дать следующее определение переменной.

    Переменная – это такой объект, который имеет постоянное имя и переменное значение.

    Константа  имеет постоянное значение и тем отличается от переменной. Она может быть просто числом (и не только), а может иметь имя.

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

    В Паскале определены следующие  стандартные типы объектов.

  1. Целый.                                      для численных
  2. Вещественный.   (арифметических) объектов
  3. Логический.
  4. Литерный (символьный).

    Есть  и нестандартные типы, но о них  скажем позднее.

    Целый (INTEGER) – применим для объектов, принимающих только целые значения: 0, 13, +193, –100. Над переменными целого типа определены все арифметические операции. Они принимают всегда точное значение в интервале [-32768, 32767].

    Вещественный (REAL) – это приближенные действительные значения, причем точность приближения зависит от конкретного устройства, на котором производятся вычисления по данному алгоритму. Любое число записывается с определенной точностью. Например, для логарифмической линейки точность представления чисел – 3 верных десятичных знака, для карманного микрокалькулятора – 6 знаков, для ЭВМ – 9 или даже 16 знаков. Переменная может получить значение в результате вычисления некоторого выражения. При этом значение выражения 0.1*10 может быть равно 0.999999999999 или 1.000000000001. (Поэтому не имеет смысла проверять вещественные данные на равенство). Итак, вещественные объекты предназначены для приближенной записи значений, например,

    10.25    -0.25    0.5825    58.25E-02  (58.25*10-2).

    Диапазон  представления вещественных чисел ±10±75. Над вещественными объектами выполняются все стандартные операции: +, -, *, /.

    Логический (BOOLEAN) – это объекты, которые могут принимать значения истина (TRUE) или ложь (FALSE). Логические значения могут получаться как результат операций сравнения (отношений) над целыми и вещественными (=, <>, <, >, …). Над логическими объектами определены специальные логические операции: AND (логическое умножение), OR (логическое сложение), NOT (логическое отрицание).

    Литерный или символьный (CHAR) – это сокращение от  CHARACTER (символ, литера). Значениями объектов этого типа являются все символы алфавита Паскаля, взятые в апострофы: ‘A’, ‘1’, ‘+’, ‘”’ (апостроф удваивается), ‘ ‘ (пробел).

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

    VAR  R1, R2, R3: INTEGER;

                X1, X2, Y1: REAL;

                EQUAL: BOOLEAN;

                WORD1: CHAR;

    CONST N = 100;  (может быть описана и константа, если у нее есть имя)

    VAR – служебное слово (от variable - переменная).

    1.3.3. Запись алгоритмов  на Паскале

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

    Рассмотрим  основные операторы языка Паскаль. 
 

    Присваивание

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

    Х := А + 1 / (1 – А);

     Х := Х – 1; здесь, в отличие от алгебраического уравнения, Х уменьшается на 1. Присваивание означает занесение требуемого значения в место памяти (МП), выделенное для переменной X.

    Общий вид (формат) оператора присваивания:

     <идентификатор переменной> := <выражение (формула)>

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

X := SIN (A), а также использовать любую из стандартных функций:     COS (X), LN (X), SQRT (X),  EXP (X), ABS (X) и т.д. При этом  

F := (1 – SQRT(X)) / (SIN (2 * X) – COS (X / 2)). 
 

В разных языках возможны различные обозначения  одних и тех же функций.

    Вопрос  о согласовании типов в выражении  рассмотрите самостоятельно.  

    Условный  оператор

      Предназначен для записи условного  (разветвляющего) алгоритма. Он полностью совпадает с базовой конструкцией структурного программирования. Общий вид оператора:

    IF <условие> THEN <действие 1>

                      ELSE  <действие 2> - может отсутствовать. 

    Оператор  цикла

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

    WHILE <условие> DO <действие>

    Скажем  несколько слов  о записи условий: 0 ≤ Х ≤ 1 на Паскале записать нельзя. Нужно применять логические связки(операции): AND, OR, NOT, например,

                (0 <= X) AND (X <= 1),

                X >= 0.

    Для разделения последовательно идущих операторов в Паскале используется знак “;”.

    Если  некоторую последовательность действий нужно рассматривать как одно действие, используются так называемые операторные скобки:

                BEGIN последовательность операторов END

                (начало)                                                  (конец)

    Алгоритм, записанный в форме, пригодной для  выполнения ЭВМ, называется программой.  

                       Программа на Паскале (общая структура)

PROGRAM <идентификатор> (INPUT, OUTPUT);{INPUT, OUTPUT - имена стандартных файлов ввода и вывода. В современных версиях языка Паскаль их указание необязательно}

{Раздел описаний:}

VAR X, Y, Z: REAL; I, J: INTEGER;

{Может быть несколько групп повторений описаний типа.}

BEGIN

……………….. тело программы

……………….. (операторы)

END. 

                   Ввод данных и вывод результатов

    Для этих целей в языке есть специальные  операторы. Правильнее говорить – процедуры ввода-вывода.

    Ввод осуществляется с помощью процедуры ввода, обращение к которой имеет вид:

          READ (<список переменных (ввода)>);

    Список  ввода состоит из имен вводимых переменных, разделенных запятыми. Например, в программе встретилось выражение READ (x).    При этом происходит обращение к клавиатуре. Программа ждет, пока на клавиатуре не будет набрано значение переменной х, которое мы хотим ввести. Выполнение оператора ввода имеет смысл присваивания переменным тех значений, которые вводятся с клавиатуры.

          READ (x);   x :=2.5;

      
 

    Отличие состоит в том, что задание  переменной значения с помощью оператора  ввода более универсально. Оператор ввода позволяет программе общаться с внешним миром.

    Как записывать значения на экране?

         INTEGER и REAL. Это должны быть допустимые константы соответствующего типа. Они отделяются друг от друга по крайней мере одним пробелом.

    целые

- 5   5 1 2            

    вещественные

- 5 . 0   1 . 5   1 Е - 1 0   - 2 . 3 Е 5
Программирование на ЭВМ