yosuyah https://blog.hatena.ne.jp/yosuyah/ NAHA https://yosuyah.hateblo.jp/ お勉強 計算とアルゴリズム テキスト1.4～1.5。1章の演習問題全て。再帰法とグラフ。 1.4.1で扱われているユークリッドの互除法の計算回数について調べた。 ラメの定理 a,b∈自然数(0を含む), a>b, mをbの桁数, nをユークリッドの互除法で余りを求めた回数とする。このとき 5m >= n となる。 証明には1.4.2で扱われているフィボナッチ数が重用な役割を演ずる。具体的に言うと、b >= f_(n+1)となることを使う。その証明はf_i = f_(i-1) + f_(i-2)とr_i = q_(n-i+1)*r_(n-i+1) + r_(n-i+2)を見比べれば分かる。（q_(n-i… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyosuyah.hateblo.jp%2Fentry%2F2014%2F10%2F23%2F211658" title="ユークリッドの互除法 - NAHA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-10-23 21:16:58 rich https://yosuyah.hateblo.jp/entry/2014/10/23/211658 1.0 100%