题目：
题意：
一共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 #include2 #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 }