Y7M2 P2A 練習-1

大數相加    ✔

大數相乘    ✔

n階乘           ✔


大數相加================ 最多 1000位的兩個非負整數相加

#include <iostream>  // cin , cout

#include <cstring>   // memset

#include <algorithm>  // min, max

using namespace std;

const int MaxN = 1000+5;  // 10^999 有1000位，相加可能1001位

void print(int x[], int xn)   // 將 整數陣列x[] 倒著印出

{

        for(int i=xn-1; i>=0; --i)    cout << x[i];

        cout << endl;            // 加換行，若不加需在 呼叫後處理

}

void s2n(string s, int x[], int& xn)   // 將大整數(以字串傳入) 倒轉成整數陣列 x[]，設定長度xn

{

        xn = s.size();

        for(int i=xn-1, j=0;  i>=0; --i, ++j)     x[j] = s[i]-'0';

}

void badd(int x[], int xn , int y[], int yn , int z[], int& zn)

{

        zn = max(xn,yn);

        for(int i=0 ; i<zn; ++i) z[i] = x[i]+y[i];

        for(int i=0; i<zn; ++i)

          if( z[i]>=10 )

          {

                z[i+1] ++;   // 大數相乘的進位  應是 z[i+1] += z[i]/10

                z[i] -=10;   // 應是 z[i]%=10 ，但兩個<10的數字相加<20

          }

          if(z[zn]!=0) zn++;   // 大數相減或可能前導不只一個0時應 while(  ) zn--

}

int main(void)

{

        string sa,sb;

        int a[MaxN],b[MaxN],c[MaxN+1];

        int an,bn,cn;

        while( cin >> sa >> sb )

        {

                memset(a,0,sizeof(a));

                s2n(sa, a, an);  // print(a,an);

                memset(b,0,sizeof(b));

           s2n(sb, b, bn);  // print(b,bn);

           memset(c,0,sizeof(c));

           badd(a,an, b,bn, c,cn);

           print(c,cn);

        }

        return 0;

}

/*

範例輸入：

123456789012345678901234567890 111111111111111111111111111111

999999999999999999999999999999 1

12345 876

123 456789

範例輸出 ：

234567900123456790012345679001

1000000000000000000000000000000

13221

456912

*/


大數相乘 ================

#include <iostream>

#include <cstring>

using namespace std;

const int MaxN = 500+2;      // 最多500位數相乘

void s2n (string xs, int x[], int& xn )        // 將大整數字串 xs 轉為 整數陣列 x[] , 長度 xn

{

        xn = xs.size();

        for(int i=xn-1,j=0;  i>=0;  --i,++j)          x[j] = xs[i]-'0';

}

void print (int x[], int xn )           // 將 整數陣列x[] 倒著印出

{

        for(int i=xn-1;  i>=0;  --i)     cout << x[i];

        cout << endl;               // 加換行，若不加需在 呼叫後處理

}

void bmul(int x[], int xn, int y[], int yn, int z[], int& zn)

{

        for(int i=0; i<xn; ++i)

          for(int j=0; j<yn; ++j)

            z[i+j] += x[i]*y[j];

//  進位

   zn = xn+yn;

   for(int k=0; k<zn; ++k)

   {

     if( z[k]>=10 )

     {

             z[k+1] += z[k]/10;

             z[k] %= 10;

     }

   }

   if(z[zn-1]==0) zn--;

}

int main(void)

{

        string sa,sb;

        int a[MaxN],b[MaxN], c[MaxN+MaxN];  // c為相乘後結果，位數加倍

        int an,bn,cn;

        cin >> sa >> sb;

        s2n(sa,a,an);   // print(a,an);

        s2n(sb,b,bn);   // print(b,bn);

        for(int i=an+bn; i>=0; --i) c[i]=0;

        bmul(a,an,b,bn, c,cn);

        print(c,cn);

        return 0;

}

/* 輸入

200000000000000000000 300000000000000000000 

123456789012345678901234567890 123456789012345678901234567890

123 5

99 99

輸出 =========

60000000000000000000000000000000000000000 

15241578753238836750495351562536198787501905199875019052100

615

9801

*/

求 n 階乘 ===================
 輸入一個 0<1<1000 的正整數， 列出一行 n!
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int MaxN = 2570; // 1000! = 4.02387260077093773543702433923e+2567

void print (int x[], int xn )
{
for(int i=xn-1;  i>=0;  --i)
  cout << x[i];
cout << endl;
}

void bmi(int x[], int& xn, int y)
{
for(int i=0; i<xn; ++i)
  x[i]*=y;     /// <<< 與 bmul 不同，不累加，故可以不用清為0
//  進位
//     double ceil (double x);
//      float ceil (float x);
//   long double ceil (long double x);
//  Round up value  :   Rounds x upward, returning the smallest integral value that is not less than x.
//   zn = xn;
      xn+=4;   //xn+=ceil(log(y));   //
//   for(int i=zn; i<xn; ++i) x[i]=0;   ///有可能進位的位數才需清為 0
   for(int k=0; k<xn; ++k)
   {
    if( x[k]>=10 )
    {
    x[k+1] += x[k]/10;
    x[k] %= 10;
    }
   }
   while( x[xn-1]==0 ) xn--;  //去前導 0 {確定位數}
}

int main(void)
{
string sa,sb;
int a[MaxN];  // n! 的陣列
int an;       // 位數
   int n,s;
cin >> n;
memset(a,0,sizeof(a));  // 清為 0
a[0]=1; an=1;  // 1! 放在 a[0], 長度為1
for( int y=2; y<=n; ++y )  // 從 2開始乘至 n
{
bmi(a,an, y );
}
print(a,an);

return 0;
}
/*
10
20
50
100
1000
------
3628800
2432902008176640000
30414093201713378043612608166064768844377641568960512000000000000
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
*/