Использование метода МИ для исследования алгоритмов (на примере обобщенного алгоритма Евклида)

Приведем общий алгоритм Евклида (EV)

Даны два числа m и n – целые положит-ные числа. Найти d=нод и а, b такие что а*m+b*n=d

Алгоритм пошаговой записи

EV1: [Начальная установка]

Положить а^|←b←1; а← b^|←0; c← m; d←n;

EV2: [разделить] Пустьq и ч являются соответственно: частное от деления c/d и остаток (имеем c=q*d+r, 0≤ч<d)

EV3: [r=0?] Если r=0, то алгоритм зак, раб, am+bn=d, если r≠0 то EV4

EV4: [Повторение цикла]

c← d; d← r; t← a^|; a^|←a; a←t-да; t←b^|; b^|←b; b←t-qb

Вернуться в EV2

Этот алгоритм похож на алгоритм Е, но дает больше возможностей, положит. коэффициент а,b.

Рассмотрим алгоритм Евклида для нахождения наибольшего общего делителя 2-х целых положительных чисел. Даны два целых положительных числа m и n.

Найти наибольший общий делитель:

Ш1. [Нахождение остатка]

Разделим m на n. Пусть остаток равен r (У нас получится 0≤r≤n)

Ш2. [остаток равен 0?]. Если r=0, то алгоритм заканчивается и n-является наибольшим делителем

Ш3. [Замещение]. Положим m←n, n←r и вернемся на Ш1

Пример. Пусть m=1769, n=551, найти a и b. am+bn=d. d- это НОД. Выполним все установки и проследим, как будут изменяться все переменные в алг-ме после шага EV2

a’	a	b’	b	c	d	q	r
			-3
	-4	-3
-4			-16

am+bn=d=5*1769-16*551=29=d, a=5, b=-16, d=29