アルゴリズムについて（ちょい難問だと思います）

質問

（a,b）が（a>b）かつ（b>=0）を満たすとき

x = a; y = b;
while(y>0){
r = (xをyで割った余り);
x = y;
y = r;
}
return x;　　(xを出力）

というa,bの最大公約数を求めるアルゴリズムがあるとする。
ここでwhile文の実行回数（while文を行う回数）を
L(a,b)とし、

F(n)をフィボナッチ数列とすると、
（つまり、F(0)=0,F(1)=1,F(2)=1, F(n+2)=F(n+1)+F(n) (n>=0))

「L(a,b)＝n」　ならば 「a >= F(n+1)」であることを示せです。

どうフィボナッチとループ回数を比較できるのか？
うまく思いつきませんでした・・・
どなたかうまい方法思いついた方お願いします。

回答No.1

Tacosan · ベストアンサー

えぇと, アルゴリズムの解析としては最初の方に出てきてもおかしくないんだけど....
L(a, b) = n に関する帰納法でがんばるのが標準的かな.

お礼

ありがとうございます！

思いついたらすごく簡単でした＞＜

きっと難しいって思い込みがあったんだと思います★