• ベストアンサー

ユークリッドの互除法について

ユークリッドの互除法を用いて a*e+b*Phi=1 となるようなa,bを求めるプログラムを作りたいのですが 以下のようにしても正しい値になりません どこが間違っているのでしょうか？ e=53499289; Phi=96298720; d=0; d_old=1; Psi=1; Psi_old=0; for (;Phi!=0;){ a= e/Phi; h=e; e=Phi; Phi= h%Phi; h=d_old; d_old=d; d=h-d*a; h=Psi_old; Psi_old=Psi; Psi=h-Psi*b; } if (e<0){ b=-e; }else{ b=e; } printf ("(%d)*e+(%d)*Phi_n=%d\n", d_old,Psi_old,b); 正しくは 9*e+(-5)*Phi=1 となるはずです

質問者が選んだベストアンサー

  • ベストアンサー
  • php504
  • ベストアンサー率42% (926/2160)
回答No.2

変数がわかりにくかったので勝手に変えました #include <stdio.h> int main(void) { int q; int n, n1, n2; int a, a1, a2; int b, b1, b2; n = 53499289; n1 = 96298720; a = 1; a1 = 0; b = 0; b1 = 1; for (;n1 != 0;){ q = n / n1; n2 = n % n1; a2 = a - q*a1; b2 = b - q*b1; n = n1; n1 = n2; a = a1; a1 = a2; b = b1; b1 = b2; } printf ("(%d)*x+(%d)*y=%d\n", a, b, n); return 0; }

mofmof03
質問者

お礼

Psi=h-Psi*bのbをaにすればよかったんですね ありがとうございます

その他の回答 (1)

  • asuncion
  • ベストアンサー率33% (2126/6286)
回答No.1

コードを掲載するときは、断片ではなく コンパイルできる形の全文を掲載してください。 > Psi=h-Psi*b; bに何が入っているかわからない状態で この文を実行している点に問題があります。

mofmof03
質問者

お礼

