USACO 2.1.2 Ordered Fractions
2011年9月14日 18:25
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!
程序的效率還是不錯的。
貼上代碼：
/*
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;
}
