Coupons UVA - 10288 （紫书例题10-18）（数学期望）

Description

Coupons in cereal boxes are numbered 1 to n, and a set of one of each is required for a prize (a cereal box, of course). With one coupon per box, how many boxes on average are required to make a complete set of n coupons?

Input

Input consists of a sequence of lines each containing a single positive integer n, 1 ≤ n ≤ 33, giving the size of the set of coupons. Input is terminated by end of file.

Output

For each input line, output the average number of boxes required to collect the complete set of n coupons. If the answer is an integer number, output the number. If the answer is not integer, then output the integer part of the answer followed by a space and then by the proper fraction in the format shown below. The fractional part should be irreducible. There should be no trailing spaces in any line of output.

Sample Input

2 5 17

Sample Output

3 5 11 -- 12 340463 58 ------ 720720

题意：

每张彩票有一张图案，每次买一张彩票，图案有 n 种，只有集齐这 n 种图片才能兑奖，平均情况下需要买多少次彩票才能兑奖。

分析： 每张彩票出现的概率都是 1/n 假设此时手中有 k 种图片，那买 t 次可以得到一张新的图片的概率是： p(t) = (k/n)^(t-1) * (1-k/n) 令(k/n) = s 那在手中有 k 种图片的前提下，拿到的下一张图片是新的图片的期望次数是： 1*P(1) + 2*P(2) + 3*P(3) + … + n*P(n) + … = (1-s)*( 1 + 2*s + 3*s^2 + 4*s^3 + …) = 1 + 2*s + 3*s^2 + 4*s^3 + … - s - 2*s^2 - 3*s^3 -… = 1 + s + s^2 + s^3 + … [泰勒级数求和公式] = 1/(1-s) = n/(n-k)

所以：平均情况下需要买的次数是

ans = n * ( 1 + 1/2 + 1/3 + … + 1/(n-1) + 1/n );

代码

#include <iostream> #include <cstdio> #include <functional> #include <vector> #include <algorithm> #include <queue> #include <stack> #include <cstring> #include <map> #include <utility> #include <cstdlib> #include <cmath> #define mem(a,b) memset(a,0,sizeof(b)) #define Pair pair<int,int> #define binary_count(a) __builtin_popcount(a) //计算一个数字的二进制中有多少个位是1 #define LL long long #define maxn 1000001 #define MOD 1000000007 #define INF 0x3f3f3f3f using namespace std; bool operator<(const Pair &a, const Pair &b) { return a.first > b.first; } //计算 1->n 最小公倍数，lcm(a,b)*gcd(a,b) = a*b LL lcm(LL a,LL b){ return (a*b)/__gcd(a,b); //return a/__gcd(a,b)*b; // 推荐写成这种形式 } int main() { LL n; while(cin >> n) { //ans = n * ( 1 + 1/2 + 1/3 + ... + 1/(n-1) + 1/n ); //计算 1->n 最小公倍数，lcm(a,b)*gcd(a,b) = a*b LL lm = 1; for(LL i = 1;i <= n;i++) { lm = lcm(lm,i); } LL fenzi = 0; for(LL i = 1;i <= n;i++) { fenzi += (lm/i); } fenzi = fenzi * n; LL ansfz = fenzi / __gcd(fenzi,lm); LL ansfm = lm / __gcd(fenzi,lm); // 判断分母的位数 LL tmp = ansfm; int cont = 0; while(tmp / 10) { cont ++; tmp = tmp / 10; } // 计算整数部分的位数 tmp = ansfz/ansfm; int cont2 = 0; while(tmp / 10) { cont2 ++; tmp = tmp / 10; } // 输出格式好恶心啊~~~ if(ansfz % ansfm == 0) // 若是能整除，输出整数 cout << ansfz / ansfm << endl; else { // 不能整除，输出分数，分数形式为 xx又xx分之xx for(int i = 0;i <= cont2;i++) cout << " "; cout << " " << ansfz%ansfm << endl; cout << ansfz/ansfm << " "; for(int i = 0;i <= cont;i++) cout << "-"; cout << endl; for(int i = 0;i <= cont2;i++) cout << " "; cout << " " << ansfm << endl; } } return 0; }

注意

// 判断分母的位数 LL tmp = ansfm; int cont = 0; while(tmp / 10) { cont ++; tmp = tmp / 10; }

可以直接改成 …(´・ω・`)

int cont = log10(ansfm);