Циклы в вычислительных алгоритмах

Определение 4. Циклические алгоритмы – алгоритмы, содержащие фрагменты повторения вычислений.

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

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

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

Общий вид блок-схем циклических алгоритмов представлен в таблице 2.

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

Задача 4.

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

2. . – произведение натуральных чисел 1*2*3…n, . Вычисление значения факториала можно рассматривать как последовательное повторение операции умножения предшествующего значения факториала F на очередное натуральное число.

3. схема алгоритма вычисления факториала на рис.5.

Рис. 5 Алгоритм вычисления функции n!

Задача 5.

1. Составить алгоритм вычисления выражения

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

3. схема алгоритма представлена на рис.6.

Задача 6.

1. Составить алгоритм нахождения наибольшего общего делителя двух целых чисел a и b. [6]

2. Наибольший общий делитель (НОД) двух целых чисел a и b – это наибольшее целое число, которое делит нацело оба числа. Рассмотрим способ, который называется алгоритмом Евклида. Пусть a и b одновременно не равные нулю целые неотрицательные числа и a b. Если b = 0, то НОД(a, b) =a, а если b 0, то для чисел a,b и r, где r – остаток от деления a на b, выполняется равенство НОД (a, b) = НОД(b, r). Действительно, r:=a Mod b, r:= a –(a Div b) * b. Если какое-то число делит нацело и a, и b, то из приведенного равенства следует, что оно делит нацело и число r.

3. Блок-схема алгоритма Евклида нахождения НОД и НОК двух целых чисел на рис.7.

4. Программная реализация алгоритма Евклида (Приложение 1, Evclid.pas).

Задача 7.

1. Дано натуральное число n. Требуется подсчитать количество цифр данного числа.

2. Количество цифр в числе n неизвестно, поэтому необходимо использовать цикл с предусловием. Подсчёт количества цифр можно начать с последней цифры числа, далее увеличить изначально нулевой счётчик цифр на единицу. Повторять уменьшение числа в 10 раз, пока оно не станет равным 0.

3. Блок-схема на рис.8.

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

Рис.7 Алгоритм Евклида нахождения НОД и НОК двух целых чисел

Рис.8 Алгоритм подсчета количества цифр в натуральном числе.

4. Программа для решения задачи 7 (подсчет количества цифр в числе) представлена в Приложении 1, Program7.pas.

МАШИНА ПОСТА

В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

В теории алгоритмов существует так называемый “тезис Поста”: “Всякий алгоритм представим в форме машины Поста”. Этот тезис одновременно является формальным определением алгоритма. Алгоритм(по Посту) — программа для машины Поста, приводящая к решению поставленной задачи.

Тезис Поста является гипотезой. Его невозможно строго доказать (так же, как и тезис Тьюринга), потому что в нем фигурируют, с одной стороны, интуитивное понятие “всякий алгоритм”, а с другой стороны — точное понятие “машина Поста”. Для того чтобы опровергнуть гипотезу Поста, необходимо придумать алгоритм, который невозможно записать в виде программы для машины Поста. На сегодняшний день такого алгоритма не существует. [12]

Состав машины Поста.

Машина Поста состоит из ленты и каретки. Лента бесконечна и разделена на секции одинакового размера — ячейки.

Рис. 9. Состав машины Поста

В каждой ячейке ленты может стоять метка V либо ничего не записано.. Состояние ленты — это распределение меток по ячейкам. Состояние ленты меняется в процессе работы машины.

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

Команды машины Поста:

1. записать 1 (метку), перейти к i-й строке программы;

2. записать 0 (стереть метку), перейти к i-й строке программы;

3. сдвиг влево, перейти к i-й строке программы;

4. сдвиг вправо, перейти к i-й строке программы;

5. останов;

6. если 0, то перейти к i, иначе перейти к j.

Недопустимые действия, ведущих к аварийной остановке машины:

· попытка записать 1 (метку) в заполненную ячейку;

· попытка стереть метку в пустой ячейке;

