PTA第1周——7-9顺序的分数

题目:

输入一个自然数 nn,对于一个最简分数 a/ba/b(分子和分母互质的分数),满足 1 \le b \le n,0 \le a/b \le 11≤bn,0≤a/b≤1,请找出所有满足条件的分数。

这有一个例子,当 n=5n=5 时,所有解为:

\frac01,\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34 ,\frac45,\frac1110​,51​,41​,31​,52​,21​,53​,32​,43​,54​,11​

给定一个自然数 nn,请编程按分数值递增的顺序输出所有解。

注:
1、00 和任意自然数的最大公约数就是那个自然数。
2、互质指最大公约数等于1的两个自然数。

输入格式

单独的一行一个自然数 nn

输出格式

每个分数单独占一行,按照大小次序排列

输入输出样例

输入

5

输出

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

说明/提示

【数据范围】
对于 100\%100% 的数据,1\le n \le 1601≤n≤160

题意分析:

判断互质数。

解题思路:

结构体存分数分母和分子,利用枚举法判断分子分母是否互质数,满足条件的存入数组,最后排序输出。

具体算法流程:

首先输入n,然后外循环列举i分母2-n、内循环列举j分子1-i,用函数cmp1辗转相除法判断分子分母是否互质数,如果互质数计数器t++并存入数组x中,枚举结束后用sort排序,并使用cmp2条件,将两分数通分比较分子的大小,排序结束后按顺序将答案输出。

实现细节(代码):

#include<bits/stdc++.h>
using namespace std;
int n,t;
struct st{
	int a,b;	
}x[1000000];
int cmp1(int k,int l)
{
	while(k%l!=0)
	{
		int s;
		s=l;
		l=k%l;
		k=s;
	}
	if(l==1) return 1;
	else return 0;
}
bool cmp2(st k,st l)
{
	if((k.a*l.b)>(k.b*l.a)) return 0;
	else return 1;
}
int main()
{
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(cmp1(i,j)==1)
			{
				t++;
				x[t].a=j;
				x[t].b=i;
			} 
		} 
	}
	sort(x+1,x+1+t,cmp2);
	cout<<"0/1";
	for(int i=1;i<=t;i++)
	{
		cout<<endl;
		cout<<x[i].a<<"/"<<x[i].b;
	}
	cout<<endl<<"1/1"<<endl;
	return 0;
}

总结:

要掌握辗转相除法,同时不要忘记在最前面加上0/1和最后面的1/1。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