PTA顺序的分数
题目
题目描述
输入一个自然数 n，对于一个最简分数 a/b（分子和分母互质的分数），满足 1≤b≤n，0≤a/b≤1，请找出所有满足条件的分数，并按分数值递增的顺序输出这些分数。
输入格式:
输入一个正整数 n（1≤n≤160)。
输出格式:
每个分数单独占一行，按照分数值递增的顺序排列。
输入样例:
5
输出样例:
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
注： 1、0 和任意自然数的最大公约数就是那个自然数。 2、互质指最大公约数等于1的两个自然数。
思路
- 将没问题的点压入数组
- 不能直接取余，要用辗转相除法（比如4和6）
- 对数组进行特殊的排序
- 可以优化，不用特地计算它们的商，而是通过移项的方式构造出不等式来进行判断。
- 优化：
- 变长数组，省点空间
- 预处理：先压特殊点进去，0和1，1和1；
代码
原始代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
typedef struct{
double x,y;
}nod;
nod node[40000];
int cnt=0;
bool cmp(nod a,nod b)
{
double ad=a.x/a.y;
double bd=b.x/b.y;
return ad<bd;
}
int gcd(int a,int b)
{
if(a%b==0)
{
return b;
}
else
{
return gcd(b,a%b);
}
}
int main()
{
int n;
int i,j;
int cx,cy;
node[0].x=0;
node[0].y=1;
node[1].x=1;
node[1].y=1;
cnt=1;
cin>>n;
for(i=2;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(gcd(i,j)==1||j==1)
{
cnt++;
node[cnt].x=j;
node[cnt].y=i;
}
}
}
sort(node,node+cnt+1,cmp);
for(i=0;i<=cnt-1;i++)
{
cout<<node[i].x<<"/"<<node[i].y<<endl;
}
cout<<node[cnt].x<<"/"<<node[cnt].y;
return 0;
}
稍微改进
#include<iostream>
#include<stdio.h>
#include<algorithm>//sort
#include<string.h>
#include<vector>//变长数组
#include<math.h>
using namespace std;
typedef struct{
int x,y;
}node;
vector <node > nodes;
int cnt=0;
bool cmp(node a,node b)
{
return a.x*b.y<b.x*a.y;
}
int gcd(int a,int b)
{
if(a%b==0)
return b;
else
return gcd(b,a%b);
}
int main()
{
int n;
int i,j;
int cx,cy;
nodes.push_back(node{0,1});
nodes.push_back(node{1,1});
cin>>n;
for(i=2;i<=n;i++)
{
for(j=1;j<i;j++)
{
if(gcd(i,j)==1||j==1)
{
nodes.push_back(node{j,i});
}
}
}
sort(nodes.begin(),nodes.end(),cmp);
for(i=0;i<nodes.size();i++)
cout<<nodes[i].x<<"/"<<nodes[i].y<<endl;
return 0;
}
变长数组
- 变长数组名.size():返回元素的个数；
- 变长数组名.begin():返回起始位置；
- 变长数组名.end():返回终点位置；