摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:數學(排列組合)或(遞迴)

想法:
舉出所有可能的"組合",再利用不盡相異物的排列去算,所以效率不佳 6x ms

遞迴公式: N是骰子個數 M是點數
ans[0][0]=1;
ans[N][M]=ans[N-1][M-1]+ans[N-1][M-2]+ans[N-1][M-3]+ans[N-1][M-4]+ans[N-1][M-5]+ans[N-1][M-6];

也就是說,如果我要N顆骰出M點的話,必定是N-1顆骰出 M-1 點 + 1點的可能就可以到達，最多只有M-6點可能+上6點，可能性是累加的

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

#include<stdio.h>
#include<stdlib.h>
main()
{
 int a,b,c;
 long long int math[21]={0};
 math[0]=1;
 for(a=1;a<21;a++) 
  math[a]=math[a-1]*a;
 int N,M;
 int n;
 scanf("%d",&n);
    while(n--)
    {
    scanf("%d %d",&N,&M);
    long long int ans=0;
     int x1,x2,x3,x4,x5,x6;
     for(x6=N;x6>=0;x6--)
      {
       if(x6*6>M) continue;
        for(x5=N-x6;x5>=0;x5--)
          {
            if(x6*6+x5*5>M) continue; 
            for(x4=N-x6-x5;x4>=0;x4--)
             {
               if(x6*6+x5*5+x4*4>M) continue;  
                for(x3=N-x6-x5-x4;x3>=0;x3--)
                  {
                   if(x6*6+x5*5+x4*4+x3*3>M) continue;  
                    for(x2=N-x6-x5-x4-x3;x2>=0;x2--)
                     {
                       x1=N-x6-x5-x4-x3-x2;
                       if(x1*1+x2*2+x3*3+x4*4+x5*5+x6*6==M)
                        ans=ans+math[N]/math[x1]/math[x2]/math[x3]/math[x4]/math[x5]/math[x6];
                     }
                  }
             }
          }
      }
        printf("%lld\n",ans);
      }
 return 0;
}

/*************加速版建表 30MS 仍然不夠快***************/

#include<stdio.h>
#include<stdlib.h>
long long int ans[21][121]={0};
long long int math[21]={0};
void make(int N)
{
   int x1,x2,x3,x4,x5,x6;
     for(x6=N;x6>=0;x6--)
        for(x5=N-x6;x5>=0;x5--)
            for(x4=N-x6-x5;x4>=0;x4--)
                for(x3=N-x6-x5-x4;x3>=0;x3--)
                    for(x2=N-x6-x5-x4-x3;x2>=0;x2--)
                     {
                       x1=N-x6-x5-x4-x3-x2;
                        ans[N][x1*1+x2*2+x3*3+x4*4+x5*5+x6*6]=ans[N][x1*1+x2*2+x3*3+x4*4+x5*5+x6*6]+math[N]/math[x1]/math[x2]/math[x3]/math[x4]/math[x5]/math[x6];
                     }
}
main()
{
 int a,b,c;
 math[0]=1;
 for(a=1;a<21;a++) 
  math[a]=math[a-1]*a;
 int N,M;
 int n;
 scanf("%d",&n);
    while(n--)
    {
    scanf("%d %d",&N,&M);
     if(ans[N][M]==0) make(N);
        printf("%lld\n",ans[N][M]);
    }
 return 0;
}

 /************遞迴版****************************/

#include<stdio.h>
#include<stdlib.h>
main()
{
 long long int ans[21][121]={0};
 int N,M,n;
 ans[0][0]=1;
 for(N=1;N<=20;N++)
  for(M=N;M<=N*6;M++)
   for(n=M-1;n>M-7&&n>=0;n--)
    ans[N][M]+=ans[N-1][n];
  int t;
  scanf("%d",&t);
  while(t--)
   {
     scanf("%d %d",&N,&M);
     printf("%lld\n",ans[N][M]);
   }
  return 0;
}