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

      В алгоритмах задач второй группы, когда вычисляется новый массив с неизвестным заранее числом элементов, используется понятие "счетчик". Счетчик- это некоторая переменная, которая определяет номер текущего элемента в новом массиве, если такой элемент существует. Очевидно, что номер последнего элемента массива совпадает с числом элементов в этом массиве. Идею использования счетчика продемонстрируем на следующей задаче.

      Введем  некоторую переменную K - счетчик, которая будет определять число элементов в новом массиве. Эту переменную можно использовать в качестве индекса при вычислении очередного элемента нового массива. Если найдутся элементы в массиве A, для которых выполняются сформулированные условия, новый массив C будет содержать K элементов. В начале алгоритма K равно 0. Для каждого A[I] < 0 и Z1 < A[I] < Z2 K увеличивается на 1 и вычисляется C[K] := A[I]. Если в конце алгоритма K останется равным нулю, то в новый массив не попал ни один элемент.

      Рассмотрим  алгоритмы, которые решают задачу удаления (вставки) элементов в массиве. Предположим, что в заданном массиве A[1:N] надо удалить все элементы, удовлетворяющие условию X < A[I] < Y; X, Y заданы, причем X < Y. Воспользуемся идеей "счетчика", позволяющей вычислить новый массив A на месте исходного массива A. Пусть M - счетчик, определяющий номер элемента и число элементов в новом массиве A. Вычислим новый массив A из элементов исходного массива, для которых не выполняется условие X < A[I] < Y. Алгоритм удаления представлен в Примере 11.

Пример 11.

      Отметим, что вычисление нового массива  A осуществлялось при выполнении условия (A[I] <= X) или (A[I] >= Y), которое является противоположным условию удаления соответствующих элементов:

  X < A[I] < Y.

      Перейдем  к алгоритмам вставки элементов  в заданный массив и обсудим одно из возможных решений.

 

  Очевидно, что решение распадается на несколько логических этапов: 

      Сформулированные  этапы являются результатом поставленной задачи. Они позволяют свести сложную  задачу к последовательности более  простых задач. Сначала необходимо выполнить предварительный поиск  номера минимального элемента NMin в массиве A. Если таким элементом окажется последний, то задача вставки сводится к переписыванию в конец массива A элементов массива B. Переписывание повторяется в цикле M раз, причем каждый B[I] записывается на место A [N+I]. Действительно, для I = 1 первый элемент массива B запишется на (N + 1) -е место в массиве A. Для вставки элементов внутрь исходного массива сначала надо подготовить M мест в массиве A после минимального элемента с номером NMin, т.е. cдвинуть элементы массива A вправо (N - NMin) раз. Именно такое количество элементов массива A, начиная с последнего, надо передвинуть на M позиций вправо. Каждый раз A[N - I + 1] переписывается на место A[N + M - I + 1]. Формулы для индексов легко проверить на граничных значениях. Для I = 1 на (N+ M)-е место в массиве A переписывается последний элемент A[N], для I = 2 на (N + M - 1)-е место - предпоследний элемент A[N - 1] и т.д. После сдвига элементов массива A можно записать элементы массива B в массив A на подготовленное место. Операция повторяется M раз, причем

A[NMin + I] = B[I].

      Действительно, для I = 1 первый элемент из B записывается на соседнее с минимальным элементом место в массиве A. В заключение остается модифицировать число элементов в массиве A, увеличив его на величину M. Детальный алгоритм задачи представлен в примере 12.

Пример 12.

      Заметим, что если минимальный элемент окажется последним в исходном массиве, то сдвиг элементов в массиве A не происходит, а сразу выполняется вставка элементов, которая по существу будет являться дописыванием элементов массива B после последнего элемента массива A, ведь в этом случае NMin = N.

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

      Определим для этой задачи переменную Flag и присвоим ей некоторое начальное значение, например, 0. Это означает, что в исходном массиве A пока не нашли элемента, равного заданной величине. Будем просматривать все элементы массива в цикле пока не встретится искомый элемент и пока не достигнут предпоследний элемент ( если A[N] = X, то сумму вычислять не надо):

      цикл  пока (Flag > = 0) и (I < N).

      Как только встретится элемент равный X достаточно поменять значение переменной Flag на любое, отличное от 0, чтобы обеспечить досрочный выход из цикла. Дальнейшие шаги алгоритма тривиальны. Ограничимся их формальным описанием на псевдокоде в примере 13.

Пример 13

      Строго  говоря, в этом алгоритме для досрочного выхода из цикла можно использовать другое условие:

      В этом случае условие выхода из цикла определяется значением переменной I:

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

7. Трансляция, компиляция и интерпретация.

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

      Транслятор – это программа, предназначенная для перевода программы, написанной на одном языке программирования, в программу на другом языке программирования. Процесс перевода называется «трансляцией».

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

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

      Компилятор – это программа, предназначенная для перевода программы, написанной на каком-либо языке, в программу в машинных кодах. Процесс такого перевода называется «компиляцией».

      Компилятор  создаёт законченный результат  – программу в машинных кодах. Затем эта программа выполняется. Откомпилированный вариант исходной программы можно сохранить на диске. Для повторного выполнения исходной программы компилятор уже не нужен. Достаточно загрузить с диска в память компьютера откомпилированный в предыдущий раз вариант и выполнить его.

      Существует  другой способ сочетания процессов  трансляции и выполнения программы. Он называется «интерпретацией». Суть процесса интерпретации состоит в следующем. Вначале переводится в машинные коды, а затем выполняется первая строка программы. Когда выполнение первой строки окончено, начинается перевод второй строки, которая затем выполняется и так далее. Управляет этим процессом программа-интерпретатор.