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!
 

 

程序的效率還是不錯的。

 

貼上代碼：

/*
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;
}