わかりました、気をつけます。 ありがとうございます

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • ユークリッド互除法

    ユークリッド互除法を使用して最大公約数を求めるプログラムを、C言語で書いてみました。 #include <stdio.h> main() { int a, b, t; scanf("%d %d", &a, &b); if(a<b){ t=a; a=b; b=t; } while(b != 0){ t = a % b; a = b; b = t; } printf("GCD = %d\n", a); return 0; } これを、もっと簡略化できるらしいのですが、これ以上できることはありますか？ どう考えてもわかりません

  • ユークリッドの互除法

    二つの整数a,bの最大公約数dを、ユークリッドの互除法で求める方法は分かります。 そうして求めたdは、適当な数x,yを使い、d=ax+byで表せることも何とか分かります。 しかし、d=ax+byが与えられたとき、ユークリッドの互除法を使って、特殊解xとyをどうやって求めたらよいのかが分かりません。 これまでの書き込みを見ても理解ができませんでした。 どなたか分かりやすくお教えください。

  • ユークリッドの互除法

    ユークリッドの互除法をJavascriptで書こうとしてます。以下のように書いたのですが、うまく動きません。(45と60の最大公約数を求めるプログラム) <script> window.alert(gcd(45, 60)); function gcd(a, b){ var r=a%b; if(r==0){ return b; }else{ gcd(b, r); } } </script> undifinedとなってしまいます。どうしたら正確な答えが出るでしょうか？

  • ユークリッドの互除法の証明

    ユークリッドの互除法なんですが、これを使った証明がわからないので質問させてください。 a,bは正の整数で、b≦aである。 r_0=a、r_1=bとしq_iとr_iは整数で0<r_i<r_(i-1)である。(qについては特に指示はありません) このとき r_0=r_1*q_1+r_2 r_1=r_2*q_2+r_3 ・ ・ ・と続き r_(n-2)=r_(n-1)*q_(n-1)+r_n r_(n-1)=r_n*q_n が成り立つ。 n≧2の時、ユークリッドの互除法はgcd(a,b)=ax+byとなる整数(x,y)を持つことを証明しなさい。 これは帰納法を使えばいいのでしょうか？ n=2の時にr_2=r_0-r_1*q_1が成り立つことはr_(n-1)=r_n*q_n にn=2を代入して示せるのですがn=k、n=k+1の時にどうすればうまく証明できるのかわかりません。 どなたか教えて下さい。

  • ユークリッドの互除法

    ユークリッドの互除法の処方でつまづいています。 どなたか教えて頂けませんか。 aとbは正の整数でb≦aの関係にある。 aとbの最大公約数gcd(a,b)。 この時gcd(a,b)=ax+byの解となる(x,y)のペアはいくついるのでしょうか? 直感ですと(x,y)は一つしか存在しないように感じるのですが、どうやって記述すればいいのでしょうか？ よろしくお願いします。

  • ユークリッドの互除法

    ユークリッドの互除法の証明の一部なのですが aをで割った商をbあまりをrとすると a=bq+r であるので　r=a-bq である。ここで、この右辺はa bの最大公約数でわり切れるのは、なぜか教えて下さい。あと　a bの最大公約数がrとb の公約数でもあるのはなぜですか？お願いします。

  • ユークリッドの互除法についての問題です。

    ユークリッドの互除法についての問題です。 a,bが任意の整数のとき、次の式を満たす整数xは必ずあるか。 (1)aが5の倍数でないとき　ax≡b (mod5) (2)aが4の倍数でないとき　ax≡b (mod4) 誰か教えてください。

  • C言語の配列の使い方について質問です。

    以下のプログラムを配列を使って見やすくしたいのですが、どのように作ったら良いでしょうか？ 宜しくお願いします。 #include<stdio.h> int main(void) { int a, b, c, d, e, f, g, h, i, j, k, l, m ,n, o; /*5段目の処理*/ for(a = 1; a <= 15; a++) { for(b = 1; b <= 15; b++) { if(a == b) continue; for(c = 1; c <= 15; c++) { if(a == c || b == c) continue; for(d = 1; d <= 15; d++) { if(a == d || b == d || c == d) continue; for(e = 1; e <= 15; e++) { if(a == e || b == e || c == e || d == e) continue; // printf("%d %d %d %d %d\n", a, b, c, d, e); ////4段目//// if(a>b){ f=a-b; } else if(a<b){ f=b-a; } if(b>c){ g=b-c; } else if(b<c){ g=c-b; } if(c>d){ h=c-d; } else if(c<d){ h=d-c; } if(d>e){ i=d-e; } else if(e<d){ i=e-d; } // printf(" %d %d %d %d \n", f, g, h, i); /////3段目//// if(f>g){ j=f-g; } else if(f<g){ j=g-f; } if(g>h){ k=g-h; } else if(g<h){ k=h-g; } if(h>i){ l=h-i; } else if(h<i){ l=i-h; } // printf(" %d %d %d \n", j, k, l); /////2段目//// if(j>k){ m=j-k; } else if(j<k){ m=k-j; } if(k>l){ n=k-l; } else if(k<l){ n=l-k; } // printf(" %d %d \n", m, n); /////三段目///// if(m>n){ o=m-n; } else if(m<n){ o=n-m; } // printf(" %d \n", o); if(a != b != c != d != e != f != g != h != i != j != k != l != m != n != o){ printf("%d %d %d %d %d\n", a, b, c, d, e); printf(" %d %d %d %d \n", f, g, h, i); printf(" %d %d %d \n", j, k, l); printf(" %d %d \n", m, n); printf(" %d \n", o); } } } } } } }

  • ユークリッドの互除法について

    質問させて頂きます。　　 （有理整数環Ｚにωを添付した整域Z[ω]をＲとする。Ｒ=Z[ω]={a+bω}において） ω=(-1+√3i)/2 とした場合、α=16+14ω、β=11+9ω　の最大公約元、最小公倍元の求め方をユークリッド互除法にて教えて下さい。 よろしくお願いいたします。

  • C言語　初心者です

    Cで計算して出た結果をエクセルに出力するやり方を教えて下さい。 #include<stdio.h> #include<math.h> double V(double x) { double pot=0.0; if (x >-1 && x<1) { pot=-2.0; } return(pot); } double F(double psi, double E,double x) { return(2.*(V(x)-E)*psi); } int main() { double E; int i,j; double psi,psi1,phi,phi1,x,dx; psi=0.01; phi=0.01; scanf("%1f",& E); x=-5.; i=5; dx=pow(10,-i)*10.0; for(j=0;j<pow(10,i);j++) { psi1=psi+phi*dx; phi1=phi+F(psi,E,x)*dx; x=x+dx; psi=psi1; phi=phi1; if((j+1)/5000*5000==j+1) { printf("x=%f phi= %f psi= %f\n",x,phi,psi); } } }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する