Дополнительные требования к составлению алгоритмов

Для внесения большей ясности в блок-схемы мы воспользуемся несколькими правилами стандарта ГОСТ 19.701-90 составления схем.

  • Там, где это возможно, будем придерживаться правила, согласно которому стрелки входят в элемент сверху и/или слева, а выходят снизу и/или справа.
  • Условия циклов будем записывать в сочетании со словом "пока", за которым следует условие, которое должно выполняться.
  • Необходимо избегать пересечения стрелок
  • Для уменьшения количества входящих стрелок можно объединять несколько стрелок в одну.

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

А вот новый вариант:

Цикл с параметром

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

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

Если же мы работаем по заранее составленной программе тренировок, мы знаем точное количество повторений:

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

Свойства алгоритмов

Алгоритмы обладают следующими свойствами:

  1. Дискретность. Алгоритм представляет процесс решения задачи с помощью последовательности действий.
  2. Детерминированность. В каждый момент известно, какая следующая команда должна выполниться. При одних и тех же входных данных алгоритм даст один и тот же результат. Например, алгоритм подсчета площади прямоугольника при одних и тех же длинах сторон всегда будет давать одно и то же значение площади.
  3. Понятность. Алгоритм должен быть понятен исполнителю и должен включать только те команды, которые входят в систему команд исполнителя.
  4. Массовость. Алгоритм должен работать с различным набором входных данных. Например, программа, вычисляющая длину окружности, должна уметь делать это для разных значений радиуса.
  5. Результативность. Алгоритм должен получать результат решения поставленной задачи либо выдавать сообщение о том, что решение не может быть получено. Если, к примеру, программе, вычисляющей длину окружности, передать отрицательное значение радиуса, программа должна выдать соответствующее сообщение об ошибке.
  6. Эффективность. Чем меньше времени требуется алгоритму для получения решения, тем он эффективнее.
  7. Алгоритм содержит ошибки, если приводит к неправильным результатам или не дает результатов вовсе. Алгоритм не содержит ошибок, если он выдает правильные результаты для любых допустимых исходных данных.

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

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

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

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

Составить алгоритм уборки N полей, считая, что поля являются квадратными и имеют площадь S, а за один проход трактор покрывает полосу шириной w.

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

Составить алгоритм расчета количества краски, необходимого для покраски автомобиля. Известно количество краски Q, которое тратится на покраску 1м2.

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

Введение в программирование

Мы рассмотрели различные варианты записи алгоритмов - в словесной форме, в виде блок-схем и с помощью псевдокода. Однако все они допускают различную форму записи одних и тех же действий. Тем не менее, в качестве исполнителя этих алгоритмов мы рассматриваем компьютер, поэтому программы, которые он будет выполнять, должны быть записаны на понятном ему языке. Язык для записи алгоритмов должен быть формализован и в нем не должно быть места для произвольного их толкования исполнителем. Такой язык называется языком программирования, а запись алгоритма на этом языке - программой для компьютера .

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

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

  • Машинные
  • Машинно-ориентированные (ассемблеры)
  • Машинно-независимые (языки высокого уровня)

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

Машинные языки

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

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

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

Язык ассемблера

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

Вот фрагмент программы, написанной на языке ассемблера для IBM PC:

  MOV AX,b
  ADD AX,c
  MOV a,AX

В данном фрагменте показана процедура вычисления выражения a = b + c. Для этого сначала в регистр (ячейку памяти) AX помещается значение b, затем к значению регистра AX (т.е. к b) прибавляется c и содержимое регистра AX перезаписывается. В конце концов, полученное значение переписывается в ячейку памяти, где хранится переменная a.

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

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

  • Алфавит алгоритмического языка значительно шире алфавита машинного языка, что позволяет повысить наглядность программы.
    Чем больше букв в алфавите, тем больше разных слов можно из них составить и тем легче понимать язык.
  • Набор операций, допустимы для использования, не зависит от набора машинных операций, а выбирается из соображений удобства записи алгоритмов решения задача определенного класса.
    Например, существуют языки, где для строк определена операция сложения, в результате которой образуется строка, состоящая из объединения первой и второй. К примеру, если сложить строки "я хочу " и "научиться программировать", получится строка "я хочу научиться программировать". Это становится возможным благодаря наличию в языке операции объединения строк.
  • Формат предложений гибок и удобен, что позволяет с помощью одного предложения задать достаточно содержательный этап обработки данных.
    Рассмотренный выше пример сложения чисел b и c и перемещения результата в a на языке высокого уровня будет выглядеть следующим образом:
            a := b + c;
          
  • Операции над числами задаются с помощью общепринятых математических обозначений.
    Сложение определяется с помощью оператора "+", вычитание - с помощью оператора "-", деление - с помощью "/", имеется возможность использовать скобки для задания последовательности операций и т.д.
  • Данным в алгоритмических языках присваиваются индивидуальные имена, выбираемые программистом.
    Сравните читаемость следующих формул для закона Кулона:
          Fk := k*Q1*Q2/R12;
        
    и
          a := b*c*d/e;
        
    Что нагляднее?
  • В языке может быть предусмотрен более широкий набор типов данных по сравнению с набором машинных типов данных.
    В компьютере имеются логический тип данных, целые числа, числа с фиксированной и плавающей точками. Наиболее простым примером крайне ходового типа данных, который не предсмотрен в компьютере - это буква.

Какие компоненты образуют алгоритмический язык?

Алфавит - это фиксированный для данного языка набор основных символов, из которых должен состоять любой текст, написанный на данном языке.

