本文主要是介绍UVA 10288 - Coupons(概率递推)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
UVA 10288 - Coupons
题目链接
题意：n个张票，每张票取到概率等价，问连续取一定次数后，拥有所有的票的期望
思路：递推，f[i]表示还差i张票的时候期望，那么递推式为
f(i)=f(i)∗(n−i)/n+f(i−1)∗i/n+1 化简后递推即可，输出要输出分数比较麻烦
代码：
#include <cstdio>
#include <cstring>
#include <cmath>long long gcd(long long a, long long b) {if (!b) return a;return gcd(b, a % b);
}long long lcm(long long a, long long b) {a = a / gcd(a, b) * b;if (a < 0) a = -a;return a;
}struct Fraction {long long a, b;Fraction() {a = 0; b = 1;}Fraction(long long x) {a = x; b = 1;}Fraction(long long x, long long y) {a = x; b = y;}void deal() {if (b < 0) {b = -b; a = -a;}long long k = gcd(a, b);if (k < 0) k = -k;a /= k; b /= k;}Fraction operator+(Fraction p) {Fraction ans;ans.b = lcm(b, p.b);ans.a = ans.b / b * a + ans.b / p.b * p.a;ans.deal();return ans;}Fraction operator-(Fraction p) {Fraction ans;ans.b = lcm(b, p.b);ans.a = ans.b / b * a - ans.b / p.b * p.a;ans.deal();return ans;}Fraction operator*(Fraction p) {Fraction ans;ans.a = a * p.a;ans.b = b * p.b;ans.deal();return ans;}Fraction operator/(Fraction p) {Fraction ans;ans.a = a * p.b;ans.b = b * p.a;ans.deal();return ans;}void operator=(int x) {a = x;b = 1;}void print() {if (a == 0) {printf("0\n"); return;}if (a % b == 0) {printf("%lld\n", a / b); return;}int sn = 0;if (a / b > 0) {long long num = a / b;while (num) {num /= 10;sn++;}}if (sn) for (int i = 0; i <= sn; i++) printf(" ");printf("%lld\n", a % b);long long num = b;int cnt = 0;while (num) {num /= 10;cnt++;}printf("%lld ", a / b);for (int i = 0; i < cnt; i++) printf("-");printf("\n");for (int i = 0; i <= sn; i++) printf(" ");printf("%lld\n", b);}
};Fraction dp[35][35];
int n;int main() {for (long long i = 1; i <= 33; i++) {dp[i][0] = 0;for (long long j = 1; j <= i; j++)dp[i][j] = (dp[i][j - 1] * Fraction(j, i) + Fraction(1)) * Fraction(i, j);}while (~scanf("%d", &n)) {dp[n][n].print();}return 0;
}这篇关于UVA 10288 - Coupons(概率递推)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
