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 <cstdio>
  2 #include <cassert>
  3 #include <cstdlib>
  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
", 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
%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
", 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 }

uva10288 Coupons 【概率 分数】

题目：

题意：

思路：

程序：

uva10288 Coupons 【概率分数】