本文主要是介绍UVA10288 Coupons，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：n个物品(兑换券)，每次从中选择一个(不取出)，求期望多少次可以取遍所有的物品n<=33。
题解：先说一下概率吧：显然为1 * (n-1)/n * (n-2)/n * ... * 1/n 。这道题要求的期望一定不能直接取概率的倒数，因为直接取倒数的意义是一次取n个，期望多少次可以取遍，与题目不符。应该对于每一步取倒数然后相加作为答案。ans = 1 * n/(n-1) * n/(n-2) ... * n。实现的时候用long long，并且注意要不停地约分，不然会爆long long。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
LL n;
LL fz, fm; //当前分子和分母
LL adz, adm; //增加的分子和分母
LL gcd(LL a, LL b) {if (!b) return a;return gcd(b, a%b);
}
void add() {LL g = gcd(fm, adm);LL t1 = fz*adm/g+adz*fm/g, t2 = fm/g*adm;fz = t1; fm = t2;g = gcd(fz, fm);fz/=g; fm/=g;
}
int lg(LL n)
{int cnt = 0;while (n) ++cnt, n/=10;return cnt;
}
void put(int cnt, char c) {while (cnt>0) putchar(c), --cnt;
}
void print() {if (fz % fm == 0) {cout << fz << '\n';return;}LL a = fz/fm , b = fz%fm, c = fm;put(lg(a) + 1, ' ');cout << b << '\n';cout << a << ' ';put(lg(c), '-');put(1, '\n');put(lg(a) + 1, ' ');cout << c << '\n';
}
int main()
{while (cin >> n) {LL i;fz = 0; fm = 1;adz = 0; adm = 1;for (i = 0; i<n; ++i) {adz = n; adm = n - i;add();}print();}return 0;
}
这篇关于UVA10288 Coupons的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
