Основы программирования. Борисенко

1.5.2. Инвариант цикла

51

2.Построить индуктивное расширение и выписать алгоритм вы¬ числения функции, которая последовательности коэффициен¬ тов многочлена по убыванию степеней ставит в соответствие значение k-ой производной многочлена в точке t, где k — фик¬ сированное натуральное число.

1.5.2.Построение цикла с помощью инварианта

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

Основная идея состоит в следующем. В процессе выполнения цикла изменяются значения набора переменных. Надо найти соотно¬ шение между меняющимися переменными, которое остается посто¬ янным. Это соотношение называется инвариантом цикла. Сознатель­ ное построение цикла "пока" всегда связано с явной формулировкой и использованием инварианта цикла.

Явная формулировка инварианта помогает выписать инициали¬ зацию переменных, выполняемую до начала цикла, и тело цикла. Инициализация должна обеспечить выполнение инварианта до нача¬ ла работы цикла. Тело цикла должно быть сконструировано таким образом, чтобы обеспечить сохранение инварианта. (Более точно, из того, что инвариант выполняется до начала исполнения тела цик¬ ла, должно следовать выполнение инварианта после окончания тела цикла. В процессе исполнения тела цикла инвариант может нару¬ шаться.)

Завершение цикла, как правило, связано с ограниченной вели¬ чиной, которая монотонно возрастает или монотонно убывает при

каждом	выполнении	тела	цикла. Ц и к л	"пока"	завершается, когда
условие	после слова	"пока"	в заголовке	цикла	становится ложным .

Следовательно, это условие должно прямо или косвенно зависеть от величины, монотонно убывающей или возрастающей в процессе вы¬ полнения цикла. По достижению ее определенного значения условие должно становиться ложным . Условием завершения цикла называют отрицание условия, стоящего после слова "пока" в заголовке цикла.

Выполнение инварианта цикла и одновременно условия заверше¬ ния должно обеспечивать решение требуемой задачи.

52 1.5.2. Инвариант цикла

Общая схема

Обозначим через X множество всевозможных наборов значений всех переменных, меняющихся в ходе выполнения цикла. Множество X иногда называют фазовым, или конфигурационным, простран¬ ством задачи. Инвариант — это некоторое условие I(x), зависящее от точки x из множества X и принимающее значение "истина" или "ложь". (Математики называют такие условия предикатами.) В про¬ цессе инициализации точке x присваивается такое значение x 0 , что условие I(xo) истинно.

Обозначим условие завершения цикла через Q(x) . Условия /(x) и Q(x) должны быть подобраны таким образом, чтобы одновременная истинность /(x) и Q(x) обеспечивала решение требуемой задачи: нахождение точки x с требуемыми свойствами.

Тело цикла можно трактовать как отображение точки x в новую точку T ( x ) из того ж е множества X :

T : X — X .

Условие I(x) является инвариантом для отображения T : если /(x) истинно, то I ( T ( x ) ) также истинно.

О б щ а я схема построения цикла с помощью инварианта выглядит следующим образом:

x :=	x0;	//	x0 выбирается так, чтобы	условие
		//	I(x0) было	истинным
утверждение: I(x);
цикл	пока не	Q(x)
| инвариант: I(x);				в T(x)
| x	:= T(x);		// точка x преобразуется
конец цикла

утверждение: Q(x) и I(x); ответ := x;

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

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

53

Алгоритм Евклида вычисления наибольшего общего делителя

Пусть даны два целых числа m и n, хотя бы одно из которых не равно нулю. Требуется найти их наибольший общий делитель. Напо¬ мним, что наибольшим общим делителем двух чисел m и n называ¬ ется такой их общий делитель d, который делится на любые другие общие делители d'. Такое определение Н О Д подходит не только для чисел, но и для многочленов, поскольку в нем не используется срав¬ нение по величине. Наибольший общий делитель определен с точ¬ ностью до обратимого множителя; в частности, поскольку в кольце чисел обратимы только элементы ± 1 , Н О Д целых чисел определен с точностью до знака.

