わり算

質問

Ｎ進数の数を配列を用いてのわり算を作りたいのですが、アルゴリズムを教えてください。

回答No.3

επιστημη（@episteme）

632÷25 を筆算で解いてみれば、
引き算と桁ずらしを繰り返しているのが体感できます。

63から25を引けるだけ引く -> 2 あまり 13
13をひと桁ずらし、2をつなぐ -> 132
132から25を引けるだけ引く -> 5 あまり 7
つなぐ桁がないのでおしまい。

したがって 632÷25 = 25 あまり 7
引いてはずらす、を繰り返しています。

補足

アドバイスありがとうございます。
参考にさせてもらい書いてみました！
でももう一息なんです・・・・・
コメントとかなくてすいませんがもし良ければ見てください。
#include<iostream.h>
#include<cstdlib>
#include<ctime>

using namespace std;

void plus(unsigned int CMPI1[4],unsigned int CMPI2[4],unsigned int CMPI[5]);
void minus(unsigned int CMPI1[4],unsigned int CMPI2[4],unsigned int CMPI[5]);
void crass(unsigned int cross1[4],unsigned int cross2[4],unsigned int cross[8]);

void plus(unsigned int CMPI1[4],unsigned int CMPI2[4],unsigned int CMPI[5])
{
for(int i=0;i<4;++i) CMPI[i]=0;
for(int i=0;i<4;++i)
{
if(CMPI[i]+CMPI1[i]+CMPI2[i]>=65536)
{
CMPI[i]=CMPI[i]+CMPI1[i]+CMPI2[i]-10;
CMPI[i+1]=1;
}
else CMPI[i]=CMPI[i]+CMPI1[i]+CMPI2[i];
}
}

void minus(unsigned int CMPI1[4],unsigned int CMPI2[4],unsigned int CMPI[5])
{
for(int i=0;i<4;++i) CMPI[i]=0;
for(int i=0;i<4;++i)
{
if(CMPI1[i]<CMPI2[i])
{
CMPI[i]=10+CMPI1[i]-CMPI2[i];
CMPI1[i+1]=CMPI1[i+1]-1;
}
else CMPI[i]=CMPI1[i]-CMPI2[i];
}
}

void crass(unsigned int cross1[4],unsigned int cross2[4],unsigned int cross[8])
{
long int kuri;
for(int i=0;i<4;++i)
{
for(int j=0;j<4;++j)
{
kuri=cross[i+j]+cross1[i]*cross2[j];
cross[i+j]=kuri%10;
cross[i+j+1]=cross[i+j+1]+kuri/10;
}
}
}

int main(void)
{
static unsigned int CMPI[5];
static unsigned int CMPI1[4];
static unsigned int CMPI2[4];
static unsigned int A[5];
static unsigned int Sho[4];
int keta1,keta2,S,kenchi_0,kenchi,mod_end,atai;

for(int i=0;i<4;i++) cin>>CMPI1[i];
cout<<"\n";
for(int i=0;i<4;i++) cin>>CMPI2[i];

for(keta1=3;CMPI1[keta1]==0;--keta1);//CMPI1の桁数ー１
for(keta2=3;CMPI2[keta2]==0;--keta2);//CMPI２の桁数ー１
cout<<keta2;cout<<"\n";
for(int i=keta2,j=keta1;i>=0;--i,--j) A[i]=CMPI1[j];

for(int t=keta1-keta2,mod_end=1;mod_end==1,t>=0;--t)
{
atai=0;
S=0;
if(t!=keta1-keta2)
{
if(A[keta2+1]!=0) atai=1;
}
kenchi_0=1;
if(atai==0)
{
for(int x=0;x<=keta2,A[keta2-x]<=CMPI2[keta2-x];++x)
{
if(A[keta2-x]<CMPI2[keta2-x]) kenchi_0*=0;
}
}
if(kenchi_0==0) S=0;
for(;kenchi_0==1;)
{
minus(A,CMPI2,CMPI);
for(int i=keta1;i>=0;--i) cout<<A[i];cout<<"\n";
for(int i=keta2;i>=0;--i) cout<<CMPI2[i];cout<<"\n";
for(int i=keta1;i>=0;--i) cout<<CMPI[i];cout<<"\n";
S++;
for(int x=0;x<=keta2,CMPI[keta2+atai-x]<=CMPI2[keta2+atai-x];++x)
{
if(CMPI[keta2+atai-x]<CMPI2[keta2+atai-x]) kenchi_0*=0;
}
if(kenchi_0==1)
{
for(int i=keta1+atai;i>=0;--i) A[i]=CMPI[i];
}
}cout<<S;

kenchi=1;
for(int x=0;x<=keta2,A[keta2-x]<=CMPI2[keta2-x];++x)
{
if(A[keta2-x]<CMPI2[keta2-x]) kenchi*=0;
}
if (t==0 && S==0) mod_end=0;
else
{
for(int k=keta1-keta2;k>=0;--k)
{
Sho[k+1]=Sho[k];
Sho[0]=S;
}
}
cout<<"%%";
if(t!=0)
{
for(int i=keta2;i>=0;--i) A[i+1]=CMPI[i];
A[0]=CMPI1[t-1];cout<<t<<" &"<<CMPI1[t-1]<<"\n";
}for(int i=keta1;i>=0;--i) cout<<A[i];cout<<"\n";
}

for(int i=keta1-keta2+1;i>=0;--i) cout<<Sho[i];

return(0);
}

