FC2ブログ

Welcome to my blog

[答377] ユークリッドのアルゴリズム

ヤドカリ

ヤドカリ


'


[答377] ユークリッドのアルゴリズム


 ユークリッドのアルゴリズムという、素因数分解の困難な場合に有効な最大公約数の求め方があります。

 2つの自然数の最大公約数を求めるとき、まず、(大きい数)÷(小さい数) を計算し、

 余りが出たら、(割る数)÷(余り) の計算を割りきれるまで繰り返します。

 割り切れたら、そのときの「割る数」 すなわち直前の「余り」が求める最大公約数になります。

 例えば、247 と 91 の場合、

  247÷91=2 余り 65 ,91÷65=1 余り 26 ,65÷26=2 余り 13 ,26÷13=2 となって、

 4回の割り算で最大公約数 13 を得ます。

 では、この方法で、12回の割り算でやっと最大公約数を求められる2つの自然数で最小の組は?



[解答]

 最小の組を求める問題ですので、その最大公約数が1のときで、

 最後の計算は、2÷1=1 になるはずです。

 その直前は、割る数が2で、余りが1だから、割る数を最小にするためには商が1になります。

 従って、3÷2=1 余り 1 です。

 更にその前は、割る数が3で、余りが2だから、5÷3=1 余り 2 です。

 更にその前は、割る数が5で、余りが3だから、8÷5=1 余り 3 です。

 更にその前は、割る数が8で、余りが5だから、13÷8=1 余り 5 です。

 割る数を並べると、(その次が割られる数で)

 1,2,3,5,8,13,21,34,55,89,144,233,377,610,……

 12番目は、割る数が 233,割られる数が 377 となって、377 と 233 が答えです。


☆ 言うまでもなく、フィボナッチ数です。

.

スポンサーサイト



Comments 20

There are no comments yet.
古い人  
No title

今日の花はアロエですね。

此花もこの寒い時期に咲いてますね。
色も形も特徴の有る花です。
ポチ。

ひとりしずか  
No title

わぁー!アロエの花初めて見ましたー
筒状の花びら長さはどれくらいですか?
全体もかなり大きいですねぇ
暖色が太陽を思わせます~ポチ☆

さっちゃんこ  
No title

おはようございます
見事なアロエの花ですネ
色も形も最高です
そろそろメジロも蜜を吸いにやって来るかも知れませんね ポチ

アキチャン  
No title

おはようございます。
アロエがいっぱいになったことがありましたが、
いつから、どうしてなくなってしまったのか、覚えがないのですf(^。^;
でも、家では、お花を咲かせることはできませんでした!ポチ♪

uch*n*an  
No title

この問題は,与えられたアルゴリズムと最小の状況を理解できれば,容易な問題でした。
アルゴリズムが有名なユークリッドの互除法で,最小の場合はフィボナッチ数列になること,
に気付けば,さらに簡単ですね。
私の解法も[解答]と同じでした。

ニリンソウ  
No title

花の咲くアロエは食べたら体にいい、胃の薬?
切り傷にもいいようです。
花が付くのをあまり見かけません。
ポチ

ゆうこ つれづれ日記  
No title

アロエが咲きだしたのですねー
道東では室内で育てているご家庭が多いですが
滅多に花をつけてくれないようです。
大きくてきれいですね。もっと大きくなるのかな?
ポチッ☆

ヤドカリ  
No title

黒翼さん、早速のコメントとポチを有難う御座います。
逆から考えるとフィボナッチになりますね。
有名な数列だけにいろんな所で現れます。

ヤドカリ  
No title

crazy_tomboさん、早速のコメントを有難う御座います。
小さい方から2番目については、
233,610 や 322,521 がありますが、どちらが小さいといえるか判断に迷います。

ヤドカリ  
No title

古い人さん、早速のコメントとポチを有難う御座います。
寒い時期にもかかわらずよく見かけます。
仰る通り、特徴のある花です。

ヤドカリ  
No title

ひとりしずかさん、早速のコメントとポチを有難う御座います。
アロエの花を見られたことがないのですね。
こちらでは所々で見られます。
花の大きさは、長さまで測っていませんが、写真の通りです。

ヤドカリ  
No title

さっちゃんこさん、早速のコメントとポチを有難う御座います。
そちらでも沢山咲いていることでしょう。
残念ながら、こちらではメジロはほとんど見られません。
私が鳥にあまり興味が無いので見落としているのかも知れませんが……。

ヤドカリ  
No title

アキチャンさん、早速のコメントとポチを有難う御座います。
私の母もかつてアロエを育てていましたが、いつの間にか見当たらなくなりました。
同じく、覚えがないです。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
仰る通り、カラクリがわかれば簡単な問題ですね。
フィボナッチを書き出せば、何回以内に最大公約数が求められるかが分かります。

ヤドカリ  
No title

ニリンソウさん、コメントとポチを有難う御座います。
私も傷口にアロエの汁を何回か塗ったのを覚えています。
花はこちらでは所々で見られます。

ヤドカリ  
No title

ゆうこさん、コメントとポチを有難う御座います。
花はこれ以上大きくはならないと思います。
不思議な独特の花ですね。

こっこちゃん  
No title

こんばんは

大きなアロエの花ですね
色が鮮やかですね” ポチ

ヤドカリ  
No title

こっこちゃんさん、コメントとポチを有難う御座います。
アロエの花は独特な雰囲気がありますね。
大きく咲いていました。

いっちゃん  
No title

こんばんは。アロエの花・・・懐かしいです^^
我が家にはたくさんのアロエがありました。お花もちょうど
こんな花でした。。
でも・・でも植木屋さんが、勘違いしてみぃ~~んな取り除いてしまいました。気づいた時はあとの祭り。。><
ポチ

ヤドカリ  
No title

いっちゃん、コメントとポチを有難う御座います。
沢山のアロエが全部なくなったのは残念ですね。
多肉植物の花は独特で面白いです。