Описание алгоритма Евклида блок-схемой

На рисунке 2.8 приведена блок-схема алгоритма Евклида.

Структура алгоритма — цикл-пока с вложенным ветвлением. Цикл повторяется, пока значения M и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

А теперь посмотрите на трассировочную таблицу алгоритма для исходных значений M = 32, N = 24:

Шаг	Операция	M	N	Условие
	ввод М
	ввод N
	MON			32<>24, да
	M>N			32>24,да
	M:=M-N
	M<>N			8<>24, да
	M>N			8>24, нет
	N:=N-M
	M <> N			8 <>16, да
	M>N			8>16, нет
	N:=N-M
	M <> N			8<>8, нет
	вывод M
	конец

В итоге получился верный результат.

Коротко о главном

Алгоритм Евклида предназначен для получения наибольшего общего делителя двух натуральных чисел. Структура алгоритма Евклида — цикл с вложенным ветвлением.

Ручная трассировка может использоваться для проверки правильности лишь сравнительно простых алгоритмов. Поиск алгоритмических ошибок в программе производится с помощью тестирования.

Вопросы и задания

1. Выполните на компьютере программу Evklid(из параграфа). Протестируйте ее на значениях М = 32, N = 24; М = 696, N = 234.

2. Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:

НОД(А, В, С) = НОД(НОД(А, В), С).

3. Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:

А·В = НОД(А, Б)·НОК(А, В).

ЕК ЦОР: часть 2, глава 6, § 40. ЦОР № 8, 9.

§17

Таблицы и массивы

Основные темы параграфа:

■ что такое массив;

■ описание и ввод значений в массив в Алгоритмическом языке;

■ цикл с параметром в Алгоритмическом языке;

■расчет среднего значения элементов массива.

Изучая базы данных, электронные таблицы, вы познакомились с табличным способом организации данных. Вы уже знаете, что большие наборы данных удобно представлять в табличном виде. В таблицах могут храниться данные разных типов. На практике чаще всего приходится встречаться с таблицами, содержащими числовые и символьные (текстовые) данные.

Что такое массив

Для представления таблиц в языках программирования можно использовать массивы. Вот, например, таблица, содержащая среднемесячные значения температуры в Перми в 2000 году:

Месяц
Температура	-21	-18	-7,5	5,6			22,2			5,4	-7	-18

Такую таблицу называют линейной. Она представляет собой последовательность пронумерованных чисел. Для обозначения этих чисел используют индексированные имена. Например, через Т[ 1] обозначается температура в январе (первом месяце года), Т[5] — температура в мае и т. д.

В программировании линейная таблица называется одномерным массивом. В нашем примере Т — это имя массива. Элементы массива пронумерованы. Порядковый номер элемента называется его индексом. Каждый элемент массива обозначается индексированным именем в следующей форме:

<имя массива> [<индекс>]

Индекс записывается в квадратных скобках: Т[2], Т[10], Т[ 12]. Индексы могут быть представлены не только в виде констант, но и в виде целых переменных и даже выражений целого типа: T[i], T[k], T[i+k], Т[2*k]. Важно следить, чтобы значения индексов не выходили за допустимые границы. В примере с температурами они должны лежать в диапазоне от 1 до 12.

Все элементы массива должны иметь одинаковый тип. Если массив состоит только из целых чисел, то тип массива — целый. В нашем примере значения температур могут быть дробными, поэтому тип массива — вещественный.

Количество величин определяется при описании массива. Все элементы массива могут выбираться произвольно и являются одинаково доступными.

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