В качестве пространства X рассмотривается множество пар це¬ лых чисел

X = {(a, b)| а, b G Z , а = 0 или b = 0}

Надо вычислить Н О Д для заданной пары чисел (m, n). В качестве инварианта используем утверждение, что Н О Д текущей пары чисел равен Н О Д исходной пары:

/ (a, b) : Н О Д (а, b) = Н О Д ( т , n).

Следовательно, цикл надо строить таким образом, чтобы при из­ менении переменных a, b наибольший общий делитель пары (a, b) оставался неизменным. В качестве начальной точки x 0 используется пара (m, n).

Обозначим через r остаток от деления а на b:

а =	qb +	r,	где |r| <		|b|.
Тогда нетрудно доказать,	что	Н О Д ( Ь , r )		=	Н О Д ^ , ^ .		Достаточно
показать, что множества общих делителей					пары (b, r)	и	пары	(а, b)
совпадают. Пусть d делит	b и r. Тогда из			равенства а =		qb + r		выте­
кает, что b делит а. Обратно, пусть d делит а и b. Из						определения
остатка имеем:
	r	=	а — qb.
Так как правая часть равенства делится				на	d, то r тоже		делится на
d.

54					1.5.2. Инвариант цикла
Итак, при	замене	пары (а, b)	на	пару	(b, r) Н О Д не	меняется.
Обозначим через T отображение
		T :fa,b)	-	(b,r).
Условие /(а, b) является инвариантным для					отображения	T .
Осталось	только	определить условие завершения цикла Q ^ b ) .

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

НОД (а, 0) = а.

Итак, в качестве условия завершения цикла используем условие, что вторая компонента пары (a, b) нулевая:

Q ^ , b ) : b = 0.

Теперь можно выписать алгоритм нахождения наибольшего общего делителя:

цел алгоритм НОД(вх: цел m,								цел	n)
|	дано: целые			числа m,		n, хотя бы одно отлично от нуля
|	надо: вычислить наибольший общий делитель пары (m, n)
начало		алгоритма
| цел a, b, r;
|	// инициализация
|	a := m; b := n;					b)	==	НОД(ш, n);
|	утверждение: Н О Д ^ ,
|
| цикл пока b != 0						b)	==	НОД(ш, n)
|	| инвариант: Н О Д ^ ,
|	| r	:=	a %	b;	//	находим остаток от деления a на b
|	| a	:=	b; b	:=	r; //	заменяем			пару	(a, b) на (b, r)
|	конец		цикла
|	утверждение: b				== 0 и Н О Д ^ ,				b) ==	НОД(ш, n);
|
|	ответ		:= a;
конец		алгоритма

Быстрое возведение в степень

55

Алгоритм Евклида — один из самых замечательных алгоритмов теории чисел и программирования. Работает он исключительно бы¬ стро, за время, линейно зависящее от длины записи входных чисел. (Действительно, легко показать, что за два выполнения тела цикла число b уменьшается не менее чем в четыре раза. Следовательно, число выполнений тела цикла в худшем случае равно длине двоич¬ ной записи максимального из чисел а, b.) Это позволяет применять алгоритм Евклида к очень большим целым числам — например, к двухсотзначным десятичным. Алгоритм Евклида (более точно, рас¬ ширенный алгоритм Евклида, который будет рассмотрен ниже) при¬ меняется для таких больших чисел в схеме кодирования с открытым ключом R S A , которая в настоящее время широко используется на практике для защиты информации.

Б ы с т р ое возведение в степень

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

Пусть требуется возвести элемент а в целую неотрицательную степень n. В качестве а может фигурировать целое или веществен¬

ное число, квадратная матрица, элемент кольца вычетов по модулю
m и т.п. — требуется только, чтобы элемент а принадлежал	алгебра¬
ической структуре, в которой определена ассоциативная	операция
умножения (т.е. в общем случае, а — элемент полугруппы).

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

умножения.
В качестве фазового		пространства	X этой	задачи рассмотрим
множество троек
		X = {(b,k,p)}.
