骰子問題
作法:數學(排列組合)或(遞迴)
想法:
舉出所有可能的"組合",再利用不盡相異物的排列去算,所以效率不佳 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;
}
上一篇:漂亮數碼
建表有可能 0ms ,將所有答案跑出來觀察規律...