Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Формульно-словесный способ.






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

Пример 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.

 

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

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.