Здесь b выступает	в роли	текущего основания		степени, k — в ро­
ли текущего показателя степени, p — это у ж е				вычисленная «часть»
степени. Ключевым	моментом всегда		является	формулировка инва-

56	1 5 2 Инвариантцикла
рианта цикла:
I(b, k , p ) :	b k • p = а" = const,

т.е. величина b k • p постоянна и равна а". Легко подобрать начальные значения так, чтобы инвариант выполнялся:

b 0 = а ;	k 0 =	n ;	p 0 =	1 .
I(b 0 ,	k 0 , p 0 )	=	I(а,	n, 1) : а" • 1 = а"

Условие завершения совместно с выполнением инварианта должно обеспечить легкое решение требуемой задачи, т.е. вычисление а". Действительно, если k = 0, то из инварианта следует, что

b0 • p = p = а",

т.е. искомая величина содержится в переменной p. Итак, условие завершения состоит в равенстве нулю числа k:

Q(b, k, p) : k = 0.

Осталось написать преобразование T точки x = (b, k, p), которое сохраняет инвариант и одновременно уменьшает k. Определим пре¬ образование T следующим образом:

, ,	=	Г (b • b, k / 2 ,		p),	если	k	четное
T(b, k, p)		( b, k — 1	,	p • b),	если	k	нечетное

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

вещ алг. быстрое возведение в степень(вх: вещ				a, цел n)
| дано: основание a и		показатель степени n >=		0
| надо: вычислить a в степени n
начало алгоритма
| вещ b, p; цел k;
|	инициализация
| //		:=	n;
| b	:= a; p := 1.0; k
| утверждение: b~k * p		==	a~n;
|

Вычисление			логарифма				57
| цикл пока k > 0
|	| инвариант: b~k * p == a~n;
|	| если			k четное
|	|	| то		:=	k	/	2;
I	I	I	k
|	|	|	b	:=	b	*	b;
I	I I иначе				k	-	1;
I I I		I	k	:=
I	I		p	:=	p	*	b;
I	I конец			если

I конец цикла
I утверждение: k ==	0 и b~k	* p ==	a~n;
I ответ := p;
конец алгоритма
Вычисление логарифма б е з использования
разложения в ряд
Схема построения	цикла с	помощью	инварианта позволяет лег¬

ко написать алгоритм вычисления логарифма заданного числа без использования разложения в ряд.

Пусть задано вещественное число ж. Требуется вычислить лога­

рифм числа ж по основанию а c точностью е, где е — некоторое			поло­
жительное очень	маленькое число. Д л я определенности,	пусть	а > 1
(для а < 1 можно	воспользоваться тождеством l o g 1 / a ж =	— l o g a ж).

Из определения логарифма следует, что надо найти число y такое,

что

а у = ж.

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

а у z* = ж = const.

Таким образом, в цикле будут меняться три переменные

(y,z,t),

58	1.5.2. Инвариант цикла
и инвариант записывается в виде
I(y, z, t) :	а у z* = ж.

Начальные значения переменных y, z, t выбираются так, чтобы выполнялся инвариант:

y0 = 0, z0 = ж, t0 = 1.

Определим условие завершения цикла Q ( y , z , t ) . Необходимо, чтобы искомая величина по окончанию цикла содержалась в пере¬ менной y. Следовательно, величина z* должна быть близка к едини¬ це: тогда приблизительно выполняется равенство

а у w а у z*	= ж,
т.е. y приближенно равен искомому	логарифму. Д л я того, чтобы ве¬

личина z* была близка к единице, нужно, чтобы показатель степени t был близок к нулю, а основание z было не очень велико и не очень

мало. Д л я этого достаточно

выполнения

трех

неравенств

|t| <

е,

1/а < z < а.

М о ж н о доказать строго, что при выполнении

этих неравенств, а так­

ж е условия а у z* = ж, величина

y отличается от l o g a ж не больше

чем

на е.

Выполнение этих трех неравенств и являются условием заверше¬

ния цикла:

Q ( y , z , t ) :

|t| < е

и

1/а

< z

