作法:數學,大數
應用:C(N取M)的大數

想法:有N位數

C(N,0)*9^N+C(N,2)*9^(N-2)+C(N,4)*9^(N-4)...一直到超過N的偶數

目前沒有新想法將程式碼縮短  (第2程式碼)

/******************/

2009/7/15更新 建中數學專題教材第45頁11題

遞迴推導的結果如下:(8^N+10^N)/2 為了省去大數除法的部份改用4*8^(N-1)+5*10^(N-1)

推導過程:待善心人士幫補  (第1程式碼)

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
main()
{
 int n;
 while(scanf("%d",&n)==1&&n!=0)
   {
     if(n==1) {printf("9\n");continue;}
      int a,b,c;
      int ans[100]={0};
      int n8[100]={0},n10[100]={0};
      n8[0]=4;
      n10[0]=5;
      for(a=0;a<n-1;a++)
       {
         for(b=0;b<100;b++)
           {n8[b]*=8;n10[b]*=10;}
         for(b=0;b<100;b++)
           {
            n8[b+1]=n8[b+1]+n8[b]/10;n8[b]%=10;
            n10[b+1]=n10[b+1]+n10[b]/10;n10[b]%=10;
            ans[b]=n8[b]+n10[b];
           }
       }
      for(a=0;a<100;a++)
       {ans[a+1]=ans[a+1]+ans[a]/10;ans[a]%=10;}
      for(a=99;a>=0;a--)
       if(ans[a]!=0)
         {
           for(b=a;b>=0;b--)
             printf("%d",ans[b]);
             printf("\n");
             break;
         }
   }
 return 0;
}

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
int gcd(int a,int b)              
 {              
  int temp;              
  while(a%b)                    
   {                    
    temp=a;                    
    a=b;                    
    b=temp%b;                               
   }              
   return b;              
 } 
main()
{
 int map[101][100]={0};
 map[0][0]=1;
 int a,b,c,m,n;
 for(a=1;a<=100;a++)/*9^N 表*/
    for(b=0;b<100;b++)
     {
      map[a][b]=map[a][b]+map[a-1][b]*9;
      if(map[a][b]>=10)
       {
        map[a][b+1]=map[a][b+1]+map[a][b]/10;
        map[a][b]%=10;
       }
     }
 int math[101]={0},N,M;
 while(scanf("%d",&N)==1&&N!=0)
  {
   int lastans[100]={0},a1;
   n=N;
   for(a1=0;a1<=N;a1=a1+2)
   {
    m=a1;
       for(a=1;a<=n;a++)  math[a]=a;
        if(m>n/2) m=n-m;
        for(a=2;a<=m;a++)  
        {  
         c=a;
        for(b=n-m+1;b<=n;b++)
          {
           if(math[b]%c==0)
            {
             math[b]=math[b]/c;
             c=1;
            }
           if(gcd(math[b],c)!=1)
            {
             int gg=gcd(math[b],c);
             math[b]=math[b]/gg;
             c=c/gg;
            }
            if(c==1)
             break;
          }
        } 
     int ans[50]={0};
     ans[0]=1;
     for(b=n-m+1;b<=n;b++)
      {
       for(c=0;c<49;c++)
        ans[c]=ans[c]*math[b];
       for(c=0;c<49;c++)
        if(ans[c]>=10)
         {
         ans[c+1]=ans[c+1]+ans[c]/10;
         ans[c]=ans[c]%10;
         }
      }
      for(a=0;a<100;a++)
       for(b=0;b<50;b++)
        {
         lastans[a+b]=lastans[a+b]+map[N-a1][a]*ans[b];
          if(lastans[a+b]>=10)
           {
            lastans[a+b+1]=lastans[a+b+1]+lastans[a+b]/10;
            lastans[a+b]%=10;
           }
        }
    } 
    for(a=99;a>=0;a--)
     if(lastans[a]!=0)
      {
       for(b=a;b>=0;b--)
        printf("%d",lastans[b]);
       printf("\n");
       break;
      }
  }
 return 0;
}