多項式のユークリッドの互除法を解くプログラミング

質問

二つの多項式（ＡとＢ）を割り算し、出た余り（Ｃ）を割る数、割る数（Ｂ）を割られる数にし、余りが０になるまで割り算を行うプログラムをＣ言語で作っています。
例
Ａ÷Ｂ＝商・・・余りＣ
Ｂ÷Ｃ＝商・・・余りＤ
Ｙ÷Ｚ＝商・・・余り０

以下失敗したプログラム
#include <stdio.h>
int main(void)
{
int m,m2,i,j,k;
int a[1000],b[1000],c[1000],d[1000],e[1000];

puts("何次の多項式ですか？");
printf("１つめ:"); scanf("%d",&m);
printf("２つめ:"); scanf("%d",&m2);

puts("１つめの多項式の係数を入力してください。");
for(i=m;i>=0;i--){
scanf("%d",&a[i]);
}
puts("２つめの多項式の係数を入力してください。");
for(i=m2;i>=0;i--){
scanf("%d",&b[i]);
}

printf("一回目の商は\n");
for(l = 1 ;l>=0;l--){
for(k=m-m2;k>=0;k--){
c[k]=a[m - (m - m2 - k)]/b[m2];
printf("%d ",c[k]);//商の表示
j = m2;
for(i = m - (m - m2 - k);i>= m - (m - m2 - k) - m2 ;i--){
d[i]=a[i]-c[k]*b[j];
a[i]=d[i];
j=j-1;
}
}
m=m2;
m2=m2-1;
a[l]=b[l];
b[l]=d[l];
}

printf("\n");
for(i = m - (m - m2 - k);i>= m - (m - m2 - k) - m2+1 ;i--){
d[i]=a[i]-c[0]*b[j];
a[i]=d[i];
j=j-1;
printf("%d ",d[i]);
}
return(0);
}
間違いがわかる人は教えてください、お願いします

回答No.3

himajin100000 · ベストアンサー

#include <stdio.h>
#include <math.h>
/*
質問文から続けて書いたら思ったより嵌った
変数名を整理したりすればもっときれいになるはずだし，

Oh-Orangeさんのように構造体なりを使えばこんなに苦労はしないと思う。
*/
int main(void)
{

int m,m2,i,j,k,l,n,p,q;
double a[1000],b[1000],c[1000],d[1000],e[1000];

puts("何次の多項式ですか？");
printf("１つめ:"); scanf("%d",&m);
printf("２つめ:"); scanf("%d",&m2);

puts("１つめの多項式の係数を入力してください。");
for(i=m;i>=0;i--){
scanf("%lf",&a[i]);
}
puts("２つめの多項式の係数を入力してください。");
for(i=m2;i>=0;i--){
scanf("%lf",&b[i]);
}

q = 1;
l = 0;
while(q == 1){
q = 0;
printf("--\n");
printf("%d回目の商は",l+1);

for(k=m-m2;k>=0;k--){

c[k] = a[m - (m - m2 - k)] / b[m2];
printf("%lfx^%d + ",c[k],k);//商の表示
j = m2;
for(i = m - (m - m2 - k);i>= m - (m - m2 - k) - m2 ;i--){
d[i]=a[i]-c[k]*b[j];
a[i] = d[i];

j = j - 1;
}

}
printf("\n");
for (k = m2;k >=0 ;k--){
a[k] = b[k];
}
for (k = m-m2;k >=0 ;k--){
b[k] = d[k];
if (d[k] != 0){
q = 1;
}
}
for (k = 0;k <= 1000;k++){
d[k] = 0;
}
while(b[m2] == 0){
m2 = m2 - 1;
}
if (m2 <= 0){
break;
}

printf("q:%d\n",q);
p = m2 - 1;
m = m2;
m2 = p;
l = l + 1;
printf("\n");

}
if (q == 0){
printf("割り切れた");
}else{
printf("割り切れなかった");
}
return(0);
}

回答No.4

himajin100000

多分順番間違えている

printf("q:%d\n",q);
p = m2 - 1;
m = m2;
m2 = p;
l = l + 1;
printf("\n");

while(b[m2] == 0){
m2 = m2 - 1;
}
if (m2 <= 0){
break;
}

回答No.2

Oh-Orange

