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

По Кнуту:

Программа реализующая алгоритм Евклида (Кнут 1.1Е, поиск наибольшего общего частного для двух целых чисел)




Программа определения среднего количества шагов по алгоритму Евклида если n=5.



Программа дает следующий результат:



1. i=2   mid=2
2. i=3   mid=2.5
3. i=4   mid=3.25
4. i=3   mid=3.125
5. i=1   mid=2.0625
6. i=2   mid=2.03125
7. i=3   mid=2.51562
8. i=4   mid=3.25781
9. i=3   mid=3.12891
10. i=1  mid=2.06445
11. i=2  mid=2.03223
12. i=3  mid=2.51611
13. i=4  mid=3.25806
14. i=3  mid=3.12903
15. i=1  mid=2.06451
16. i=2  mid=2.03226
17. i=3  mid=2.51613
18. i=4  mid=3.25806
19. i=3  mid=3.12903
20. i=1  mid=2.06452
21. i=2  mid=2.03226
22. i=3  mid=2.51613
23. i=4  mid=3.25806
24. i=3  mid=3.12903
25. i=1  mid=2.06452

то есть видно, что при значении m кратном 5, шагов надо 1. При увеличении m на единицу, количество шагов увеличивается. Среднее кол-во шагов тоже будет меняться в соответствии с законом:
q*5  --------- 2.0645...
q*5+1 ------- 2.0322...
q*5+2 ------- 2.5161...
q*5+3 ------- 3.2580...
q*5+4 ------- 3.1290...