Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Формульно-словесный способ.
Здесь для записи алгоритма используется естественный язык с привлечением, если это необходимо, математических формул и обозначений. Пример 1. Найти Шаг 1. Положить равным . Шаг 2. Если , то положить равным . Шаг 3. Если , то положить равным . Конец. Пример 2. Найти наибольший общий делитель двух целых чисел . Для решения этой задачи обычно используют разложение значений и на простые множители, после чего произведение множителей, общих для и , определяет их наибольший общий делитель. Например, для = 420 и = 90 имеем 420 = 2 × 2 × 3 × 5 × 7; 90 = 2 × 3 × 3 × 5. Наибольший общий делитель в этом случае равен 2 × 3 × 5 = 30. В принципе этот способ можно использовать для формулировки рассматриваемого алгоритма, однако вначале потребуется разработать алгоритм разложения числа на простые множители, что является нетривиальной задачей.
Более просто поставленная задача решается с помощью, так называемого алгоритма Евклида. Обозначим наибольший общий делитель через . Вполне очевидно, что . Тогда алгоритм Евклида можно описать следующим образом. Шаг 1. Если = 0, то принять и закончить вычисления, иначе перейти к шагу 2. Шаг 2. Вычислить и . Шаг 3. Заменить значение на значение , а значение - на значение . Пе- рейти к шагу 1. Здесь q - целая часть от деления m на n; r - остаток от деления.
При = 420, = 90 имеем: Шаг 1. = 90 ¹ 0; Шаг 2. = [420/90] = 4; = 420 - 4 × 90 = 60; Шаг 3. = 90; = 60; Шаг 1. = 60 ¹ 0; Шаг 2. = [90/60] = 1; = 90 – 1 × 60 = 30; Шаг 3. = 60; = 30; Шаг 1. = 30 ¹ 0; Шаг 2. = [60/30] = 2; = 60 – 2 × 30 = 0; Шаг 3. = 30; = 0; Шаг 1. = 0 Þ = 30.
Основным недостатком формульно-словесной записи алгоритма является то, что здесь используется естественный язык, для которого органически присуща неоднозначность слов. К недостаткам данного способа относят также ненаглядность записи алгоритма.
|