C语言程序（大数公约数）
本帖是有关于求大数的公约数，采用的是辗转相除法！大数存储在字符串当中！程序当中我分别重载了大数比较，大数相减，大数相除获得商与余数，可是调试中得不到正确结果 求助！真的很急，求各位大神帮帮忙
#include<stdio.h>
#include<string.h>
#define N 1001
int compare(char * c1,int s1,int e1,char *c2,int s2,int e2)/*大整数比较大小*/
{
while(c1[s1]=='0'&&s1<e1)s1++;
while(c2[s2]=='0'&&s2<e2)s2++;
if(e1-s1>e2-s2)return 0;
if(e1-s1<e2-s2)return 1;
int i1;int f11=0;
for(i1=0;i1<=e1-s1;i1++)
{
if(c1[s1+i1]>c2[s2+i1]){f11=1;break;}
if(c2[s2+i1]>c1[s1+i1])break;
}
if(i1>e1-s1||f11==1)return 0;
//if(f11)return 0;
return 1;
//return -1;
}
void sub(char *c1,int l1,char *c2,int n,int l)/*两个大整数相减,结果放在c1中*/
{
int fig=0;
if(l1>l)
{
fig=1;
int i5;
for(i5=l;i5>0;i5--)
c2[i5]=c2[i5-1];
c2[0]='0';l++;
}
int jw=0;
int i4;
char tc[N];
for(i4=l-1;i4>=0;i4--)
{
tc[i4]=((c2[i4]-48)*n+jw)%10+48;
jw=((c2[i4]-48)*n+jw)/10;
}
jw=0;
for(i4=l-1;i4>=0;i4--)
{
int ttt=jw;
if(c1[i4]-tc[i4]-jw>=0)
{
tc[i4]=c1[i4]-tc[i4]-jw+48;
jw=0;
}
else
{
jw=(tc[i4]-c1[i4]+jw);
if(jw%10==0)jw/=10;
else jw=jw/10+1;
tc[i4]=jw*10+c1[i4]-tc[i4]-ttt+48;
}
}
if(fig)
{
for(i4=0;i4<l-1;i4++)c2[i4]=c2[i4+1];
l--;
c2[l]='\0';
}
tc[l1]='\0';
for(i4=0;i4<=l1;i4++)
c1[i4]=tc[i4];
}
void high_precise_division(char *c1,char *c2)//求两个整数的余数
{
int len1,len2;
len1=strlen(c1);
len2=strlen(c2);
int i,j,k,ip;
i=0;
while(c1[i]=='0'&&i<len1-1)i++;
for(j=0;i<len1;j++,i++)c1[j]=c1[i];
len1=j;c1[j]='\0';
i=0;
while(c2[i]=='0'&&i<len2-1)i++;
for(j=0;i<len2;j++,i++)c2[j]=c2[i];
len2=j;c2[j]='\0';
/*while(c1[0]=='0'&&i<len1-1)
{
for(k=0;k<len1-1;k++)
c1[k]=c1[k+1];
len1--;
}去掉前面的0*/
/*while(c2[0]=='0'&&j<len2-1)
{
for(k=0;k<len2-1;k++)
c2[k]=c2[k+1];
len2--;
}去掉前面的0*/
c1[len1]='\0';
c2[len2]='\0';
if(strcmp(c2,"0")==0)return ;/*当除数为0时*/
if(strcmp(c1,"0")==0){strcpy(c2,"0");return ;}/*当被除数为0时*/
if(len1<len2||len1==len2&&compare(c1,0,len1-1,c2,0,len2-1)>0)
{
strcpy(c2,c1);
c1[0]='0';c1[1]='\0';
return ;
}
else
{
ip=0;
char product[N],*pr;/*部分积*/
pr=product;
for(ip=0;ip<len2-1;ip++)
pr[ip]=c1[ip];
for(i=0;i<=len1-len2;i++)
{
pr[ip++]=c1[len2-1+i];
if(ip>=len2&&compare(pr,0,ip-1,c2,0,len2-1)==0)
{
char tc[N];
for(j=1;j<=9;j++)
{
for(k=0;k<ip;k++)tc[k]=pr[k];
sub(tc,ip,c2,j,len2);/*pr-c2*j结果放在tc中*/
for(k=0;tc[k]!='\0';k++);
if(compare(tc,0,k-1,c2,0,len2-1)>0)
break;
}
strcpy(pr,tc);
ip=strlen(pr);
c1[i]=j+48;
while(pr[0]=='0'&&ip>1)
{
for(j=0;j<ip-1;j++)
pr[j]=pr[j+1];
ip--;
}
if(ip==1&&pr[0]=='0')ip--;
}
else c1[i]='0';
}
while(c1[0]=='0')
{
for(j=0;j<i-1;j++)
c1[j]=c1[j+1];
i--;
}
c1[i]='\0';
if(ip==0){pr[0]='0';pr[1]='\0';ip=1;}
else
{
while(pr[0]=='0'&&ip>1)
{
for(j=0;j<ip-1;j++)pr[j]=pr[j+1];
ip--;
}
}
for(j=0;j<ip;j++)
c2[j]=pr[j];
c2[ip]='\0';
return ;
}
}
int Judge(char *J)//判断字符串是否为0
{ int i;
for(i=0;i<strlen(J);i++)
{
if(J[i]!='0')
return 0;
}
return 1;
}
char* gcd(char* a,char* b)//辗转相除
{
char* m1=b;
int len1,len2;
len1=strlen(a);
len2=strlen(b);
//high_precise_division(a,b);
//char* m=b;
//int len1,len2;
// len1=strlen(a);
//len2=strlen(b);
char* c;
if (compare(a,0,len1-1,b,0,len2-1))
{
strcpy(c,a);//交换
strcpy(a,b);
strcpy(b,c);
}
high_precise_division(a,b);
char* m=b;
if (Judge(m))
{
//m=b;
return m1;
}
else
{
return gcd(m1,m);
}
}
int main()
{
int i,j;
char c1[N],c2[N];/*整数高精度除法*/
while(scanf("%s %s",c1,c2)!=EOF)
{
char *pc1,*pc2,*pc3;
pc1=c1;pc2=c2;
c1[strlen(c1)]='\0';
c2[strlen(c2)]='\0';
pc3=gcd(pc1,pc2);
//high_precise_division(pc1,pc2);/*结果放在pC1中，余数放在pC2中*/
//printf(" 商:%s\n",pc3);
puts(pc3);
}
return 0;
}
[解决办法]
先把大数的+-*/比较的函数写好。
[解决办法]
求公约数可以用另一种方法：
若x和y均为偶数, f(x,y) = 2*f(x/2, y/2) = 2* f(x>>1, y>>1)
若x为偶数，y为奇数， f(x,y) = f(x/2, y) = f(x>>1, y)
若x为奇数，y为偶数， f(x,y) = f(x, y>>1)
若x和y均为奇数，f(x,y) = f(y, x-y)，这样x-y必定为偶数，下一步可以除以2进行缩小。
[解决办法]
仅供参考
#include <iostream>
#include <string>
using namespace std;
inline int compare(string str1,string str2) {//相等返回0，大于返回1，小于返回-1
if (str1.size()>str2.size()) return 1; //长度长的整数大于长度小的整数
else if (str1.size()<str2.size()) return -1;
else return str1.compare(str2); //若长度相等，则头到尾按位比较
}
string SUB_INT(string str1,string str2);
string ADD_INT(string str1,string str2) {//高精度加法
int sign=1; //sign 为符号位
string str;
if (str1[0]=='-') {
if (str2[0]=='-') {
sign=-1;
str=ADD_INT(str1.erase(0,1),str2.erase(0,1));
} else {
str=SUB_INT(str2,str1.erase(0,1));
}
} else {
if (str2[0]=='-') {
str=SUB_INT(str1,str2.erase(0,1));
} else { //把两个整数对齐，短整数前面加0补齐
string::size_type L1,L2;
int i;
L1=str1.size();
L2=str2.size();
if (L1<L2) {
for (i=1;i<=L2-L1;i++) str1="0"+str1;
} else {
for (i=1;i<=L1-L2;i++) str2="0"+str2;
}
int int1=0,int2=0; //int2 记录进位
for (i=str1.size()-1;i>=0;i--) {
int1=(int(str1[i])-'0'+int(str2[i])-'0'+int2)%10;
int2=(int(str1[i])-'0'+int(str2[i])-'0'+int2)/10;
str=char(int1+'0')+str;
}
if (int2!=0) str=char(int2+'0')+str;
}
}
//运算后处理符号位
if ((sign==-1)&&(str[0]!='0')) str="-"+str;
return str;
}
string SUB_INT(string str1,string str2) {//高精度减法
int sign=1; //sign 为符号位
string str;
int i,j;
if (str2[0]=='-') {
str=ADD_INT(str1,str2.erase(0,1));
} else {
int res=compare(str1,str2);
if (res==0) return "0";
if (res<0) {
sign=-1;
string temp =str1;
str1=str2;
str2=temp;
}
string::size_type tempint;
tempint=str1.size()-str2.size();
for (i=str2.size()-1;i>=0;i--) {
if (str1[i+tempint]<str2[i]) {
j=1;
while (1) {//zhao4zhong1添加
if (str1[i+tempint-j]=='0') {
str1[i+tempint-j]='9';
j++;
} else {
str1[i+tempint-j]=char(int(str1[i+tempint-j])-1);
break;
}
}
str=char(str1[i+tempint]-str2[i]+':')+str;
} else {
str=char(str1[i+tempint]-str2[i]+'0')+str;
}
}
for (i=tempint-1;i>=0;i--) str=str1[i]+str;
}
//去除结果中多余的前导0
str.erase(0,str.find_first_not_of('0'));
if (str.empty()) str="0";
if ((sign==-1) && (str[0]!='0')) str ="-"+str;
return str;
}
string MUL_INT(string str1,string str2) {//高精度乘法
int sign=1; //sign 为符号位
string str;
if (str1[0]=='-') {
sign*=-1;
str1 =str1.erase(0,1);
}
if (str2[0]=='-') {
sign*=-1;
str2 =str2.erase(0,1);
}
int i,j;
string::size_type L1,L2;
L1=str1.size();
L2=str2.size();
for (i=L2-1;i>=0;i--) { //模拟手工乘法竖式
string tempstr;
int int1=0,int2=0,int3=int(str2[i])-'0';
if (int3!=0) {
for (j=1;j<=(int)(L2-1-i);j++) tempstr="0"+tempstr;
for (j=L1-1;j>=0;j--) {
int1=(int3*(int(str1[j])-'0')+int2)%10;
int2=(int3*(int(str1[j])-'0')+int2)/10;
tempstr=char(int1+'0')+tempstr;
}
if (int2!=0) tempstr=char(int2+'0')+tempstr;
}
str=ADD_INT(str,tempstr);
}
//去除结果中的前导0
str.erase(0,str.find_first_not_of('0'));
if (str.empty()) str="0";
if ((sign==-1) && (str[0]!='0')) str="-"+str;
return str;
}
string DIVIDE_INT(string str1,string str2,int flag) {//高精度除法。flag==1时,返回商; flag==0时,返回余数
string quotient,residue; //定义商和余数
int sign1=1,sign2=1;
if (str2 == "0") { //判断除数是否为0
quotient= "ERROR!";
residue = "ERROR!";
if (flag==1) return quotient;
else return residue ;
}
if (str1=="0") { //判断被除数是否为0
quotient="0";
residue ="0";
}
if (str1[0]=='-') {
str1 = str1.erase(0,1);
sign1 *= -1;
sign2 = -1;
}
if (str2[0]=='-') {
str2 = str2.erase(0,1);
sign1 *= -1;
}
int res=compare(str1,str2);
if (res<0) {
quotient="0";
residue =str1;
} else if (res == 0) {
quotient="1";
residue ="0";
} else {
string::size_type L1,L2;
L1=str1.size();
L2=str2.size();
string tempstr;
tempstr.append(str1,0,L2-1);
for (int i=L2-1;i<L1;i++) { //模拟手工除法竖式
tempstr=tempstr+str1[i];
tempstr.erase(0,tempstr.find_first_not_of('0'));//zhao4zhong1添加
if (tempstr.empty()) tempstr="0";//zhao4zhong1添加
for (char ch='9';ch>='0';ch--) { //试商
string str;
str=str+ch;
if (compare(MUL_INT(str2,str),tempstr)<=0) {
quotient=quotient+ch;
tempstr =SUB_INT(tempstr,MUL_INT(str2,str));
break;
}
}
}
residue=tempstr;
}
//去除结果中的前导0
quotient.erase(0,quotient.find_first_not_of('0'));
if (quotient.empty()) quotient="0";
if ((sign1==-1)&&(quotient[0]!='0')) quotient="-"+quotient;
if ((sign2==-1)&&(residue [0]!='0')) residue ="-"+residue ;
if (flag==1) return quotient;
else return residue ;
}
string DIV_INT(string str1,string str2) {//高精度除法,返回商
return DIVIDE_INT(str1,str2,1);
}
string MOD_INT(string str1,string str2) {//高精度除法,返回余数
return DIVIDE_INT(str1,str2,0);
}
int main() {
char ch;
string s1,s2,res;
while (cin>>s1>>ch>>s2) {
switch (ch) {
case '+':res=ADD_INT(s1,s2);break;
case '-':res=SUB_INT(s1,s2);break;
case '*':res=MUL_INT(s1,s2);break;
case '/':res=DIV_INT(s1,s2);break;
case '%':res=MOD_INT(s1,s2);break;
default : break;
}
cout<<res<<endl;
}
return(0);
}
