大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。
| Time Limit: 2000MS | Memory Limit: 65536K | |||
| Total Submissions: 8245 | Accepted: 2186 | Special Judge | ||
Description
“Green, orange, brown, red…”, colorful sugar-coated shell maybe is the most attractive feature of ACM chocolate. How many colors have you ever seen? Nowadays, it’s said that the ACM chooses from a palette of twenty-four colors to paint their delicious candy bits.
One day, Sandy played a game on a big package of ACM chocolates which contains five colors (green, orange, brown, red and yellow). Each time he took one chocolate from the package and placed it on the table. If there were two chocolates of the same color on the table, he ate both of them. He found a quite interesting thing that in most of the time there were always 2 or 3 chocolates on the table.
Now, here comes the problem, if there are C colors of ACM chocolates in the package (colors are distributed evenly), after N chocolates are taken from the package, what’s the probability that there is exactly M chocolates on the table? Would you please write a program to figure it out?
Input
For each case, there are three non-negative integers: C (C <= 100), N and M (N, M <= 1000000).
The input is terminated by a line containing a single zero.
Output
Sample Input
5 100 2 0
Sample Output
0.625
Source
题意：C种颜色的巧克力在桶中，从里面依次拿出n个巧克力，颜色同样的吃掉，求最后剩下m个巧克力的概率
当n>1000 时候，考虑奇偶性取1000或1001就可以，由于非常大的时候概率会趋于稳定，至于奇数时取1001 偶数
时取1000有些不解
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#define N 1010
using namespace std;
double dp[N][110];
int main()
{
int c,n,m;
while(scanf("%d",&c)!=EOF)
{
if(c==0)
{
break;
}
scanf("%d %d",&n,&m);
if(m>c||m>n||(n-m)%2)
{
printf("0.000\n");
continue;
}
if(n>1000)
{
n = 1000+n%2;
}
memset(dp,0,sizeof(dp));
dp[0][0] = 1;
dp[1][1] = 1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=i&&j<=c;j++)
{
if(j-1>=0)
{
dp[i][j] = dp[i-1][j-1]*(double)(c-j+1)/(double)c;
}
dp[i][j] += dp[i-1][j+1]*(double)(j+1)/(double)c;
}
}
printf("%.3lf\n",dp[n][m]);
}
return 0;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/118765.html原文链接：https://javaforall.net
