[help]超大數求(factorial)

HopeCao

用vector呢？？？

michael009

to syo:
  的确是那个问题，谢谢！但是为什么我用bcb执行时没有出错信息？（尽管结果不对）
  还有，那本书上错误很多，尽管都是小错，但是却很要命：）

HopeCao

修改了一下前面的程序：
#include <stdio.h>;
#include <vector>;

int main(void)
{
    int i,j,k,r&#59;
    vector<int>; data&#59;
    int n&#59;
    int digit&#59;

    data.push_back(1)&#59;
    data.push_back(1)&#59;
   
    digit = 1&#59;

    printf(&quot;Enter a number what you want tocalculus:&quot&#59;
    scanf(&quot;%d&quot;, &amp;n)&#59;

    for (i = 1&#59; i < n + 1&#59; i++)
    {
        for (j = 1&#59; j < digit + 1&#59; j++)
            data[j] *= i&#59;

        for (j = 1&#59; j < digit + 1&#59; j++)
        {
            if (data[j] >;= 10)
            {
                for (r = 1&#59; r < digit + 1&#59; r++)
                {
                    if (data[digit] >;= 10)
                        digit++&#59;
                    
                    if ((r + 1) >;= data.size())
                        data.push_back(data[r] / 10)&#59;
                    else
                        data[r + 1] += data[r] / 10&#59;

                    data[r] = data[r] % 10&#59;
                }
            }
        }
    }

    printf(&quot;%d! = &quot;,n)&#59;
   
    for (k = data.size()&#59; k >; 0&#59; k--)
        printf(&quot;%d&quot;,data[k])&#59;
    printf(&quot;\n&quot&#59;

    return 1&#59;
}
这样子的话你想要多大都行，只要你的机器撑得住！
在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

楼上的兄弟，你的结果明显不对嘛。
还有我说for(r=1&#59;r<digit+1&#59;r++) -->; for(r=j&#59;r<digit+1&#59;r++) 跟程序的正确性无关，这是效率方面的问题（效率需求不很高，也就无所谓了，都没问题的）。
#include <stdio.h>;

void main(){
int i,j,k,r&#59;
int data[200000]&#59;
int n&#59;
int digit&#59;
for (i=1&#59;i<200000+1&#59;i++)data=0&#59;

data[0]=1&#59;
data[1]=1&#59;
digit=1&#59;

printf(&quot;Enter a number what you want tocalculus:&quot&#59;
scanf(&quot;%d&quot;,&amp;n)&#59;

for(i=1&#59;i<n+1&#59;i++){
for(j=1&#59;j<digit+1&#59;j++)data[j]*=i&#59;
for(j=1&#59;j<digit+1&#59;j++){
if (data[j]>;=10){
for(r=j&#59;r<digit+1&#59;r++){
if (data[digit]>;=10)
                                                      digit++&#59;
data[r+1]+=data[r]/10&#59;
data[r]=data[r]%10&#59;
}
}
}
}

printf(&quot;%d! = &quot;,n)&#59;
for (k=digit&#59;k>;0&#59;k--)printf(&quot;%d&quot;,data[k])&#59;
printf(&quot;\n&quot&#59;
}

HopeCao

你说结果前面多了两个0是吧？ 我再看看！！！

西北风

采用本贴诸位兄弟提供的算法，（我做了一点小小的优化）：

计算（10000!）耗时间3.622948秒；
计算（100000!）耗时间533.321603秒；

机器性能：采用如下单循环测试：
    for( i = 0&#59; i < 1000000000LL&#59; i ++ ) {
        NULL&#59;
    }
耗费时间15.628547秒。这个算法还是很高效的。

gshcode

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=0;
       Data[0]=1;
       Data[1]=1;
       Digit=1;
           j=1;

       printf("Enter a number what you want to calculus:";
       scanf("%d",&amp;i);
         Data[j]*=i;


      printf("%d!=",i);
                           for(k=Digit;k>;0;k--)
                       printf("%d",Data[k]);
               printf("\n";
               
      
}
我发现结果也是出现错误报告，但结果一样！
我将700运行后发现，改后是40秒钟，原来是45秒钟。是不是这样的算法正确，更有效呢？
To：西北风
    我不知道你的时间那么精确是怎样得到的，想知道，谢谢。。。。

gshcode

补充一下，这是我得到的结果：

1000!=2659145937280696950074260464409418865331402264639025936134946798633634608506605341848117565232388967220691521047646742106119945633540336330666600432078786176582966449460027973609668901653686743285383633365019008885800724681058439656928488234674600228182369645568491041056756580282897572385061357278232779114920004862830266253560118867403382725038217198944792853513297566489925034122733378247374893115844266512923590957895774954254684111154225441297453518636458346880304846554071307406210897567750299938329844830490645919588789172145775148824774815917136735740105391969156910568647797541225196431545003714622672452935520154778257840461215903510523490121099122992710237093624896586489414282184090257084036565907108276497163709114611666176371931495655244797158995705279462867837621538546736906193006117563959298078750455022641295446206557214134210045563196992157659632978729060
57887874366481492114239499494420645461417455786975332429889773266399462613084246185660877247088256248539150323711696576294168044289595511449194870371270526115044951820380624338541606624929353671599440413097787213590864384717122770909891683643680301659290230285195643474450353297145010559807667954579121926296394756474451469098244156117738300646048923358984033634852832076004802798791410318090305900996740524708176985163078147237675560523133749365108382431746659724222978687365798656110097554000908096212339382465006987799497057634005428606343141476132927154380658495834830521382383688967513430487795230239031873429076752801190736250460271509909782907878196535298175643180848799560230618524992640978059091447000509455184385479308971688016532057509623059040314461506758805438770202971754447840907060036434710363017957650066521183803191608505443274074162222868882585167935671682785390548898517200277096962840230200388651521118932881689204122728463810564190124718599666532053336884382660016350447195471572559841601252573309450748165829815669399211575612269892043452873781312997200527618503185576072780709408819926326671778813266925086902168977019120102505655301410282649800055414213554471827663350333998952004716041840730265515180149457398561891097192842235811555940646681974384129328099886594856943626538556391133529146832764689233967561098573890208392046609072818623606875777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

lzjwhu

//效率不是很高，不过对大数没问题，主要限制是计算速度。

#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<<"lease 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=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!='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);
if(v==1)v=51;
}
}
//--------------------------------
main()
{unsigned long int n;char quit;
while(quit!='y'&amp;&amp;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

//效率不是很高，不过对大数没问题，主要限制是计算速度。

#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<<"lease 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=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!='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);
if(v==1)v=51;
}
}
//--------------------------------
main()
{unsigned long int n;char quit;
while(quit!='y'&amp;&amp;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;
}