回答No.2

επιστημη（@episteme）

まずＮ進数の数を配列を用いての引き算と掛け算とシフト(桁ずらし)を作ります。

あとは筆算での手順とおなじ。

補足

ありがとうございます。
　筆算の手順ですが、見当の付け方等どうしたらよろしいですか？
　また、シフトずらしはどのように作り、使うのでしょうか？

回答No.1

fukuchiyamashi

書いてみました。動きませんが。だれか見てやってください。
#include<iostream.h>
#include<cstdlib>
#include<ctime>

using namespace std;

int main (void)
{
static unsigned int A[3];
static unsigned int B[3];
static unsigned int C[3];
static unsigned int Sho[3];
unsigned short int keta1,keta2,kenchi_0,kenchi,i,j,k,kento,end1,end2,count;
unsigned long int S;

for(int i=0;i<4;i++) cin>>A[i];
cout<<"\n";
for(int i=0;i<4;i++) cin>>B[i];

for(keta1=3;A[keta1]==0;--keta1);
for(keta2=3;B[keta2]==0;--keta2);

kenchi_0=1;
for(i=keta1,j=keta2;j>=0,A[i]<=B[j];--i,--j)
{
if(A[i]<B[j]) kenchi*=0;
}

if(kenchi_0==1)
{
kento=A[keta1]/B[keta2];
end1=1;
for(count=0;count<2,end1==1;++count)
{
for(k=0;k<=keta2;++k) C[k]=0;
for(k=0;k<=keta2;++k)
{
S=B[k]*kento+C[k];
C[k]=S%10;
C[k+1]=S/10;
}
if(C[keta2+1]!=0) kento--;
else
{
kenchi=1;
for(i=keta1,j=keta2;j>=0,A[i]<=C[j];--i,--j)
{
if(A[i]<C[j]) kenchi*=0;
}
if(kenchi==0)kento--;
else
{
end1*=0;
Sho[0]=kento;
for(i=keta1-keta2,j=0;j<=keta2;++i,++j)
{
if(A[i]>=C[j])A[i]=A[i]-C[j];
else
{
A[i]=10+A[i]-C[j];
A[i+1]--;
}
}
}
}
}
}
else
{
kento=(A[keta1]*10+A[keta1-1])/B[keta2];
end1=1;
for(count=0;count<2,end1==1;++count)
{
for(k=0;k<=keta2;++k) C[k]=0;
for(k=0;k<=keta2;++k)
{
S=B[k]*kento+C[k];
C[k]=S%10;
C[k+1]=S/10;
}
kenchi=1;
for(i=keta1,j=keta2+1;A[i]<=C[j],j>=0;--i,--j)
{
if(A[i]<C[j]) kenchi*=0;
}
if(kenchi==0) kento--;
else
{
end1=0;
Sho[0]=kento;
for(i=keta1-keta2-1,j=0;j<=keta2+1;++i,++j)
{
if(A[i]>=C[j]) A[i]=A[i]-C[j];
else
{
A[i]=10+A[i]-C[j];
A[i+1]--;
}
}
}
}

end2=1;
for(int x=keta1+kenchi_0-1;x>=keta2,end2==1;--x)
{
kenchi=1;
for(i=x,j=keta2;j>=0,A[i]<=B[j];--i,--j)
{
if(A[i]<B[j]) kenchi*=0;
}
if(kenchi==0)
{
for(i=2;i>=0;--i) Sho[i+1]=Sho[i];
Sho[0]=0;
}
else
{
kento=(A[x]*10+A[x-1])/B[keta2];
end1=1;
for(count=0;count<2,end1==1;++count)
{
for(k=0;k<=keta2;++k) C[k]=0;
for(i=0;i<=keta2;++i)
{
S=C[i]+B[i]*kento;
C[i]=S%10;
C[i+1]=S/10;
}
for(i=x,j=keta2+1;j>=0,A[i]<=C[j];--i,--j)
{
if(A[i]<C[j]) kenchi*=0;
}
if(kenchi==0) kento--;
else
{
end1=0;
for(i=2;i>=0;--i) Sho[i+1]=Sho[i];
Sho[0]=kento;
for(i=x-keta2-1,j=0;j<=keta2+1;++i,++j)
{
if(A[i]>=C[j]) A[i]=A[i]-C[j];
else
{
A[i]=10+A[i]-C[j];
A[i+1]--;
}
}
}
}
}
if(x==keta2)
{
for(i=x,j=keta2;j>=0;--i,--j)
{
if(A[i]<B[j]) end2*=0;
}
}
}

}
for(i=0;i<=4;++i) cout<<Sho[i]<<" ";
return(0);
}