- ベストアンサー
アルゴリズムについての問題
(1)AとBは正の整数値とする。 (2)A=L,B=Sとして代入する。 (3)L:Sで比較したときにL>Sの場合はL-S→L(矢印は代入を表す)としてL<Sの場合はS-L→Sとする。 (4)どちらかの計算をした後にLとSを比較し、＝(イコール)の場合はLとして出力する。 (5)＝でない場合は(3)に戻る。LはA,Bに関してどのような関係であるか簡潔に答えよ。 という問題がありました。私はLはAとBの最大公約数と答えました。 あっていますでしょうか？またこのアルゴリズムの名前のようなものがあれば教えてください。
- 数学・算数
- 回答数3
- ありがとう数2
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
あっています。 L と S の最大公約数は、L と S を割り切るので、 L-S または、S-L も割り切ります。質問文にある、 L, S を L-S, S-L に置き換えるアルゴリズムで最大公約数 を求めることができます。
その他の回答 (2)
- Tacosan
- ベストアンサー率23% (3656/15482)
質問番号 5360312 で回答があって, しかもそれに対して「良回答」と出しているにもかかわらずまた同じ質問をしているのはなぜ? あっちの回答者に対する仁義はないの? ちなみにこっちが本来の「ユークリッドの互除法」らしいよ.
お礼
お礼ではありませんが、その時の質問と今回の質問は違うのでよく見てください。自分が善だと思っていてもまわりは偽善と見ていることもありますよ？ 偽善は不愉快です。
- hashioogi
- ベストアンサー率25% (102/404)
「ユークリッド互除法」というキーワードでwebを検索されたらいかがでしょうか ?
お礼
ありがとうございました。参考になりました。
関連するQ&A
- アルゴリズムについて？の問題
(1)AとBは正の整数値とする。 (2)A=L,B=Sとして代入する。 (3)L:Sで比較したときにL>Sの場合はL-S→L(矢印は代入を表す)としてL<Sの場合はS-L→Sとする。 (4)どちらかの計算をした後にLとSを比較し、＝(イコール)の場合はLとして出力する。 (5)＝でない場合は(3)に戻る。LはA,Bに関してどのような関係であるか簡潔に答えよ。 という問題がありました。私はLはAとBの最大公約数と答えました。 あっていますでしょうか？やさしい回答よろしくお願いします。
- ベストアンサー
- 数学・算数
- アルゴリズムと問題解決に関する問題
二つの正の整数A,Bの最大公約数を求めるユークリッドの互除法のアルゴリズム 互除法（A,B） 入力正の整数A,B 1 もしA<Bならば 2 BをAで割ったあまりをCとせよ 3 もしC=0でないならAを出力して終了 4 そうでないならば 5 GCD=互除法（A,C)とし、GCDを出力し終了 6 そうでないならば 7 AをBで割ったあまりをCとせよ 8 もしC=0ならばBを出力して終了 9 そうでないならば 10 GCD=互除法（B,C)とし、GCDを出力し終了 互除法(48,84)を行ったときのうえのアルゴリズムの動作(再帰呼び出しの途中に現れるCやGCDの値）を求めよ これを一応といてみましたが表現方法がいまいちわからないので良い回答の仕方教えてください。 自分で解いた答え 1 A<BなのでB/Aのあまり36をCとする 2 C=36 3 Cは0でない 4、5 GCD=(A,C)=(48,36) 1に戻る A=48,B=36とする 1 A＜Bでない 6 A/BのあまりをCとする 7 48/36のあまり C=12 8 Cは0でない 9,10 GCD=(36,12） 1に戻る A=36,B=12 1 A＜Bでない 6,7 36/12 C=0 8 C=0 B=12
- 締切済み
- その他（プログラミング・開発）
- アルゴリズムについて（ちょい難問だと思います）
（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)」であることを示せです。 どうフィボナッチとループ回数を比較できるのか？ うまく思いつきませんでした・・・ どなたかうまい方法思いついた方お願いします。
- ベストアンサー
- 数学・算数
- 組み合わせ問題のアルゴリズム
あらかじめ用意された整数を足して、その合計がある指定された整数と等しくなる組み合わせの数を調べるプログラムを書こうとしているのですが、苦労しています。 具体例がないと伝わりにくいかもしれないので例をあげると、 例えばあらかじめ用意された整数というのが 1・1・2・2・5・8 の4つで、 指定された整数が10である場合は、 8と2 8と1と1 5と2と2と1 という3通りの組み合わせがあるので、3を出力したいというわけです。 今まではもっと単純なアルゴリズムしか考えてこなかったので、こういった組み合わせのような問題が難しく感じられます。 こういう場合、アルゴリズムはどのようなものが考えられるでしょうか。 よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- 整数問題
二つの奇数a，b にたいして，m = 11a + b，n = 3a + b とおく．つぎのことを証明せよ． m，n の最大公約数は，a，b の最大公約数をd として，2d，4d，8d のいずれかである． 僕はユークリッドの互除法を考えました。 (11a+b)=(3a+b)*1+8a よってmnの最大公約数は3a+bと8aの最大公約数である。 さらに(3a+b)=(3/8)*8a+b として8aとbの最大公約数が求める最大公約数と考えましたが、ここで矛盾が生じます。 bは奇数であるので偶数の2d等を因数に持たない。 よく考え直してみたのですが、ユークリッドは商が整数にならなければならないのでしょうか？2回目にユークリッドを使うときに商が3/8となってるのがまずいのでしょうか？ またこの問題はどう解いたらよいでしょうか？教えてください。
- 締切済み
- 数学・算数
- aとbをa=b=0でない２つの整数とする。a,bの公約数の集合の中の最
aとbをa=b=0でない２つの整数とする。a,bの公約数の集合の中の最大数dを、aとbの最大公約数といい、 d=(a,b)とかく 例えば(6,4)=2 このときar+bs＝(a,b)のような整数rとsが存在するというのを証明する。という問題です、教えてください。
- ベストアンサー
- 数学・算数
- アルゴリズムの問題です
以下のフローチャートは、基本選択法でデータを昇順（小→大）にソートしたものなのですが、整数の一次元配列に格納されているデータ（１００個）を降順（大→小）にソートするフローチャートを作成するには、どこの部分を変化させればいいのか教えていただけませんか？ 手書きなので見にくいですがよろしくお願いします。 開始 ｌ 整数配列A(100)と整数変数I,J,N,P,MIN,TEMPを宣言 ｌ データの個数N の値を読む ｌ ループ１の開始 I = 1,2,3, ・・・,N ｌ A(I)の値を読む ｌ ループ１の終了 ｌ ループ２の開始 I = 1,2,3, ・・・,N ｌ A(I)の値を出力 ｌ ループ２の終了 ｌ ループ３の開始 I = 1,2,3, ・・・,N-1 ｌ MIN = A(I) ｌ P = I ｌ ループ４の開始 J = I+1,I+2,I+3, ・・・,N ｌ ｌ yes A(J) < MIN ーーーーーー MIN = A(J) ｌ no ｌ ｌ P = J ｌ ｌ ｌ←ーーーーーーーーーーー ｌ ループ４の終了 ｌ TEMP = A(I) ｌ A(I) = A(P) ｌ A(P) = TEMP ｌ ループ３の終了 ｌ ループ５の開始 I = 1,2,3, ・・・,N ｌ A(I)の値を出力 ｌ ループ５の終了 ｌ 終了
- ベストアンサー
- その他([技術者向] コンピューター)
- 数学の整数の問題で分からないことがあります。
最大公約数が1である整数a,b,cはa^2+b^2=c^2を満たしている。 このとき、a,bのうち、一方が偶数であり、一方が奇数であることを 示せ。 まず2で割り切れるか割り切れないかということで、 a=2s+x,b=2t+y,c=2u+z(s,t,uは整数 x,y,z:0か1) とおいてa^2+b^2=c^2に代入してその結果が 2(2s^2+2sx+2t^2+2ty)+(x^2+y^2)=2(2u^2+2uz)+z^2・・・(1)となり、 この式から[x^2+y^2を2で割った余り]=[z^2を2で割った余り]となる。 解答ではここから更に(1)を 4(s^2+sx+t^2+ty)+(x^2+y^2)=4(u^2+uz)+z^2とし、 [x^2+y^2を4で割った余り]=[z^2を4で割った余り]として z=0の場合とz=1のときの場合分けで示しているのですが、 [x^2+y^2を2で割った余り]=[z^2を2で割った余り]の段階で z=0の場合とz=1のときの場合分けを使って考えてはいけないのは 何の不都合があるのでしょうか？
- ベストアンサー
- 数学・算数
補足
丁寧な説明ありがとうございました。