HDU/HDOJ 1099 Lottery

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1099

以前记得做过这题,不过HDOJ上次资料丢失,导致我已经AC的150题也没了,就重新做了遍。

水题吧~~~

就是求n*(1/1 + 1/2 + … + 1/n)

我AC的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
using namespace std;
 
typedef struct tt{
    __int64 fenmu, fenzi;
}tt;
 
int gcd(int a, int b)//求最大公约数
{
    if(a < b)
        return gcd(b, a);
    if(a%b == 0)
        return b;
    return gcd(b, a%b);
}
 
tt add(tt a, tt b)
{
    int temp = gcd(a.fenmu, b.fenmu);
    tt c;
    c.fenmu = a.fenmu*b.fenmu/temp;
    c.fenzi = c.fenmu/a.fenmu*a.fenzi + c.fenmu/b.fenmu*b.fenzi;
    int g = gcd(c.fenzi, c.fenmu);
    c.fenmu /= g;
    c.fenzi /= g;
    return c;
}
 
int bit(int n)
{
    int cnt = 0;
    while(n)
    {
        ++cnt;
        n /= 10;
    }
    return cnt;
}
 
int main()
{
    bit(1234);
    int n;
    while(cin >> n)
    {
        tt res, temp;
        res.fenmu = 1;
        res.fenzi = 1;
        for(int i=2; i<=n; ++i)
        {
            temp.fenmu = i;
            temp.fenzi = 1;
            res = add(res, temp);
        }
        res.fenzi *= n;
        //cout << "res: " << res.fenzi << " " << res.fenmu << endl;
        if(res.fenzi/res.fenmu*res.fenmu == res.fenzi)
            cout << res.fenzi/res.fenmu << endl;
        else
        {
            int num1 = res.fenzi/res.fenmu;
            int num2 = res.fenzi - num1*res.fenmu;
            int gg = gcd(num2, res.fenmu);
            res.fenmu /= gg;
            res.fenzi = num2/gg;
            int t1 = bit(num1);
            int t2 = bit(res.fenzi);
            int t3 = bit(res.fenmu);
            for(int i=1; i<=t1+1; ++i)
                cout << " ";
            cout << res.fenzi<< endl;
            cout << num1 << " ";
            for(int i=1; i<=t3; ++i)
                cout << "-";
            cout << endl;
            for(int i=1; i<=t1+1; ++i)
                cout << " ";
            cout << res.fenmu << endl;
 
 
        }
    }
}

我写的很乱,下面这个写的比较不错:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
using namespace std;
 
int getBit(int n)
{
    int i=0;
    while(n!=0){
        n/=10;
        ++i;
    }
    return i;
}
void print(int s,int n,int d){
    int i,len=getBit(s)+1;
    for(i=0;i<len;++i)
        putchar(' ');
    printf("%d\n%d ",n,s);
    len=getBit(d);
    for(i=0;i<len;++i)
        putchar('-');
    putchar('\n');
    len=getBit(s)+1;
    for(i=0;i<len;++i)
        putchar(' ');
    printf("%d\n",d);
    return;
}
 
int gcd(int n,int d){
    while( n!=d ) {
        if(n>d)  n=n-d;    
        else  d=d-n;
    }
    return  n;
}
 
int main()
{
    int n,i;
    int sum,g;
    int numerator;
    int denominator;    
 
    while(cin>>n){
        sum=0;
        numerator=0;
        denominator=1;
        for(i=1;i<=n;i++){
            numerator=numerator*i+n*denominator;
            denominator*=i;
            g=gcd(numerator,denominator);
            numerator/=g;
            denominator/=g;
            sum+=numerator/denominator;
            numerator%=denominator;
        }
        if(numerator==0) 
            printf("%d\n",sum);
        else
            print(sum,numerator,denominator);
    }
    return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 1099 Lottery》有342个想法

    1. 《算法导论》适合当一本字典,遇到这个算法不会时,就去查,入门不太推荐,入门的书挺多的,刘如佳的算法竞赛入门经典和算法艺术与信息学竞赛,王晓东的计算机算法设计与分析,吴文虎的忘了叫啥,你搜搜就知道了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注