★最初に
＞多項式のユークリッドの互除法を解くプログラミング…
　↑
　この多項式とは配列を用いて桁数の大きい数を表現して計算させるものでしょうか？
　俗に『多倍長演算』という事ですか？
・もしもそのような演算でユークリッドの互除法を行うならば、まず割り算(あまり)を
　正確に計算できるルーチンを作ります。
　割り算のアルゴリズムをきちんと整理しないと何時まで経っても完成しませんので
　小学生で習った『筆算』の方法を参考に実装します。
・考え方は次の通り。
　(1)『被除数の桁数』を『除数の桁数』に合わせて切り出す。→これが最終的な『あまり』の数。
　(2)『被除数』÷『除数』を行う。→ここがポイント
　(3)『被除数』－『中間の商』×『除数』＝『中間のあまり』
　(4)『被除数』を１要素分だけ左方向にずらして１要素分の『被除数』を補う。
　(5)(1)へ戻り繰り返し計算。
　(6)『被除数』の一の位までを繰り返したら除算ループを終了
　このアルゴリズムで除算を行うと同時にあまりも計算されます。
・質問にあるソースをざっと見た限りでは『除算』そのものが多項式に対応していないような気がします。
　多項式÷配列の１つ＝１回目という考えて行っているのでしょうかね。ソースは？
　この方法だと収束するまでに時間が掛かりすぎますし、あまりお勧めではありません。
　まずは１つの数の『多項式』を分かりやすい構造体を使って表現して減算、除算、除算(剰余)の
　それぞれの処理を関数で分けたほうが良いですよ。見やすいしね。→main一本(１つの関数)では
　処理が長くなりすぎますので分けましょう。

サンプル:

// 構造体の一例
struct bignum_t {
　int len;
　int num[ 1000 ];
} stBIGNUM, *lpBIGNUM;

// プロトタイプ宣言の一例
int cmp( lpBIGNUM a, lpBIGNUM b );　// 比較
void sub( lpBIGNUM ans, lpBIGNUM a, lpBIGNUM b );　// 減算
void mul( lpBIGNUM ans, lpBIGNUM a, lpBIGNUM b );　// 乗算
void div( lpBIGNUM ans, lpBIGNUM a, lpBIGNUM b, lpBIGNUM r );　// 除算＆剰余(あまり)

// 肝心の除算(サブ関数を４つに分ければ分かりやすい)
void div( lpBIGNUM ans, lpBIGNUM a, lpBIGNUM b, lpBIGNUM r )
{
　int bottom = (a->len - b->len);

　if ( a->len == 0 ){
　　return;　// aがゼロの処理
　}
　if ( b->len == 0 ){
　　return;　// bがゼロの処理(ゼロ除算エラーなど)
　}
　// ans構造体の初期化(ゼロで埋める)
　memset( ans, 0, sizeof(stBIGNUM) );
　// 筆算方式の除算
　for ( divStart(r,a,bottom) ; ; divShift(r,a->num[bottom]) ){
　　ans->num[ bottom ] = divValue( r, b );

　　if ( --bottom < 0 ){
　　　lenAdjust( ans );　// lenメンバの補正
　　　return;
　　}
　}
}

// サブ関数のプロトタイプ宣言
void lenAdjust( lpBIGNUM ans );
void divStart( lpBIGNUM r, lpBIGNUM a, int bottom );
void divShift( lpBIGNUM r, int value );
int　divValue( lpBIGNUM r, lpBIGNUM b );

以上。参考に。

お礼

わざわざわかりやすくサンプルまでありがとうございますm(_ _)m
Ｃ言語始めたばかりで構造体や関数もよくわからないので勉強してみます＾＾；

回答No.1

himajin100000

ちょっと待ってね。まだ考えてなくて少ししたら考えてみるつもり。
当時ソース張ったけど，
あれ，整形し忘れて「あちゃー」っと回答してから思い(汗)
そのまま締め切られた記憶が蘇ってきて
懐かしかったから

(↓当時の)
http://aol.okwave.jp/qa3514558.html

お礼

あの時はありがとうございましたm(_ _)m
本当に助かりました！
最終的に多項式の因数分解のプログラムを作らなきゃいけないんですが正直実力以上のことをやらされてるものでかなり欝です・・・