Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
C-lections / lection2.ppt
Скачиваний:
27
Добавлен:
27.03.2015
Размер:
244.22 Кб
Скачать

Алгоритм

Определения

Алгоритм Евклида

Формы представления алгоритма

Программа = Алгоритм + Данные

Составные части языка программирования

Общее описание типичной

Определения

Понятие алгоритм является основным при составлении любого рода программ для ЭВМ.

Современное значение слова алгоритм очень схоже со значением слов рецепт, процесс, метод, способ, процедура, программа, однако в слове «алгоритм» имеется свой дополнительный оттенок.

Алгоритм – конечная последовательность общепонятных предписаний, формальное, не требующее проявления человеческой изобретательности, исполнение которых позволяет за конечное время получить решение некоторой задачи или любой задачи из некоторого класса задач.

Алгоритм – свод конечного числа правил, задающих последовательность выполнения операций, при решении той или иной задачи.

Алгоритм - формальное однозначное описание последовательности действий.

Важные особенности алгоритма

Конечность (финитность). Алгоритм всегда должен заканчиваться после конечного числа шагов;

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

Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число входных данных, т.е. величин, заданных ему до начала работы;

Вывод. Алгоритм имеет одну или несколько выходных величин, т.е. величин, имеющих вполне определенное отношение к входным данным;

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

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

К 1950г. Под словом алгоритм чаще всего подразумевали изложенный в «Элементах» Евклида (книга VII, предложения I и II) алгоритм Евклида – процесс нахождения наибольшего общего делителя двух чисел.

Алгоритм Евклида

Даны два целых положительных числа m и n. Требуется найти их наибольший общий делитель, т.е. наибольшее положительное целое число, которое нацело делит как m, так и n.

Е1.[нахождение остатка] Разделим m на n. Пусть остаток равен r. (Имеем 0 ≤ r < n.)

Е2. [Это нуль?] Если r равен 0, алгоритм завершается; n – искомое число.

Е3. [Замена] Положите n в m (m ← n), r в n (n ← r) и возвращайтесь к шагу Е1.

Формы представления алгоритма

Псевдокод

Псевдокод – искусственный и неформальный язык, используемый для описания алгоритмов.

Псевдокод часто используется для разработки алгоритмов, которые потом должны быть преобразованы в структурированную программу на любом из известных вам языков (например, C).

Преимущества псевдокода:

подобен разговорному языку;

удобен и дружелюбен.

Псевдокод это не язык программирования, программы, написанные на псевдокоде, не могут выполняться на компьютере.

Соседние файлы в папке C-lections