uva10288 Coupons 【概率分数】-白红宇

题目：

题意：

一共n种不同的礼券，每次得到每种礼券的概率相同。求期望多少次可以得到所有n种礼券。结果以带分数形式输出。1<= n <=33.

思路：

假设当前已经得到k种，获得新的一种的概率是(n-k)/n，则对应期望是n/(n-k)。求和得到步数期望是n/n+n/(n-1)+...+n/1=n*sum(1/i) (1<= i <= n)。需要注意及时约分，用分数类模板。

程序：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4   5 long long gcd (long long a, long long b) {  6     return b == 0 ? a : gcd(b, a % b);  7 }  8   9 class fraction { 10 public: 11     fraction() { 12         numerator = 0; 13         denominator = 1; 14     } 15     fraction(long long num) { 16         numerator = num; 17         denominator = 1; 18     } 19     fraction (long long a, long long b) { 20         assert(b != 0); 21         if (b < 0) { 22             numerator = -a; 23             denominator = -b; 24         } else { 25             numerator = a; 26             denominator = b; 27         } 28         this->reduction(); 29     } 30  31     void operator = (long long num) { 32         numerator = num; 33         denominator = 1; 34     } 35  36     void operator = (const fraction &b) { 37         numerator = b.numerator; 38         denominator = b.denominator; 39         this->reduction(); 40     } 41  42     fraction operator + (const fraction &b) const { 43         long long gcdnum = gcd(denominator, b.denominator); 44         return fraction(numerator*(b.denominator/gcdnum) + b.numerator*(denominator/gcdnum), denominator/gcdnum*b.denominator); 45     } 46  47     fraction operator + (const int b) const { 48         return ((*this) + fraction(b)); 49     } 50  51     fraction operator - (const fraction &b) const { 52         return ((*this) + fraction(-b.numerator, b.denominator)); 53     } 54  55     fraction operator - (const int &b) const { 56         return ((*this) - fraction(b)); 57     } 58  59     fraction operator * (const fraction &b) const { 60         return fraction(numerator*b.numerator, denominator * b.denominator); 61     } 62  63     fraction operator * (const int &b) const { 64         return ((*this) * fraction(b)); 65     } 66  67     fraction operator / (const fraction &b) const { 68         return ((*this) * fraction(b.denominator, b.numerator)); 69     } 70  71     void reduction() { 72         if (numerator == 0) { 73             denominator = 1; 74             return; 75         } 76         long long gcdnum = gcd(abs(numerator), denominator); 77         numerator /= gcdnum; 78         denominator /= gcdnum; 79     } 80  81 public: 82     long long numerator;//分子 83     long long denominator;//分母 84 }; 85  86 int countLen (long long n) { 87     int m = 0; 88     while (n) { 89         n /= 10; 90         m++; 91     } 92     return m; 93 } 94  95 void printF (const fraction &f){ 96     long long a, b, c; 97     int m, n; 98     b = f.numerator; 99     c = f.denominator;100     if (c == (long long)1) {101         printf("%lld\n", b);102     } else {103         a = b / c;104         m = countLen(a);105         b -= a * c;106         n = countLen(c);107         for (int i = 0; i <= m; i++) {108             printf(" ");109         }110         printf("%lld\n%lld ", b, a);111         for (int i = 0; i < n; i++) {112             printf("-");113         }114         puts("");115         for (int i = 0; i <= m; i++) {116             printf(" ");117         }118         printf("%lld\n", c);119     }120 }121 122 int main() {123     int n, maxn = 33;124     fraction f[maxn + 1];125 126     for (int i = 1; i <= maxn; i++) {127         f[i] = f[i - 1] + fraction(1, i);128     }129 130     while (~scanf("%d", &n)) {131         printF(f[n] * n);132     }133 134     return 0;135 }

本文转自 jiu~ 博客园博客，原文链接：http://www.cnblogs.com/jiu0821/p/8303132.html，如需转载请自行联系原作者