Студопедия

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

КАТЕГОРИИ:

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






Понятие алгоритма. Понятие «алгоритм» является одним из основных понятий информатики и математики






 

 

Понятие «алгоритм» является одним из основных понятий информатики и математики. Название алгоритм происходит от Algorithmi – латинской формы написания имени великого учёного средневекового Востока Мухаммеда ибн Мусса Аль Хорезми. Его годы жизни приблизительно с 783 по 850 гг. Он сформулировал правила выполнения арифметических действий над многозначными числами.

Что же будем понимать под алгоритмом?

Задача 1. Даны два натуральных числа[1] a и b. Напишите алгоритм нахождения НОД(a, b) – наибольшего общего делителя a и b.

Решение. a и b – входные данные задачи. По существу, мы имеем не одну задачу, а бесконечное множество однотипных задач, столько, сколько существует различных пар натуральных чисел (a; b). Возникает вопрос: существует ли общий метод, позволяющий для любой частной задачи, получаемой подстановкой вместо a и b конкретной пары натуральных чисел, за конечное число шагов определить НОД(a, b).

Для решения задачи необходимо иметь последовательность каких-то действий над входными данными и результатами предыдущих действий, если такие уже имеются, позволяющих найти НОД(a, b). Желательно, чтобы набор этих действий был невелик и в то же время достаточен для нахождения наибольшего общего делителя для любых a, b Î N. Тогда должно существовать нечто такое, обозначим его «А», что после каждого действия оно должно указывать, что делать дальше: либо окончить процесс и указать результат, либо перейти к выполнению следующего определенного действия.

Вот это «А» и принято называть алгоритмом.

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

Алгоритмом решения поставленной задачи для выбранного исполнителя является, например, алгоритм Евклида.

Шаг 1. Сравни два числа a и b. Обозначь большее число через r, а меньшее через r 1. Найди остаток r 2 от деления r на r 1. Сравни r 2 с нулем, если r 2 равно нулю, то НОД(a, b) присвой значение r 1 и иди на шаг 3, иначе иди на шаг 2.

Шаг 2. Переменной r присвой значение r 1, а r 1 – значение r 2. Найди остаток от деления r на r 1 и обозначь его r 2. Сравни r 2 с нулем, если r 2 равно нулю, то НОД(a, b) присвой значение r 1 и иди на шаг 3, иначе иди на шаг 2.

Шаг 3. Процесс вычисления НОД(a, b) закончи.

Возникает вопрос: всегда ли описанный процесс заканчивается, т.е. всегда ли за конечное число шагов получим нулевой остаток? Легко доказать, что процесс последовательного деления конечен. Любой из остатков является неотрицательным целым числом, и последовательность остатков монотонно убывает. Следовательно, последовательность конечна и последний остаток равен нулю.

Под алгоритмом будем понимать понятное и точное предписание исполнителю совершить последовательность действий, направленных на решение поставленной задачи. [2]


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал