| FreeFox 回复于：2002-11-04 19:38:25
|
网上有算圆周率的原码，建议去看看。
|
| siupan 回复于：2002-11-04 21:17:16
|
能否推介一個??
|
| 真无极 回复于：2002-11-04 21:27:05
|
不要用递归来实现
用公式来实现看看
|
| syo 回复于：2002-11-04 21:29:39
|
用数组来储存
|
| 真无极 回复于：2002-11-04 21:39:20
|
另外可以用long long
因为double保存数据时可能会有舍入的情况
|
| JohnBull 回复于：2002-11-04 23:36:04
|
恐怕再怎么long也没用，69！就已经大约1.7e98了，需要327bit才能表示！
恐怕你只能考虑用字符串模拟数字运算了。
|
| siupan 回复于：2002-11-05 10:35:05
|
我也是這樣想的, 但太複習, 怎也寫不好, 救救我!!
|
| syo 回复于：2002-11-05 11:47:30
|
每一位分别存储在数组里就行了
|
| michael009 回复于：2002-11-05 12:11:13
|
同意syo的说法，如下：
void main(void)
{
int Data[10000];
int Digit;
int i,r,j,k;
int N;
for(i=1;i<10000+1;i++)
Data[i]=0;
Data[0]=1;
Data[1]=1;
Digit=1;
printf("Enter a number what you want to calculus:" ;
scanf("%d",&N);
for(i=1;i<N+1;i++)
{
for(j=1;j<Digit+1;j++)
Data[j]*=i;
for(j=1;j<Digit+1;j++)
{
if(Data[j]>10)
{
for(r=1;r<Digit+1;r++)
{
if(Data[Digit]>10)
Digit++;
Data[r+1]+=Data[r]/10;
Data[r]=Data[r]%10;
}
}
}
printf("%d!=",i);
for(k=Digit;k>0;k--)
printf("%d",Data[k]);
printf("\n";
}
}
|
| siupan 回复于：2002-11-05 19:03:33
|
出來的答案是錯的....
如69!就與windows的小算盤所出答案不一樣
|
| siupan 回复于：2002-11-05 19:04:12
|
忘了道謝
先謝了!
|
| syo 回复于：2002-11-05 23:26:17
|
[这个贴子最后由syo在 2002/11/05 11:28pm 编辑]
#include <stdio.h>
void main()
{
int i,j,k,r;
int data[1000];
int n;
int digit;
for (i=1;i<1000+1;i++)
data[i]=0;
data[0]=1;
data[1]=1;
digit=1;
printf("Enter a number what you want tocalculus:";
scanf("%d",&n);
for(i=1;i<n+1;i++)
{
for(j=1;j<digit+1;j++)
data[j]*=i;
for(j=1;j<digit+1;j++)
{
if (data[j]>=10)
for(r=1;r<digit+1;r++)
{
if (data[digit]>=10)
digit++;
data[r+1]+=data[r]/10;
data[r]=data[r]%10;
}
}
}
printf("%d! = ",n);
for (k=digit;k>0;k--)
printf("%d",data[k]);
printf("\n";
}
|
| syo 回复于：2002-11-05 23:37:34
|
我靠，怎么我的程序的行缩进都不行呀
真难看呀
……
这程序不是我写的......
|
| syo 回复于：2002-11-05 23:38:51
|
你应该看看数据结构
|
| JohnBull 回复于：2002-11-05 23:40:08
|
[quote][b]下面引用由[u]siupan[/u]在 [i]2002/11/05 10:35am[/i] 发表的内容：[/b]
我也是這樣想的, 但太複習, 怎也寫不好, 救救我!!
[/quote]
连这都觉得复杂？
思路已经知道了，拿出60分钟先把框图画出来，画不出来改行。
|
| pydwh 回复于：2002-11-05 23:45:07
|
To syo
可不可以介绍一下你的解题思路和怎样确定你这个算法的上限，我试了一下，在n=450范围内可以正常运行。超过450就有问题，我怀疑是数组越界造成的？
|
| pydwh 回复于：2002-11-06 00:27:09
|
哎，原来找不到第一个用这种算法做的人，要不就可以问问他（她）是怎么想到这样来解决的。
|
| siupan 回复于：2002-11-06 01:42:05
|
受益不淺!!
謝謝指教!!
|
| syo 回复于：2002-11-06 17:44:04
|
[这个贴子最后由syo在 2002/11/06 06:38pm 编辑]
[quote][b]下面引用由[u]pydwh[/u]在 [i]2002/11/05 11:45pm[/i] 发表的内容：[/b]
To syo
可不可以介绍一下你的解题思路和怎样确定你这个算法的上限，我试了一下，在n=450范围内可以正常运行。超过450就有问题，我怀疑是数组越界造成的？
[/quote]
450以后就超过我定的数组1000位了
你可以把第5和第9行的1000加大就行了。
|
| pydwh 回复于：2002-11-06 17:48:12
|
To syo:
我猜也是这样。关键是能不能由设定的数组的大小，就直接推出n的取值范围；或者知道n来确定要设定的数组的大小。望指教！
|
| syo 回复于：2002-11-06 18:27:30
|
[这个贴子最后由syo在 2002/11/06 06:39pm 编辑]
思路：
声明一个大小为xxx的数组,负责存储每一位的数据,变量digit为计算位数的变量,i,j,r,k为循环中记数的变量.
data(0)存放0的阶乘.
开始时,使第一位为1,位数为1,将每次相乘后的乘积存入数组.
循环处理每个数组中超过10的数字,
若值大于10,则digit++,原来的数除以10,
其商加上后一位的数值后存入后一位的数组中,余数存入原来的数组里.
循环计算结束后,打印出n!=......
|
| syo 回复于：2002-11-06 18:38:27
|
[这个贴子最后由syo在 2002/11/06 11:22pm 编辑]
不知道
|
| michael009 回复于：2002-11-07 11:04:34
|
[quote][b]下面引用由[u]syo[/u]在 [i]2002/11/06 05:44pm[/i] 发表的内容：[/b]
450以后就超过我定的数组1000位了
你可以把第5和第9行的1000加大就行了。
[/quote]
不能这么做，syo你看我的程序，已经这么做了，我们的程序是一样的，可是阶数稍微高一点就出错，就是计算结果是错误的，我怀疑是c自身的原因，求不了太高阶数的阶乘，有谁可以指导一下？是不是这个原因？谢谢
|
| JohnBull 回复于：2002-11-07 11:12:46
|
用malloc动态调整数组digit[]的大小。
先开10k，一旦发现不够就用realloc再加10k……
|
| michael009 回复于：2002-11-07 11:17:12
|
[这个贴子最后由michael009在 2002/11/07 11:18am 编辑]
谢谢，我试一下
|
| syo 回复于：2002-11-07 14:46:28
|
[这个贴子最后由syo在 2002/11/07 03:33pm 编辑]
我认为这和语言本身有关，
c语言本身对int的大小就有一个限制
我在vc6.0中调试了以下，发现程序中数组最大可以是[b]258552[/b]位
超过这个大小就无法算出n!的值
不过,25万位,也该足够用了吧..
|
| syo 回复于：2002-11-07 15:32:40
|
[quote][b]下面引用由[u]michael009[/u]在 [i]2002/11/07 11:04am[/i] 发表的内容：[/b]
不能这么做，syo你看我的程序，已经这么做了，我们的程序是一样的，可是阶数稍微高一点就出错，就是计算结果是错误的，我怀疑是c自身的原因，求不了太高阶数的阶乘，有谁可以指导一下？是不是这个原因？谢谢
[/quote]
michael009：
我把你的程序复制到vc中调试，编译通过无错误
但是总是在得出结果后，
提示非法操作，然后只好强制关闭
而我自己的程序却没有
我观察了一下你的程序,发现你的程序在22行和26行的
if语句中 Data[Digit]>10 而不是 Data[Digit]>=10
所以你的程序从27!就开始出错
真正的
27! = 10888869450418352160768000000,
而你的程序运行后是
27! = 0888869450418352160768000000,
由此导致你以后的所有计算都出错.
你是参考那本C语言数据结构上的原程序吧,
我认为那本书虽然不错,但还是有一些错误的,最好自己写后再调试一下.
但搞不通的就是
我把你的程序的if语句改过来后,运行得出结果后,
虽然答案正确,但仍提示非法操作,
奇怪?!?
|
| petrelk 回复于：2002-11-07 16:10:55
|
for(r=1;r<Digit+1;r++)改为for(r=j;r<Digit+1;r++)如何？
|
| michael009 回复于：2002-11-07 16:24:19
|
我用的bcb，编译、运行都没问题
|
| HopeCao 回复于：2002-11-07 16:33:54
|
用vector呢？？？
|
| michael009 回复于：2002-11-07 16:35:10
|
to syo:
的确是那个问题，谢谢！但是为什么我用bcb执行时没有出错信息？（尽管结果不对）
还有，那本书上错误很多，尽管都是小错，但是却很要命：）
|
| HopeCao 回复于：2002-11-07 16:51:04
|
修改了一下前面的程序：
#include <stdio.h>
#include <vector>
int main(void)
{
int i,j,k,r;
vector<int> data;
int n;
int digit;
data.push_back(1);
data.push_back(1);
digit = 1;
printf("Enter a number what you want tocalculus:";
scanf("%d", &n);
for (i = 1; i < n + 1; i++)
{
for (j = 1; j < digit + 1; j++)
data[j] *= i;
for (j = 1; j < digit + 1; j++)
{
if (data[j] >= 10)
{
for (r = 1; r < digit + 1; r++)
{
if (data[digit] >= 10)
digit++;
if ((r + 1) >= data.size())
data.push_back(data[r] / 10);
else
data[r + 1] += data[r] / 10;
data[r] = data[r] % 10;
}
}
}
}
printf("%d! = ",n);
for (k = data.size(); k > 0; k--)
printf("%d",data[k]);
printf("\n";
return 1;
}
这样子的话你想要多大都行，只要你的机器撑得住！
在linux下试过了：
Enter a number what you want tocalculus:1000
1000! = 004023872600770937735437024339230039857193748642107146325437999104299385
12398629020592044208486969404800479988610197196058631666872994808558901323829669
94459099742450408707375991882362772718873251977950595099527612087497546249704360
14182780946464962910563938874378864873371191810458257836478499770124766328898359
55735432513185323958463075557409114262417474349347553428646576611667797396668820
29120737914385371958824980812686783837455973174613608537953452422158659320192809
08782973084313928444032812315586110369768013573042161687476096758713483120254785
89320767169132448426236131412508780208000261683151027341827977704784635868170164
36502415369139828126481021309276124489635992870511496497541990934222156683257208
08213331861168115536158365469840467089756029009505376164758477284218896796462449
45160765353408198901385442487984959953319101723355556602139450399736280750137837
61530712776192684903435262520001588853514733161170210396817592151090778801939317
81141945452572238655414610628921879602238389714760885062768629671466746975629112
34082439208160153780889893964518263243671616762179168909779911903754031274622289
98800519544441428201218736174599264295658174662830295557029902432415318161721046
58320367869061172601587835207515162842255402651704833042261439742869330616908979
68482590125458327168226458066526769958652682272807075781391858178889652208164348
34482599326604336766017699961283186078838615027946595513115655203609398818061213
85586003014356945272242063446317974605946825731037900840244324384656572450144028
21885252470935190620929023136493273497565513958720559654228749774011413346962715
42284586237738753823048386568897646192738381490014076731044664025989949022222176
59043399018860185665264850617997023561938970178600408118897299183110211712298459
01641921068884387121855646124960798722908519296819372388642614839657382291123125
02418664935314397013742853192664987533721894069428143411852015801412334482801505
13996942901534830776445690990731524332782882698646027898643211390835062170950025
97389863554277196742822248757586765752344220207573630569498825087968928162753848
86339690995982628095612145099487170124451646126037902930912088908694202851064018
21543994571568059418727489980942547421735824010636774045957417851608292301353580
81840096996372524230560855903700624271243416909004153690105933983835777939410970
02775347200000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000
|
| petrelk 回复于：2002-11-08 09:56:10
|
楼上的兄弟，你的结果明显不对嘛。
还有我说for(r=1;r<digit+1;r++) --> for(r=j;r<digit+1;r++) 跟程序的正确性无关，这是效率方面的问题（效率需求不很高，也就无所谓了，都没问题的）。
#include <stdio.h>
void main(){
int i,j,k,r;
int data[200000];
int n;
int digit;
for (i=1;i<200000+1;i++)data[i]=0;
data[0]=1;
data[1]=1;
digit=1;
printf("Enter a number what you want tocalculus:";
scanf("%d",&n);
for(i=1;i<n+1;i++){
for(j=1;j<digit+1;j++)data[j]*=i;
for(j=1;j<digit+1;j++){
if (data[j]>=10){
for(r=j;r<digit+1;r++){
if (data[digit]>=10)
digit++;
data[r+1]+=data[r]/10;
data[r]=data[r]%10;
}
}
}
}
printf("%d! = ",n);
for (k=digit;k>0;k--)printf("%d",data[k]);
printf("\n";
}
|
| HopeCao 回复于：2002-11-08 11:28:25
|
你说结果前面多了两个0是吧？ 我再看看！！！
|
| 西北风 回复于：2002-12-02 20:55:13
|
采用本贴诸位兄弟提供的算法，（我做了一点小小的优化）：
计算（10000!）耗时间3.622948秒；
计算（100000!）耗时间533.321603秒；
机器性能：采用如下单循环测试：
for( i = 0; i < 1000000000LL; i ++ {
NULL;
}
耗费时间15.628547秒。这个算法还是很高效的。
|
| gshcode 回复于：2003-03-24 01:26:16
|
To:syo.
我也是新手，我在我的机器上用VC运行了一下，也是有错误报告的，但结果好像是正确的，我始终没有看懂你的那段代码如果可以的话，帮我加个注释，我的邮箱gshdong@etang.com
另外，我试着改了一下你的程序，如下：
#include <stdio.h>
void main(void)
{
int Data[10000];
int i,j,k,Digit;
for(i=1;i<10000+1;i++)
Data[i]=0;
Data[0]=1;
Data[1]=1;
Digit=1;
j=1;
printf("Enter a number what you want to calculus:");
scanf("%d",&i);
Data[j]*=i;
printf("%d!=",i);
for(k=Digit;k>0;k--)
printf("%d",Data[k]);
printf("\n");
}
我发现结果也是出现错误报告，但结果一样！
我将700运行后发现，改后是40秒钟，原来是45秒钟。是不是这样的算法正确，更有效呢？
To：西北风
我不知道你的时间那么精确是怎样得到的，想知道，谢谢。。。。
|
| gshcode 回复于：2003-03-24 01:27:58
|
补充一下，这是我得到的结果：
1000!=2659145937280696950074260464409418865331402264639025936134946798633634608506605341848117565232388967220691521047646742106119945633540336330666600432078786176582966449460027973609668901653686743285383633365019008885800724681058439656928488234674600228182369645568491041056756580282897572385061357278232779114920004862830266253560118867403382725038217198944792853513297566489925034122733378247374893115844266512923590957895774954254684111154225441297453518636458346880304846554071307406210897567750299938329844830490645919588789172145775148824774815917136735740105391969156910568647797541225196431545003714622672452935520154778257840461215903510523490121099122992710237093624896586489414282184090257084036565907108276497163709114611666176371931495655244797158995705279462867837621538546736906193006117563959298078750455022641295446206557214134210045563196992157659632978729060
57887874366481492114239499494420645461417455786975332429889773266399462613084246185660877247088256248539150323711696576294168044289595511449194870371270526115044951820380624338541606624929353671599440413097787213590864384717122770909891683643680301659290230285195643474450353297145010559807667954579121926296394756474451469098244156117738300646048923358984033634852832076004802798791410318090305900996740524708176985163078147237675560523133749365108382431746659724222978687365798656110097554000908096212339382465006987799497057634005428606343141476132927154380658495834830521382383688967513430487795230239031873429076752801190736250460271509909782907878196535298175643180848799560230618524992640978059091447000509455184385479308971688016532057509623059040314461506758805438770202971754447840907060036434710363017957650066521183803191608505443274074162222868882585167935671682785390548898517200277096962840230200388651521118932881689204122728463810564190124718599666532053336884382660016350447195471572559841601252573309450748165829815669399211575612269892043452873781312997200527618503185576072780709408819926326671778813266925086902168977019120102505655301410282649800055414213554471827663350333998952004716041840730265515180149457398561891097192842235811555940646681974384129328099886594856943626538556391133529146832764689233967561098573890208392046609072818623606875777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
|
| lzjwhu 回复于：2003-03-24 14:58:57
|
//效率不是很高，不过对大数没问题，主要限制是计算速度。
#include<iostream.h>
#include<math.h>
#include<time.h>
unsigned long int getN();
double getsize(unsigned long int n);
char * initarray(unsigned long int size);
double calculate(char * add,unsigned long int n);
void multiply(char * add, unsigned long int n);
void displayresult(char * add, unsigned long int size);
//---------输入数字-----------------------
unsigned long int getN()
{unsigned long int n;
cout<<"Please input a number: ";
cin>>n;
while(n<0)
{
cout<<"Input must be larger than 0.\nPlease input again: ";
cin>>n;
}
return n;
}
//---------------计算结果共有多少位-------------
double getsize(unsigned long int n)
{unsigned long int i;double size=1;
for (i=1;i<=n;i++)size=size +log10(i);
cout<<"the result has "<<(unsigned long int)size<<"(10) digits\n";
size++;
return size;
}
//---------------初始化存放结果的数组，‘a’标记结果的最后一位--------------
char * initarray(unsigned long int size)
{
unsigned long int i;
char * address=new char[size];
if(!address)
{
cout<<"number is too large";
}
address[0]=1;
address[1]=97;//97 is 'a'
for (i=2;i<size;i++)
address[i]=0;
return address;
}
//---------------算阶乘-----------------
double calculate(char * add,unsigned long int n)
{
double t1=clock();
unsigned long int width;
cout<<"\n Now calculating... ";
for(unsigned long int i=1;i<=n;i++)
{
cout<<i;
width=log10(i);
for(unsigned long int j=0;j<=width;j++)cout<<"\b";
multiply(add,i);
}
double t2=clock();
return (t2-t1)/CLK_TCK;
}
//-------------模拟进位乘法-------------------
void multiply(char * add, unsigned long int n)
{unsigned long int intermediate, intermediatequot=0;
unsigned long int pointer=0;
while(add[pointer]==0){pointer++;};
while(add[pointer]!='a')
{
intermediate=add[pointer]*n;
intermediate+=intermediatequot;
intermediatequot=intermediate/10;
add[pointer]=intermediate-intermediatequot*10;
pointer++;
}
while(intermediatequot>=1)
{
add[pointer]=intermediatequot-intermediatequot/10*10;
intermediatequot=intermediatequot/10;
pointer++;
}
add[pointer]='a';
}
//------------------显示结果--------------
void displayresult(char * add, unsigned long int size)
{
unsigned long int i=size;
while(add[i]!='a'){i--;}
int v=51;
while(i>0)
{i--;v--;
if(v==50)
{
cout<<"\n";
cout.width(10);
cout<<i+1;
cout<<": ";
}
if(v%10==0){cout<<' '; }
cout<<(int)(add[i]);
if(v==1)v=51;
}
}
//--------------------------------
main()
{unsigned long int n;char quit;
while(quit!='y'&&quit!='Y')
{n=getN();
unsigned long int size=getsize(n);
char * address=initarray(size);
double time_used=calculate(address,n);
displayresult(address,size);
cout<<"\nCalculation used "<<time_used<<" seconds.";
delete []address;
cout<<"\nquit?(Y/N)";cin>>quit;cout<<"\n";
}
return 1;
}
|
| lzjwhu 回复于：2003-03-24 14:58:57
|
//效率不是很高，不过对大数没问题，主要限制是计算速度。
#include<iostream.h>
#include<math.h>
#include<time.h>
unsigned long int getN();
double getsize(unsigned long int n);
char * initarray(unsigned long int size);
double calculate(char * add,unsigned long int n);
void multiply(char * add, unsigned long int n);
void displayresult(char * add, unsigned long int size);
//---------输入数字-----------------------
unsigned long int getN()
{unsigned long int n;
cout<<"Please input a number: ";
cin>>n;
while(n<0)
{
cout<<"Input must be larger than 0.\nPlease input again: ";
cin>>n;
}
return n;
}
//---------------计算结果共有多少位-------------
double getsize(unsigned long int n)
{unsigned long int i;double size=1;
for (i=1;i<=n;i++)size=size +log10(i);
cout<<"the result has "<<(unsigned long int)size<<"(10) digits\n";
size++;
return size;
}
//---------------初始化存放结果的数组，‘a’标记结果的最后一位--------------
char * initarray(unsigned long int size)
{
unsigned long int i;
char * address=new char[size];
if(!address)
{
cout<<"number is too large";
}
address[0]=1;
address[1]=97;//97 is 'a'
for (i=2;i<size;i++)
address[i]=0;
return address;
}
//---------------算阶乘-----------------
double calculate(char * add,unsigned long int n)
{
double t1=clock();
unsigned long int width;
cout<<"\n Now calculating... ";
for(unsigned long int i=1;i<=n;i++)
{
cout<<i;
width=log10(i);
for(unsigned long int j=0;j<=width;j++)cout<<"\b";
multiply(add,i);
}
double t2=clock();
return (t2-t1)/CLK_TCK;
}
//-------------模拟进位乘法-------------------
void multiply(char * add, unsigned long int n)
{unsigned long int intermediate, intermediatequot=0;
unsigned long int pointer=0;
while(add[pointer]==0){pointer++;};
while(add[pointer]!='a')
{
intermediate=add[pointer]*n;
intermediate+=intermediatequot;
intermediatequot=intermediate/10;
add[pointer]=intermediate-intermediatequot*10;
pointer++;
}
while(intermediatequot>=1)
{
add[pointer]=intermediatequot-intermediatequot/10*10;
intermediatequot=intermediatequot/10;
pointer++;
}
add[pointer]='a';
}
//------------------显示结果--------------
void displayresult(char * add, unsigned long int size)
{
unsigned long int i=size;
while(add[i]!='a'){i--;}
int v=51;
while(i>0)
{i--;v--;
if(v==50)
{
cout<<"\n";
cout.width(10);
cout<<i+1;
cout<<": ";
}
if(v%10==0){cout<<' '; }
cout<<(int)(add[i]);
if(v==1)v=51;
}
}
//--------------------------------
main()
{unsigned long int n;char quit;
while(quit!='y'&&quit!='Y')
{n=getN();
unsigned long int size=getsize(n);
char * address=initarray(size);
double time_used=calculate(address,n);
displayresult(address,size);
cout<<"\nCalculation used "<<time_used<<" seconds.";
delete []address;
cout<<"\nquit?(Y/N)";cin>>quit;cout<<"\n";
}
return 1;
}
|
