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

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ

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) перейти половину улицы и  при этом смотреть налево;

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

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

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

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

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

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

         3)  посолить;

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

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

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

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

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

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

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

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

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

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

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

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

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

                                                                выход – Х

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

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

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

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

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

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

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

    Пример 2.

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

          f =   выход – f.

                x², 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,…,∞ раз.

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

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

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

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

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