Запись алгоритмов в виде блок-схем (1106283)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Запись алгоритмов в виде блок-схемВылиток А.А.Блок-схема (нем. Block, голл. blok и греч. σχηµα — наружный вид, форма) —графическое представление алгоритма (или управляющей структуры программы).Состоит из замкнутых фигур стандартной формы — блоков — и соединяющих ихстрелок. В блоках записываются команды или названия действий, а стрелки указываютна порядок их выполнения.Виды блоков:дакоманда, действиенетпроверка условияввод / выводначало / конецВ качестве примера рассмотрим алгоритм нахождения наибольшего общегоделителя двух заданных натуральных чисел m и n.

(Пусть m mod n означает остаток отделения m на n.)Алгоритм ЕвклидаШаг 1. Присвоить r остаток от деления m на n.Шаг 2. Если r = 0, то выполнение алгоритма прекращается; n — искомоезначение.Шаг 3. Присвоить m значение n, присвоить n значение r и вернуться к шагу 1.Изобразим этот алгоритм в виде блок-схемы:началоввод m, nr := m mod nr=0нетm := n; n := rдавывод nконецПокажем, что получаемое в результате число действительно являетсянаибольшим общим делителем. После шага 1 имеем m = qn + r, где q — некотороецелое число. Если r = 0, то m кратно n и, очевидно, в этом случае n — наибольшийобщий делитель чисел m и n.

Если r ≠ 0, то любой делитель обоих чисел m и n долженбыть также делителем числа r = m − qn, и любой делитель чисел n и r должен бытьделителем числа m = qn + r. Таким образом, множество общих делителей чисел m и nсовпадает с множеством общих делителей чисел n и r. Следовательно, пары чисел<m, n> и <n, r> имеют один и тот же наибольший общий делитель. Таким образом, шаг3 не изменяет ответа исходной задачи. (Очевидно, что если первоначально m < n, точастное на шаге 1 оказывается равным нулю и на шаге 3 произойдет взаимный обмензначений переменных m и n.)Алгоритм завершится после выполнения конечного числа шагов.Действительно, после шага 1 значение r меньше, чем n.

Поэтому если r ≠ 0, то наследующей итерации цикла значение n на шаге 1 уменьшается. Убывающаяпоследовательность положительных целых чисел имеет конечное число членов,-1-поэтому шаг 1 может выполняться только конечное число раз для любогопервоначально заданного числа n.Хороший стиль программирования и конструирования алгоритмов предполагаетиспользование структурированных схем.Структурированная схема строится из фрагментов, каждый из которых имеетодну входную и одну выходную стрелку. Простейший фрагмент — пустой — состоитиз одной стрелки, входной и выходной одновременно:Далее идет фрагмент, состоящий из одного оператораSФрагменты остальных видов (структурированные) получаются композициейдвух или трех операторов.

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

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

В обоих случаях фрагмент с оператором S не может бытьпустым.BнетSдаSнетBдаМожно модифицировать алгоритм нахождения наибольшего общего делителя(НОД) чисел m и n, заметив, что если m > n, то НОД(m ,n) = НОД(m − n, n), если m < n,то НОД(m, n) = НОД(m, n − m), а если m = n, то n — наибольший общий делитель.Построим структурированную блок-схему данной модификации алгоритмаЕвклида, используя метод последовательных уточнений.Если бы в системе команд исполнителя была операция НОД(m, n) нахождениянаибольшего общего делителя чисел m и n, блок-схема алгоритма выглядела бы так:началоввод m, nвывод nn := НОД(m, n)конецДетализируем оператор n := НОД(m, n): пока m ≠ n изменять значения m и n всоответствии с написанным выше (если m = n, то n — результат):началоввод m, nm≠nнетвывод nконецдаизменить m, nОсталось уточнить, как именно следует изменять значения m и n, и мы получимокончательную схему алгоритма:-3-началоввод m, nm≠nнетдаm>nдаm := m − n-4-нетn := n − mвывод nконец.

Характеристики

Тип файла PDF

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

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

Список файлов учебной работы