· бесконечное выполнение (зацикливание).

Команды машины обозначают следующим образом (рис.10):

Рис. 10 Команды машины Поста

Рассмотрим несколько арифметических задач для машины Поста и их решение.[12]

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

1. На ленте задан массив меток. Увеличить длину массива на 2 метки. Каретка находится либо слева от массива, либо над одной из ячеек самого массива. (увеличение числа на 2).

Решение:

1. ? 2; 3 (команды 1 и 2 — передвигаем каретку к массиву)

2. → 1

3. → 4 (команды 3 и 4 — передвигаем каретку к концу массива)

4. ? 5; 3

5. V 6 (команды 5–7 — ставим 2 метки в конце массива)

6. → 7

7. V 8

8. !

2. Даны два массива меток, которые находятся на некотором расстоянии друг от друга. Требуется соединить их в один массив. Каретка находится над крайней левой меткой первого массива. (сложение двух чисел)

Решение.

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

Решение.

4. На ленте заданы два массива — m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива.

Решение:

1. → 2 (команды 1–3: ищем левую метку массива m)

2. ? 3; 1

3. ← 4

4. X 5 (стираем левую метку массива m)

5. ? 6; 7

6. → 5

7. X 8 (стираем левую метку массива n)

8. → 9

9. ? 12; 10 (стерли последнюю метку в массиве n?)

10. ←11 (ищем левый край массива m)

11. ? 10; 4

12. !

5. На ленте задан массив. Удвоить массив в два раза. Каретка располагается над первой ячейкой массива.

Решение.

В результате работы программы справа от исходного массива будет сформирован новый массив удвоенной длины, исходный массив будет стерт.

МАШИНА ТЬЮРИНГА

Абстрактная вычислительная машина, предложенная в 1936 году А. Тьюрингом для уточнения понятия алгоритма. Доказано, что машина Тьюринга по своим возможностям эквивалентна машине Поста.

Состав Машины Тьюринга.

Машина Тьюринга состоит из каретки и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A={a₀,a₁,…,a_N}. Любой алфавит содержит символ «пробел», который обозначается как a₀ или Λ. При вводе команд пробел заменяется знаком подчеркивания «_».

Машина Тьюринга — это автомат, управляемый таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q={q₀,q₁,…,q_M}. В начале работы машина Тьюринга находится в состоянии q₁. Состояние q₀ — это конечное состояние: попав в него, автомат заканчивает работу.[11]

В каждой клетке таблицы, соответствующей некоторому символу a_i и некоторому состоянию q_j, находится команда, состоящая из трех частей:

1. символ из алфавита A;

2. направление перемещения: > (вправо), < (влево) или . (на месте);

3. новое состояние автомата.

Примеры решения задач с помощью машины Тьюринга рассмотрим далее.

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

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

	a0					…
q1	1 H q0	1 H q0	2 H q0	3 H q0	4 H q0		8 H q0	9 H q0	0 λ q0

Здесь q₁ — состояние изменения цифры, q₀ — остановка. Если в q₁ автомат фиксирует элемент из ряда 0..8, то он замещает ее на один из 1..9 соответственно и затем переключается в состояние q₀, то есть устройство останавливается. В случае если же каретка фиксирует число 9, то замещает ее на 0, затем перемещается влево, останавливаясь в состоянии q₁. Такое движение продолжается до того момента, пока устройство не зафиксирует цифру, меньшую 9. Если все символы оказались равными 9, они замещаются нулями, на месте старшего элемента запишется 0, каретка переместится влево и запишет 1 в пустую клетку. Следующим шагом будет переход в состояние q₀– остановка.

2. Дан ряд из символов, обозначающих открывающие и закрывающие скобки. Требуется создать программу для машины Тьюринга, которая выполняла бы удаление пары взаимных скобок, то есть элементов, расположенных подряд – “( )”. Например, исходные данные: “) ( ( ) ( ( )”, ответ должен быть таким: “) . . . ( (”.

Решение. Механизм, находясь в q₁, анализирует крайний слева элемент в строке.

Состояние q₁: если встречен символ “(”, то совершить сдвиг вправо и переход в положение q₂; если определен “a₀”, то остановка.

Состояние q₂: проводится анализ скобки “(” на наличие парности, в случае совпадения должно получиться “)”. Если элемент парный, то сделать возврат каретки влево и перейти в q₃.

Состояние q₃: осуществить удаление сначала символа “(”, а затем “)” и перейти в q₁.

	a0	(	)
q1	a0 H q0	( П q2	) П q1
q2	a0 H q0	( П q2	) λ q3
q3	a0 H q0	a0 П q3	a0 П q1

Для проверки и отладки программ для машины Поста и машины Тьюринга можно использовать тренажёр «Машина Поста» и «Машина Тьюринга». В Интернет можно найти свободно распространяемые имитаторы как машины Поста, так и машины Тьюринга. [9]

ВСПОМОГАТЕЛЬНЫЕ АЛГОРИТМЫ

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

Реализация вспомогательных алгоритмов осуществляется посредством подпрограмм.

Определение 5. Подпрограмма – обособленная, оформленная в виде отдельной синтаксической конструкции и снабженная именем часть программы. Использование подпрограмм позволяет, сосредоточив в них подробное описание некоторых операций, в остальной программе указывать только имена подпрограмм, чтобы выполнить эти операции. [7]

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

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

Определение 7.Функция – подпрограмма, которая передает в точку вызова скалярное значение.

Рассмотрим технологию создания и использования процедур и функций, руководствуясь учебником Окулова С.М. «Основы программирования».

Процедуры.

Структура процедуры схожа со структурой программы.

Вызов процедуры

Для наглядности объяснения, обратимся к примеру:

В данном фрагменте программы вызывается процедура вычисления суммы двух целых чисел. Процедура вызывается по имени.

При вызове процедуры Sum(a,b,c) из основной программы значение переменной присваивается переменной процедуры Sum, а значение переменной – переменной .

.

Рис. 11. Соответствие параметров процедуры

В любой программе все переменные делятся на глобальные и локальные.

В данном фрагменте программы переменные k, p – глобальные, a d,f - локальные. Глобальные переменные описываются в разделе описаний основной части программы, а локальные – только в том, где описываются переменные. Локальные переменные существуют только во временя работы процедуры, определяются (создаются) при её вызове и «исчезают» после завершения работы процедуры.

При описании процедуры указывается список формальных параметров. Каждый параметр является локальным, к нему можно обращаться только в пределах данной процедуры (в примере x,y,z - формальные параметры, рис.11). Фактические параметры – это параметры, которые передаются процедуре при обращении к ней. (a,b,c – фактические параметры, рис.11). Количество и типы формальных и фактических параметров должны совпадать.

Параметры-значения, т.е. передача параметров по значению. При таком способе передачи параметров значение фактического параметра становится значением соответствующего формального параметра. Внутри процедуры можно производить любые действия с данным формальным параметров (допустимые для его типа), но эти изменения никак не отражаются на значении фактического параметра, т. е. каким он был до вызова процедуры, таким же и останется после завершения её работы (x,y – формальные параметры-значения).
Параметры-переменные - формальные параметры, перед которыми стоит служебное слово Var. При таком способе передачи параметров в процедуру передаётся не значение, а адрес фактического параметра (обязательно переменной). Любые операции с формальным параметром выполняются непосредственно над фактическим параметром. [6]

Функции.

Структура функции.

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

В качестве примера приведем алгоритм вычисления выражения

Z=(A⁵+A^-3)/2*A^M, в котором возведение в степень выполняется функцией Step.[7] На рис.12 представлена блок-схема основного алгоритма.

Рис.12 Алгоритм вычисления выражения Z=(A⁵+A^-3)/2*A^M

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

Для успешного усвоения материала рекомендуется выполнить задания для самостоятельной работы в соответствии с номером своего варианта. В подборке заданий для данного пособия использованы материалы следующих источников [3], [7],[8].