예제 10 - 17 사탕 UVa 1639

1814 단어 uva수학 적 기대
1. 제목 설명: 클릭 하여 링크 열기
2. 문제 풀이 방향: 문제 의 뜻 에 따라 마지막 에 첫 번 째 상 자 를 열 어도 무방 하 다. 이때 두 번 째 상 자 는 i 개의 사탕 이 있 기 때문에 그 전에 모두 n + (n - i) 의 상 자 를 열 었 다. 그 중에서 n 번 은 상자 1, n - i 번 은 상자 2 를 찾 았 고 취 법 은 모두 C (2 * n - i, n) 종이 있 기 때문에 상자 2 에 i 개의 사탕 이 남 았 을 확률 은 C (2 * n - i, n) * p ^ (n + 1) * (1 - p) ^ (n - i) 이다.마지막 으로 상 자 를 열 확률 도 계산 해 야 합 니 다.확률 이 있 으 면 기대 하 는 정의 에 따라 답 을 구하 기 어렵 지 않다.그러나 주의해 야 할 것 은 n 이 매우 클 수 있 기 때문에 대수 로 계산 하여 과도 한 정밀도 손실 을 방지 해 야 한 다 는 것 이다.프로그램의 효율 을 높이 기 위해 서 는 n 을 미리 계산 할 수 있 습 니 다!자연 대수 의 값 을 취하 면 후속 계산 에 편리 하 다.또한 p 의 경 계 는 0 또는 1 일 수 있 으 므 로 단독으로 처리 해 야 합 니 다.
3. 코드:
#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;
#define N 200000
long double v1, v2;
long double Log[2*N+100];
void init()//   ,  n!      
{
	for (int i = 1; i <= N * 2; i++)
		Log[i] = Log[i - 1] + log(i);
}
int main()
{
	//freopen("test.txt", "r", stdin);
	int rnd = 0;
	int n;
	double p;
	init();
	while (cin >> n >> p)
	{
		double ans = 0.0;
		printf("Case %d: ", ++rnd);
		if (p == 0 || p == 1)ans = n;//    
		else
		{
			long double p1 = log(p);
			long double q1 = log(1 - p);
			for (int i = 1; i <= n; i++)
			{
				long double c = Log[2 * n - i] - Log[n] - Log[n - i];
				v1 = c + (n + 1)*p1 + (n - i)*q1;
				v2 = c + (n + 1)*q1 + (n - i)*p1;
				ans += (double)i*(exp(v1) + exp(v2));
			}
		}
		printf("%.6lf
", ans); } return 0; }

좋은 웹페이지 즐겨찾기