В ы с ш е е п р о ф е с с и о н а л ь н о е о б р а з о в а н и е информатика и программироВание осноВы информатики
жүктеу/скачать 4,7 Mb. Pdf көрінісі
|
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) предусматрива- ет использование циклической структуры общего вида (безотносительно к типу цикла), представлен- ной справа. Условие продолжения или окончания цикла может быть указано как в верхнем, так и в нижнем блоке. Ее применение целе- сообразно только в простых алгоритмах, в более сложных она теря- ется в общей структуре алгоритма ввиду отсутствия явной передачи управления. жүктеу/скачать 4,7 Mb. Достарыңызбен бөлісу:
|