标题:[求助]大数除法问题
只看楼主
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
得分:0 
以下是引用穆扬在2006-7-21 21:14:52的发言:

实际上20楼最大的问题是那个全局变量
如果main中调用to_decimal两次
破绽就出来了

20楼的斑竹,如果是八进制的34564567456123456577654322343545
你的程序能输出吗?

楼上两位的争论我看了,先回答穆扬老兄的,楼主的问题并不需要调用那个函数两次,这很明显可以看出来,所以问题不存在;
至于楼主,我真的很好奇,您是搞数值计算的吗?如果您要求实现高位的转换,可以通过数组来装,类似的方法就像那个八进制转换为十进制的问题一样,相信这也是可以解决,当然上面的那个函数是不能用了


对不礼貌的女生收钱......
2006-07-24 13:38
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
得分:0 
不过还是要谢谢两位的提醒.特别是穆扬老兄,您这吹毛求疵的习惯对人可是大有帮助!

对不礼貌的女生收钱......
2006-07-24 13:40
穆扬
Rank: 1
等 级:禁止发言
帖 子:1910
专家分:0
注 册:2006-6-1
得分:0 
提示: 作者被禁止或删除 内容自动屏蔽

2006-07-25 00:51
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
得分:0 
穆扬的话在理。
全局变量又不是不能用,你不用也不能强迫人家不能用吧。如果不用学它做什么?
小的程序是应该少用全局变量的。
函数就一定得调用两次以上,调用的次数越多只能说明你的函数效率高,代码重用度好。
函数是一个功能模块而已。

倚天照海花无数,流水高山心自知。
2006-07-25 10:55
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
得分:0 
恩,两位说得好,倒是我偷懒了,
楼主这个题,我有空会再想想,努力把两位所提出的问题都解决.

对不礼貌的女生收钱......
2006-07-25 19:12
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
得分:0 

楼主再看下这个程序 程序理论上可处理3000多位,当然实际上位数太多,计算机肯定运行不过来.
您再帮我测试一下,下午匆匆写完,只测了几个数,算法我等等再发给你吧:
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#include "math.h"
#include "ctype.h"
#include "string.h"
#define MAX_SIZE 50

void multi(int *a,int *result,int base);
void power(int time,int *result,int base);
void transform(int *result,char *str,int base);
int cal_len(long sum);
int residue(int *result,long sum);
int check(char *str,int base);

int main()
{
int base,flag=0,i,j,sum=0,result[MAX_SIZE*4]={0};
long resi=0;
char str_num[MAX_SIZE];
puts("Enter the base:");
scanf("%d",&base);
fflush(stdin);
puts("Now enter the number:");
do
{
if(flag)
puts("Input Wrongly! Enter again:");
gets(str_num);

}while((flag=check(str_num,base)));


for(i=0;i<strlen(str_num);sum+=str_num[i++]-48);
transform(result,str_num,base);
i=residue(result,(long)sum);
for(j=i;j>=0;j--)
resi+=(long)result[j]*(long)pow(10,j);
resi%(long)sum?puts("Not niven number!"):puts("Yes,it's a niven number!");
system("pause");
}
int residue(int *result,long sum)
{
int i,j,k,flag=0,length=cal_len(sum);
long trans=0;
char str_num[11];/*long型最多2147483647,刚好10位*/
while(1)
{
for(i=MAX_SIZE*4-1;!result[i];i--);
if(i-length<=0)
return i;
for(j=i-length;j<=i;j++)
trans+=(long)result[j]*(long)pow(10,j+length-i);
if(trans<sum)
{
trans=0;
flag=1;
for(j=i-length-1;j<=i;j++)
trans+=(long)result[j]*(long)pow(10,j+length+1-i);
}
trans%=sum;
ltoa(trans,str_num,10);
k=strlen(str_num);
if(flag)
{
for(j=i-length-1;j<=i;j++)
{
k--;
if(k>=0)
result[j]=str_num[k]-48;
else
result[j]=0;
}
}
else
{
for(j=i-length;j<=i;j++)
{
k--;
if(k>=0)
result[j]=str_num[k]-48;
else
result[j]=0;
}
}
trans=0,flag=0;
}
}
int cal_len(long sum)
{
int length=0;
long num=sum/10;
while(num>0)
length++,num/=10;
return length;
}
int check(char *str,int base)
{
int i=0;
while(str[i])
{
if(!isdigit(str[i])) return 1;
if(str[i++]>=base+48) return 1;
}
return 0;
}
void power(int time,int *result,int base)
{
int i=0,a1[MAX_SIZE*4]={0},a2[MAX_SIZE*4]={0};
if(time)
{
a1[0]=base;
while(++i!=time)
{
if(i%2)
multi(a1,a2,base);
else
multi(a2,a1,base);
}
if(time%2)
{
for(i=0;i<MAX_SIZE*4;i++)
result[i]=a1[i];
}
else
{
for(i=0;i<MAX_SIZE*4;i++)
result[i]=a2[i];
}
}
else result[0]=1;
}
void multi(int *a,int *result,int base)
{
int i,j,k;
for(k=MAX_SIZE*4-1;!a[k];k--);
for(i=0;i<MAX_SIZE*4;result[i++]=0);
for(j=0;j<=k;j++)
{
result[j+1]+=result[j]/10;
result[j]%=10;
result[j]+=a[j]*base;
result[j+1]+=result[j]/10;
result[j]%=10;
}
}
void transform(int *result,char *str,int base)
{
int i,j,k=strlen(str);
for(i=0;i<k;i++)
{
int transi1[MAX_SIZE*4]={0},transi2[MAX_SIZE*4]={0};
power(k-i-1,transi1,base);
multi(transi1,transi2,str[i]-48);
for(j=0;j<MAX_SIZE*4-1;j++)
{
result[j]+=transi2[j];
result[j+1]+=result[j]/10;
result[j]%=10;
}
}
}


对不礼貌的女生收钱......
2006-07-26 19:44
soft_wind
Rank: 3Rank: 3
等 级:新手上路
威 望:8
帖 子:1430
专家分:0
注 册:2006-4-5
得分:0 

主要算法还是前面提到的:
step1:存入字符串str_num[];
step2:把各位相加,sum+=str_num[i++]-48;
step3:把str_num中的字符转换为十进制数result;
step4:result%sum?puts("no"):puts("yes");

前3步实现比较快,第3步的算法和那个8进制转化为10进制十分相似.由于result是用数组来存储,所以为实现除法加大了难度,我主要说说第4步的算法.
程序每次从result数组的最高位依次往下取和sum一样长的长度位(如果取下的几位构成的数大于sum);或者取比sum的位数长度还多1位(总之,必须满足至少能够上商1);取下来的数构成一个数trans.用trans和sum求余,余数存在trans中,重新归入result数组中,如此循环直到result数组剩下的有效位长度小于等于sum为止.
取下result剩下的有效位构成一个数resi.判断resi%sum的余数情况即可。

当位数太多(超过3500上)时,sum为int型有可能也将不够大,上述的程序也将不能用,此时需要把sum也用数组来存储,求余函数(residue)就将更复杂一些.


对不礼貌的女生收钱......
2006-07-26 20:35
c__06
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2010-1-27
得分:0 
nm
2010-01-27 02:32
c__06
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2010-1-27
得分:0 
回帖切磋是一种美德,每天回帖即可获得10分可用分!
2010-01-31 02:21
c__06
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2010-1-27
得分:0 
回复 5楼 nuciewth
很好。但是没有程序,哎
2010-01-31 02:37



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-78712-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.283617 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved