В ы с ш е е п р о ф е с с и о н а л ь н о е о б р а з о в а н и е информатика и программироВание осноВы информатики



Pdf көрінісі
бет85/196
Дата09.01.2022
өлшемі4,7 Mb.
#23908
түріУчебник
1   ...   81   82   83   84   85   86   87   88   ...   196
Байланысты:
1 Основы информатики

Пример 9.4. Рассмотрим задачу определения наибольшего обще-
го делителя (НОД) двух целых положительных чисел
M, N.
В математике известен алгоритм решения этой задачи — алгоритм
Евклида, который заключается в последовательном делении сначала
большего числа на меньшее, затем меньшего на полученный остаток,
первого остатка на второй остаток и так до тех пор, пока в остатке не
Рис.  9.2.  Алгоритм
вычисления  коэффи-
циентов  приведенно-
го  квадратного  урав-
нения
Рис.  9.3.  Алгоритм  выбора
максимального  числа  из
трех заданных чисел
Рис.  9.4.  Алгоритм
определения остатка
от  деления  двух  це-
лых  неотрицатель-
ных чисел


120
получится нуль. Последний по счету делитель и будет искомым ре-
зультатом.
Запишем  алгоритм  Евклида,  рассматривая  деление  как  много-
кратное вычитание:
1) если числа равны между собой, то взять в качестве
 НОД любое
из них;
2) если числа не равны между собой, то большее из чисел заменить
их разностью и вернуться к шагу 1.
Алгоритм Евклида может быть представлен следующей словесной
записью:
Начало.
1. Ввести
М, N.
2. Пока
М
 N выполнять:
 если
M
> N,  то M := M - N;
иначе
N :
= N - M.
3. НОД :
= М.
4. Вывести НОД.
Конец.
Блок-схема алгоритма Евклида представлена на рис. 9.5, где блок
1 есть подготовка цикла, блок 2 — управление циклом, блоки 3,
 4, 
Рис. 9.5. Алгоритм Евклида


121
5
 — тело цикла (разветвляющаяся структура), из них блоки 4, 5 яв-
ляются блоками модификации значений переменных цикла
M и N.
Блок-схемы являются исключительно простым и наглядным спо-
собом представления алгоритмов. Их очень полезно использовать при
разработке общей структуры алгоритма, чтобы отчетливо представить
себе алгоритм в целом и проследить все логические связи между его
отдельными частями, проверить все ли возможные варианты решения
поставленной задачи нашли в нем отражение.
Блок-схемы  не  накладывают  никаких  ограничений  на  степень
детализации в изображении алгоритма. Степень детализации опреде-
ляется программистом. Однако следует помнить, что схемы общего
характера малоинформативны, а излишне подробные схемы проигры-
вают  в  наглядности.  При  разработке  сложных  алгоритмов,  чтобы
понять сущность выполняемых действий и выявить основные связи,
алгоритм записывается в виде общей схемы, состоя-
щей из крупных блоков. Блоки соответствуют основ-
ным  шагам  алгоритма  (вводу  данных,  обработке,
выводу данных). Затем крупные блоки разбивают на
более мелкие, составляя более детальные схемы, по-
зволяющие проверить их логическую правильность.
Именно так мы поступили при разработке алгоритма
Евклида, при этом использовали и словесную форму
записи, и блок-схему.
ГОСТ 19.701 — 90 (ИСО 5807-85) предусматрива-
ет  использование  циклической  структуры  общего
вида (безотносительно к типу цикла), представлен-
ной справа. Условие продолжения или окончания цикла может быть
указано как в верхнем, так и в нижнем блоке. Ее применение целе-
сообразно только в простых алгоритмах, в более сложных она теря-
ется в общей структуре алгоритма ввиду отсутствия явной передачи
управления.


Достарыңызбен бөлісу:
1   ...   81   82   83   84   85   86   87   88   ...   196




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет