AcWing 1360. 有序分数(每日一题)

简介: AcWing 1360. 有序分数(每日一题)

原题链接:1360. 有序分数 - AcWing题库

题目:

给定一个整数 N,请你求出所有分母小于或等于 N,大小在 [0,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。

输出格式

按照从小到大的顺序,输出所有满足条件的分数。

每个分数占一行,格式为 a/b,其中 a 为分子, b为分母。

数据范围

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
枚举版:

由于此题数据量很小只有160,O(N^2)解决此问题完全没问题,具体思路外循环枚举分母,内循环枚举分子。只要没有最大公约数,就存取下来,然后针对于分数进行排序输出即是答案。分数排序如下图:

#include<iostream>
#include<algorithm>
using namespace std;
int n;
typedef pair<int,int> PII;
PII p[50000];//至少要开到N*N
int gcd(int a,int b){//最大公约数
  return b?gcd(b,a%b):a;
}
int cmp(PII a,PII b){//a.second/a.first<b.second/b.first,分母同时同分就得到下面式子
  return a.first*b.second>b.first*a.second;
}
int main(){
  cin>>n;
  int k=0;
  for(int i=0;i<=n;i++){
    for(int j=0;j<=i;j++){
      if(gcd(i,j)==1){//只要没有最大公约数就往里面放
        p[k++]={i,j};
      }
    }
  }
  sort(p,p+k,cmp);//由小到大排序
  for(int i=0;i<k;i++){//second是分子,first是分母
    cout<<p[i].second<<"/"<<p[i].first<<endl;
  }
  return 0;
}
递归版(Stern-Brocot Tree):

Stern-Brocot Tree:

Stern-Brocot Tree主要思想就是不断递归分裂,对于本题而言,就是第二张图,开始[0/1,1/1],找到mid=0+1/1+1,区间分裂[0/1,1/2]与[1/2,1/1],[0/1,1/2]再分裂mid=0+1/1+2,区间分裂为[0/1,1/3]与[1/3,1/2],[1/2,1/1]再分裂mid=1+1/1+2,

区间分裂为[1/2,2/3]与[2/3,1/1],以此类推……这样就得到了答案,用一个递归函数,不断往下找即可。

#include<iostream>
using namespace std;
int n;
//递归做法
void dfs(int a,int b,int c,int d){//a第一个数分母,b第一个数分子,c第二个数分母,d第二个数分子
  if(a+c>n)return;//如果分母之和大于n了就返回
  dfs(a,b,a+c,b+d);//左区间[b/a,b+d/a+c]
  cout<<b+d<<"/"<<a+c<<endl;//中间数b+d/a+c
  dfs(a+c,b+d,c,d);//右区间[b+d/a+c,d/c]
}
int main(){
  cin>>n;
  cout<<"0/1"<<endl;//第一个数0单独输出
  dfs(1,0,1,1);//从[0/1,1/1]开始
  cout<<"1/1"<<endl;//最后一个数单独输出
  return 0;
}
总结:

在做此题时,很容易想到第一种方法,第二种Stern-Brocot Tree第一次了解,顺便学习一下,在算法思想上比较简单了,也比较容易理解。大家都可以学习一下,虽然运行效率差不多,但是使用Stern-Brocot Tree的代码很简单。冲刺蓝桥杯路上会遇到各种各样的方法,大家选择自己擅长的即可,只要能ac题目的算法都是好算法。博主水平有限,文章写的一般,在描述上可能不是很清楚,若有不明白的地方,可评论,看到必回复。若文章有错误的地方,请大家指出,纠正错误,规范自己,大家一起加油。


相关文章
【LeetCode-每日一题】-378. 有序矩阵中第K小的元素
【LeetCode-每日一题】-378. 有序矩阵中第K小的元素
|
人工智能 BI
牛客 序列排列1
牛客 序列排列1
65 0
【LeetCode-每日一题】-16. 最接近的三数之和
【LeetCode-每日一题】-16. 最接近的三数之和
|
算法
代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II
代码随想录算法训练营第二天 | LeetCode 977.有序数组的平方、209.长度最小的子数组、59. 螺旋矩阵 II
56 0
|
算法 索引
代码随想录算法训练营第二天| 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结
代码随想录算法训练营第二天| 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结
|
人工智能 算法 测试技术
【AcWing每日一题】4655. 重新排序
【AcWing每日一题】4655. 重新排序
61 0
|
存储 算法 测试技术
【AcWing每日一题】4653. 数位排序
【AcWing每日一题】4653. 数位排序
119 0
每日一题——有序数组的平方
每日一题——有序数组的平方
每日一题:Leetcode977 有序数组的平方
每日一题:Leetcode977 有序数组的平方
LeetCode每日一题题解:1984. 学生分数的最小差值
LeetCode每日一题题解:1984. 学生分数的最小差值