и

z <

а.

Наконец, тело цикла

должно

преобразовывать

переменные (y, z, t)

так, чтобы абсолютная

величина

t

монотонно убывала,

а

переменная

z рано или поздно попадала

бы

в

интервал (1/а, а),

и при

этом

сохранялся инвариант. Такое преобразование

T

легко

выписывается

по инварианту цикла:

{

(y +1,

z/а,

t),

если

z

>

а

(y — t,

z

• а,

t),

если z

<

1/а

(y,

z • z,

t/2),

если

1/а

< z

<

а

Расширенный алгоритм Евклида

59

Заметим, что при применении преобразования T некоторая величина как бы перетекает из одних переменных в другие, при этом равенство а у z* = ж остается неизменным.

Теперь можно выписать алгоритм вычисления логарифма:

вещ алгоритм логарифм(вх: вещ x,

вещ a, вещ eps)

I дано: x > 0, a >

1,

eps

>

0

I надо: вычислить log_a x с точностью eps

начало

алгоритма

I вещ y, z, t ;

I //

инициализация

t

:=

1.0;

I y

:=

0.0;

z

:=

x;

I утверждение: a~y

* z~t ==

x;

I цикл

пока

ItI >=

eps

или z

<= 1.0/a или z >=

a

I

I инвариант: a~y

* z~t ==

x;

I

I если z

>=

a

I

I

I то

:=

z/a;

y

:= y + t ;

I I I

z

I

I иначе

если

z

<=

1.0/a

I

I

I то

:= z*a; y

:=

y

- t ;

I

I

I

z

I

I иначе

:=

z*z; t

:=

t/2.0;

I I I

z

I

I конец

если

I конец

цикла

I утверждение:

ItI < eps

и

I

z > 1 . 0 / a и z < a и

I

:=

y;

a~y

* z~t ==

x;

I ответ

конец алгоритма

Р а с ш и р е н н ый алгоритм Евклида

Один

из

важнейших

результатов

элементарной

теории чисел

утверждает, что наибольший общий делитель двух целых чисел вы-

60	1.5.2. Инвариант цикла

ражается в виде их линейной комбинации с целыми коэффициента¬ ми. Пусть m и n — два целых числа, хотя бы одно из которых не равно нулю. Тогда их наибольший общий делитель d = Н О Д ( т , n) выражается в виде

d = u m + vn ,

где u и v — некоторые целые числа. Результат этот очень важен дл я практики, т.к. позволяет вычислить обратный элемент к n в кольце вычетов по модулю m . Действительно, пусть числа m и n взаимно просты, т.е. Н О Д ( т , n) = 1. Тогда

1 = u m + vn ,
откуда следует
v n = 1 — u m		=>
v n = 1	(mod m)
Нахождение обратного элемента	в кольце вычетов Z m применяется

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

открытым	ключом.
Д л я вычисления наибольшего						общего делителя d и одновременно
чисел u и v используется				так называемый					расширенный		алгоритм
Евклида.	В обычном		алгоритме			Евклида пара чисел (а, b) в цикле
заменяется на пару (b, r ) , где r					— остаток от деления а на b, при этом
наибольший		общий делитель			у	обеих		пар одинаковый.			Начальные
значения	переменных		а и b равны				m и n соответственно.				Алгоритм
заканчивается, когда			b становится				равным		нулю, при этом а будет
содержать наибольший общий делитель .
Идея	расширенного алгоритма						Евклида			заключается	в том, что
на любом шаге алгоритма				хранятся коэффициенты, выражающие те¬
кущие числа		а и b через		исходные			числа		m и n . При замене пары
(а, b) на пару		(b, r) эти коэффициенты перевычисляются.
Итак,	в алгоритме		участвуют			переменные				а, b, u 1 , v 1 ,	u 2 , v 2 , для
которых выполняется			следующий			инвариант				цикла:
	I ( а , b , u i , v i , u 2 , v2) :					НОД (а,b) = НОД(7П,n)
						а = u 1		m + v 1 n
						b = u 2		m + v 2 n