USACO - Freddy - Freddy の ブログ

 

Ordered Fractions

Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.

Here is the set when N = 5:

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

PROGRAM NAME: frac1

INPUT FORMAT

One line with a single integer N.

 

输入一个自然数N,对于一个最简分数a/b（分子和分母互质的分数）,满足1<=b<=N,0<=a/b<=1,请找出所有满足条件的分数。

这有一个例子，当N=5时，所有解为：

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

给定一个自然数N，1<=n<=160，请编程按分数值递增的顺序输出所有解。

注：①0和任意自然数的最大公约数就是那个自然数②互质指最大公约数等于1的两个自然数。

 

 

SAMPLE INPUT (file frac1.in)

5

OUTPUT FORMAT

One fraction per line, sorted in order of magnitude.

SAMPLE OUTPUT (file frac1.out)

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

 

本題相對而言還是USACO中的一道比較簡單的題目，但竟然放在了第二章...

本題唯一不好弄的地方就是判斷和排序，我的判斷函數列了很多種情況。

 

然後就是排序，無論我怎麼調試，用qosrt對結構體或類中的double型變量排序的結果很悲劇，不知道它是按什麽順序排的，於是我就放棄了快排函數，改用自己寫的靜態鏈表排序。

我寫的靜態鏈表排序：http://zhuyifan2007.5gbfree.com/cpp/lb.html

提交給USACO官網后竟然一次AC！

 

我的測評結果：
USER: YeeFan Zhu [zyfwork1]
TASK: frac1
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 4272 KB]
   Test 2: TEST OK [0.000 secs, 4272 KB]
   Test 3: TEST OK [0.000 secs, 4272 KB]
   Test 4: TEST OK [0.000 secs, 4272 KB]
   Test 5: TEST OK [0.000 secs, 4272 KB]
   Test 6: TEST OK [0.000 secs, 4272 KB]
   Test 7: TEST OK [0.000 secs, 4272 KB]
   Test 8: TEST OK [0.027 secs, 4272 KB]
   Test 9: TEST OK [0.081 secs, 4272 KB]
   Test 10: TEST OK [0.135 secs, 4272 KB]
   Test 11: TEST OK [0.459 secs, 4272 KB]

All tests OK.

YOUR PROGRAM ('frac1') WORKED FIRST TIME! That's fantastic -- and a rare thing.

Please accept these special automated congratulations.

Here are the test data inputs:

------- test 1 ----
1
------- test 2 ----
2
------- test 3 ----
4
------- test 4 ----
7
------- test 5 ----
10
------- test 6 ----
15
------- test 7 ----
24
------- test 8 ----
50
------- test 9 ----
75
------- test 10 ----
100
------- test 11 ----
160

Keep up the good work!
Thanks for your submission!
 

 

程序的效率還是不錯的。

 

貼上代碼：

?
USACO 2.1.2 C++滿分代碼
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
84
85
86
87
88
89
90
/*
PROB: frac1
ID: zyfwork1
LANG: C++
*/
 
#include <fstream>
using namespace std;
ifstream fin("frac1.in");
ofstream fout("frac1.out");
 
int top=0;
 
struct Fractions
{
    double key;
    double fenzi;
    double fenmu;  
    int sen;//後繼
        int next;//前驅
}N[40000];
 
void Insert(double key,double fenzi,double fenmu)
{
    int point=0;
    while (key>N[point].key)
    {
        point=N[point].next;
    }
    //Create a new node
    N[top].key=key;
    N[top].fenzi=fenzi;
    N[top].fenmu=fenmu;
     
    N[top].next=point;
    N[top].sen=N[point].sen;
     
    N[point].sen=top;//後繼的前驅等于自己
    N[N[top].sen].next=top;//前驅的後繼等于自己
     
    top++;
}
 
bool isHZ(int ma,int mi)
{
    if (ma==1 && mi==0) return true;
    if (ma==1 && mi==1) return true;
    if(mi>ma) return false;
    if (ma==1) return false;
    if (mi==0) return false;
    for (int i=2;i<=mi;i++)
    {
        if (ma%i==0 && mi%i==0) return false;
    }
    return true;
}
 
void print()
{
    int point=N[0].next;
    while(N[point].next!=-1)
    {
    fout<<N[point].fenzi<<"/"<<N[point].fenmu<<endl;
        point=N[point].next;
    }
}
 
int main()
{
    N[0].key=-1;N[0].next=1;N[0].sen=-1;
    N[1].key=65525;N[1].next=-1;N[0].sen=0;
    top=2;
    int num;
    fin>>num;
     
    for (int i=1;i<=num;i++)
    {
        for (int j=0;j<=i;j++)
        {
            if (isHZ(i,j))
            {
                double di=i;
                double dj=j;
                Insert(dj/di,dj,di);
            }
        }
    }
    print();   
    return 0;
}