Алгоритм РАЕ Кнута

 

 

 

 

 

 

 

 

………………………

 

 

 

 

 

;

 

Алгоритм Кнута удобно представлять в виде таблицы

 

Остаток (r)	q	x	y
a	*	x-1 1	y-1 0
b	*	x0 0	y0 1
r1	q1	x1	y1
r2	q2	x2	y2
…………………..	……………………….	……………………	……………………….
rn-2	qn-2	xn-2	yn-2
rn-1	qn-1	xn-1	yn-1

 

;

 

Общий вид формул для вычисления xj и yj:

 

xj=xj-2-qjxj-1

 

yj=yj-2-qjyj-1

 

Пример:

 

	q	x	y
a=1234	*
b=54	*
		1-22*0=1	…..
		-1	…..
		1-5*(-1)=6	….
		-1-1*6= -7

 

 

Вопросы для самопроверки.

 

1. Для чего предназначен алгоритм Евклида?

 

2. Что такое НОД и НОК? Какая связь между ними?

 

3. Каким образом можно вычислить НОД?

 

4. Поясните работу алгоритма Евклида.

 

5. Какое рекуррентное соотношение существует между остатками, полученными на смежных шагах алгоритма Евклида?

6. Почему алгоритм Евклида конечен?

 

7. Какими особенностями обладает алгоритм Евклида?

 

8. При каких условиях происходит выход из алгоритма Евклида?

 

9. Какие математические операции используются в алгоритме Евклида?

 

10. В чем заключается отличие модификации алгоритма Евклида от алгоритма

 

Евклида?