Синтаксис - это правила построения фраз, которые определяют, какие комбинации являются осмысленными предложениями на данном языке.

Семантика определяет смысловое значение предложений языка. Семантика определяет, какой алгоритм определен данным текстом на алгоритмическом языке.

Понятия алгоритмических языков

  1. Имена (идентификаторы) - употребляются для обозначения объектов программы (переменных, массивов, функций и др.)
  2. Операции:
    • Арифметические +, -, *, / и др.
    • Логические и, или, не
    • Операции отношения <, >, <=, >=, <>
    • Операции сцепки (конкатенации, присоединения), обозначаются знаком "+".
  3. Данные - величины, обрабатываемые программой. Имеется три основных вида данных: константы, переменные и массивы.
    • Константы - это данные, которые зафиксированы и не меняются в процессе выполнения программы. Примеры констант:
      • Числовые: 3.14, 1
      • Логические: да (истина), нет (ложь)
      • Символьные: "А", "?"
      • Литерные (содержат произвольное количество символов): "Занятие №2", "" (пустая строка)
    • Переменные - это данные, которые могуть меняться в ходе выполнения программы. Например, в процессе выполнения программы изменяется переменная счетчика цикла с параметром.
    • Массивы - это последовательности однотипных элементов, число которых фиксировано и которым присвоено одно имя. Доступ к элементам в массиве можно получить с помощью его индекса. Например, в массиве могут храниться строки с именами учащихся данной группы.
  4. Выражения - предназначаются для выполнения необходимых вычислений, состоят из констант, переменных, указателей функций (см. ниже), объединенных знаками операций.
    • Арифметические выражения служат для определения одного числового значения.
      (1+sin(x))/2
    • Логические выражения описывают условия, которые могут удовлетворяться и не удовлетворяться.
      Рассмотрим логическое выражение x*x + y*y < r*r, определяющее принадлежность точки с координатами (x,y) внутренней области круга радиусом r с центром в начале координат. При x=1, y=1, r=2 значение этого выражения "истина", при x=2, y=2, r=1 - "ложь".
    • Строковые (литерные) выражения, значениями которых являются тексты.
      Рассмотренная выше операция конкатенации является примером литерного выражения. Если A = "куст", а B = "зеленый", то значение выражения A + B есть "куст зеленый".
  5. Команды - это наиболее крупное и содержательное понятие языка: каждая команда представляет собой законченную фразу языка и определяет вполне законченный этап обработки данных.
    • Неисполняемые команды - те команды, которые предназначены для описания данных и структуры программы (например, объявление переменных).
    • Исполняемые команды - те команды, которые выполняют различные действия над данными.

Стандартные функции

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

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

Таблица стандартных функций алгоритмического языка

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

Название и математическое обозначение функции
Указатель функции
  Абсолютная величина (модуль)    | х |     abs(x)  
  Корень квадратный     sqrt(x)
  Натуральный логарифм    ln x   ln(x)
  Десятичный логарифм    lg x   lg(x)
  Экспонента (степень числа е ~ 2.72)   ex   exp(x)
  Знак числа  x  ( - 1,  если  х<0;   0,  если x = 0;  1,  если x > 0)    sign x   sign(x)
  Целая часть х (т.е. максимальное целое число,не превосходящее х)     int(x)
  Минимум из чисел х и y     min(x,y)
  Максимум из чисел х и y       max(x,y)
  Частное от деления целого х на целое y       div(x,y)
  Остаток от деления целого х на целое y     mod(x,y)
  Случайное число в диапазоне от 0 до х - 1     rnd(x)
  Синус (угол в радианах)    sin x   sin(x)
  Косинус (угол в радианах)   cos x   cos(x)
  Тангенс (угол в радианах)   tg x   tg(x)
  Котангенс (угол в радианах)   ctg x   ctg(x)
  Арксинус (главное значение в радианах)   arcsin x    arcsin(x)
  Арккосинус (главное значение в радианах)   arccos x   arccos(x)
  Арктангенс (главное значение в радианах)   arctg x   arctg(x)
  Арккотангенс (главное значение в радианах)    arcctg x   arcctg(x)

В качестве аргументов функций можно использовать константы, переменные и выражения. Например:

  • sin(3.14)
  • sin(x)
  • min(a,5)
  • max(a+b, a*b)
  • sin((exp(x)+1)*2)

Правила записи арифметических выражений

Арифметические выражения записываются по следующим правилам:

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

Примеры записи арифметических выражений

Математическая запись Запись на школьном алгоритмическом языке
x * y / z
x / ( y * z )   или   x / y / z
( a**3 + b**3 ) / ( b*c )
( a[i+1] + b[i-1] ) / ( 2*x*y )
( -b + sqrt(b*b - 4*a*c)) / ( 2*a )
0.49 * exp(a*a - b*b) + ln(cos(a*a)) ** 3
x/(1 + x*x/(3 + (2*x)**3))

Типичные ошибки в записи выражений:

  • 5x + 1 Пропущен знак умножения между 5 и x
  • a + sin x Аргумент x функции sin не заключен в скобки
  • ((a + b)/c** Не хватает закрывающей скобки

Домашнее задание

  1. Ответить на вопросы
    1. Прокомментируйте свойства алгоритмов
    2. Что такое уровень языка программирования и какие уровни существуют?
    3. В чем достоинства и недостатки ассемблера?
  2. Составить алгоритм расчета количества краски Q, необходимого для покраски автомобиля. Известно количество краски q0, которое тратится на покраску 1м2. Имеется несколько деталей, площади S которых известны. В конце Q выводится на экран.
Использованные материалы

Дата последнего изменения: 26 декабря 2014