Шпаргалка по "Информатике"

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

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

АЛГ перенос     АЛГ в_угол3    АЛГ до_края

НАЧ     НАЧ     НАЧ

      в_угол3    до_края    ПОКА не_край

      ЕСЛИ  есть    вправо    НЦ

            ТО     до_края    вперед

                  взять   вправо    КЦ

                  в_угол3  КОН     КОН

                  установить 

                  перенос

            ИНАЧЕ

                  в_угол3

      ВСЕ

КОН

Виды алгоритмов 

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

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

 

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

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

2. Определенность. Каждое правило алгоритма должно  быть четким, однозначным. 

3. Результативность. Алгоритм должен приводить к  решению за конечное число  шагов. 

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

5. Правильность. Алгоритм правильный, если его  выполнение дает правильные результаты  решения поставленной задачи 

Файл «Алгоритмические структуры» 
 

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

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

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

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

• операции присваивания;

• простейших арифметических операций;

• операций сравнения  чисел;

• операторов безусловного и условных переходов (изменяющих порядок  вычисления команд в программе);

• операторов вызова подпрограмм (вспомогательных алгоритмов).

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

Рассмотрим подробнее  операции, которые выполняются компьютером и которые являются шагами программы при операциональном подходе.

Операция присваивания состоит в том, что некоторое  значение фигурирующей в программе  величины помещается в ячейку памяти компьютера. Эта ячейка может либо принадлежать оперативной памяти, либо находиться в арифметико-логическом устройстве, выполняющем основные операции (это устройство - часть процессора). После операции присваивания указанное значение сохраняется в ячейке памяти, куда оно было помещено, пока не будет заменено другим в результате другого присваивания. Ячейка памяти, где размещается значение, в программе обозначается именем (идентификатором) соответствующей переменной. Примеры идентификаторов: а, х, у1, у2. Важно помнить, что переменные и, соответственно, их значения могут быть разных типов - числовые (целые или действительные), литерные или логические. Значения различных типов представляются (кодируются) в компьютере по-разному, поэтому они должны соответствовать типам переменных, которым они присваиваются. При разработке алгоритма следует всегда помнить и 'тщательно различать типы переменных.

Набор простейших арифметических операций «сложения» (+), «вычитания» (-), «умножения» (*) и «деления» (/) (причем во многих случаях следует  тщательно отличать деление, выполняемое над целыми числами - в этом случае операция деления распадается на деление нацело и вычисление остатка от деления) позволяет записывать арифметические выражения с использованием числовых констант и идентификаторов переменных. Для определения порядка операций в выражениях чаще всего используют стандартное математическое соглашение о старшинстве операции, согласно которому старшими и выполняемыми в 1-ю очередь являются умножение и деление, а младшими - сложение и вычитание. Для изменения «естественного» порядка выполняемых операций служат скобки. Сравните, например, порядок операций в выражениях: 

(а + 2) * х и  а + 2 * х. 

Что же касается порядка выполнения операций одного старшинства, то они, как правило, выполняются  в порядке записи в выражении.

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

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

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

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

n = 0,1,2,... 

Можно показать, что  .

Будем обозначать через x0 нулевое приближение (за него в данном случае можно принять любое положительное число), через e заданную точность вычислений и через c0 какое-нибудь число, удовлетворяющее условию 0 < c0 < , необходимое для оценки достигнутой точности с помощью неравенства 

 

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

1) ввести числа  а, e, x0, c0;

2) присвоить  переменной х значение у,

3) присвоить  переменной у значение а/х;

4) присвоить  переменной у значение х + у,

5) присвоить  переменной х значение у/2;

6) присвоить переменной у значение x2;

7) присвоить  переменной у значение y-а;

8) присвоить  переменной у значение у/c0;

9) присвоить  переменной d значение у/2;

10) сравнить d и e; если d > e, то перейти к команде 3, иначе перейти к следующей команде;

11) вывести числа х, а и e;

12) стоп.

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

Поясним эту  программу. Команда 2 помещает значение начального приближения x0 в ячейку памяти, в которой хранятся значения переменной х (на каждом этапе вычислений в этой ячейке хранится значение х, равное значению одного из членов рекуррентной последовательности xn).

Команды 3-5 вычисляют  по числу х число (х + а/х)/2. Результат  помещается в ячейку памяти, в которой  хранится значение переменной х, при  этом старое значение «стирается» новым. Команды 6-9 вычисляют величину

, 

с помощью которой  оценивается сверху разность х - . Важное значение имеет команда 10. По ней не производятся вычисления, а сравниваются между собой вычисленное значение 5 и заданная точность e. Если d > e, то управляющее устройство вернет вычислительный процесс к команде 3 и заставит повторить процесс.

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

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

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

• злоупотребление  командой условного и безусловного переходов зачастую приводило к  очень запутанной структуре программы, напоминавшей по образному сравнению  «блюдо спагетти»;