Алгоритм и его свойства. Способы записи алгоритма

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

      Для <переменная> выбор <откр_скобка>

      при <значение1>:

         <тело 1>; break;

      при <значение2>:

         <тело 2>; break;

      …

      иначе:

         <последнее тело>;

      <закр_скобка>

      где <откр_скобка><закр_скобка> - "составной оператор";

      <переменная> - переменная целого типа или типа, приводимого к целому (например, перечисления, одиночный символ и т.п.);

      <значение n> - одно из возможных значений этой переменной,

      < тело n> - последовательность действий для этого значения переменной; и

      <последнее тело> - последовательность операций в случае, если переменная не принимает ни одного из значений в блоке.

      Замечание: оператор множественного выбора может «моделироваться» повторением оператора ветвления, например:

      если <значение 1> то <тело 1>

      иначе если <значение 2> то <тело 2>

      иначе если …

      иначе <последнее тело>

                 

      где <тело> - оператор или последовательность операторов, заключенных в скобки.

      Замечание: оператор множественного выбора не часто встречается в символьных вычислениях.

      Рис. 5.7. Множественный выбор на блок-схеме.

4. Составной оператор.

      Блок  операторов представляет собой допустимую последовательность операторов, заключенных  в скобки (например, в Си/C++ это  фигурные скобки: "{…}") или между  лексемами: "Begin … End" (как в Паскале  и Алголе).

      На  блок-схеме такие операторы никак не выделяются, а представляют собой просто последовательности операторов.

      Составной оператор применяется в следующих  случаях:

1. В операциях условия, цикла, ветвления, множественного выбора, когда вместо одного оператора необходимо выполнить несколько операций (блок);
2. Необходимо определить "локальные переменные", определяемые лишь внутри блока;
3. Нужно написать тело функции или процедуры.

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

      6. Типовые алгоритмы.

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

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

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

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

  Sum := Sum + A[I] , где I = 1, 2, .., N.

      Аналогично  вычисляется произведение:

  Proiz := Proiz * A[I], где I = 1, 2, .., N.

      В качестве начального значения произведению естественно присвоить 1. Оформим  на псевдокоде алгоритм, являющийся реализацией  этой идеи. (Пример 1.)

Пример  1.

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

Пример  2.

      Принцип вычисления заключается в сравнении каждого элемента массива со значением в Max и запоминанием в нем элемента, который оказался больше значения Max. Для корректного первого сравнения в качестве начального значения Max можно использовать первый элемент массива. Тогда сравнения в цикле целесообразно начинать сI = 2.

      Заметим, что значение, полученное в Max, совпадает со значением A[NMax].

      При поиске максимального среди элементов  массива, удовлетворяющих некоторому условию, например, только среди отрицательных, нельзя инициализировать Max так же, как в примере 7 (Max = A[1]), т.к. A[1] может не быть отрицательным. В этом случае в качестве начального значения Max можно использовать очень маленькое число. Как только встретится отрицательный элемент массива больший Max, значение Max будет заменено на этот элемент. Если Max останется неизменным, это значит, что в массиве нет элементов, удовлетворяющих заданному условию (в нашем случае - отрицательных). 
Для поиска минимального среди элементов массива в качестве начального значения Min надо использовать большое положительное число (Пример 3).

      Пример  3.

      В этом случае естественно организовать цикл, начиная с первого номера элемента (I = 1). Заметим, что вместо сложного условия в ветвлении можно использовать два простых:

      Однако, первый вариант представляется более  наглядным. Следующая группа задач объединяется под условным названием вычисление новых массивов на основе заданных. Эти задачи принято разделять на две группы:

      - вычисление нового массива, число  элементов которого совпадает  с числом элементов заданного  массива;

      - вычисление массива, число элементов  которого может не совпадать  с числом элементов заданного массива.

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

  

  Очевидно, что в новом массиве B будет столько же элементов, сколько и в исходном массиве, т.к. для каждого A[I] в зависимости от условия вычисляется соответствующий B[I]. Таким образом, одна переменная I определяет номер элемента в массиве A и номер элемента в массиве B. (Пример 9).

Пример 9