【AcWing】蓝桥杯集训每日一题Day10|递归|暴力|数学归纳法|1360.有序分数(C++)

本文主要是介绍【AcWing】蓝桥杯集训每日一题Day10|递归|暴力|数学归纳法|1360.有序分数(C++)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1360.有序分数

1360. 有序分数 - AcWing题库
难度：简单
时/空限制：1s / 64MB
总通过数：4128
总尝试数：6630
来源：usaco training 2.1
算法标签 枚举排序最大公约数递归Stern-Brocot Tree

---

题目内容

给定一个整数 N，请你求出所有分母小于或等于 N，大小在 [0,1] 范围内的最简分数，并按从小到大顺序依次输出。
例如，当 N=5 时，所有满足条件的分数按顺序依次为：
$$\frac{0}{1},\frac{1}{5},\frac{1}{4},\frac{1}{3},\frac{2}{5},\frac{1}{2},\frac{3}{5},\frac{2}{3},\frac{3}{4},\frac{4}{5},\frac{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

题目详解

1. 分母N在1_{160以内，分子在0}160

暴力

分子分母的组合一共只有N的平方种，可以直接暴力做，直接N^2枚举一遍，判断一下分子分母是不是互质的，互质的话，把它放到一个数组里，排个序，输出就可以了
时间复杂度$O(n^2\log n)$

#include <iostream>
#include <cstring>
#include <algorithm>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 200;int n;
PII q[N * N];//求最大公约数模板
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}bool cmp(PII a, PII b)
{//用除法可能有精度问题return a.y * b.x < a.x * b.y;
}int main()
{//读取一下数的个数scanf("%d", &n);int cnt = 0;//依次枚举分子和分母for (int i = 0; i <= n; i ++)for (int j = 0; j <= i; j ++)\//如果它们互质的话，最大公约数等于1的话if (gcd(i, j) == 1)//第一个是分母，第二个是分子q[cnt ++] = {i, j};sort(q, q + cnt, cmp);for (int i = 0; i < cnt; i ++)printf("%d/%d\n", q[i].y, q[i].x);return 0;
}

SB Tree

可以通过一个递归的方式，找出0~1之间所有的有理数

$$\left[\frac{0}{1},\frac{1}{1}\right]$$
求区间里面的某一个分界点，把分子和分子相加，分母和分母相加，就是$\frac{1}{2}$
$$\left[\frac{0}{1},\frac{1}{2}\right]\left[\frac{1}{2},\frac{1}{1}\right]$$
$$\left[\frac{0}{1},\frac{1}{3}\right]\left[\frac{1}{3},\frac{1}{2}\right]\left[\frac{1}{2},\frac{2}{3}\right]\left[\frac{2}{3},\frac{1}{1}\right]$$
通过这样的方式，就可以将0~1之间所有的有理数全部遍历出来
整棵树在遍历的时候每次输出分界点就可以了
整棵树的中序遍历就可以有序地遍历0~1之间的所有的有理数

可以用递归来做

$$\frac{b}{a}<\frac{b+d}{a+c}<\frac{d}{c}$$
每次在递归的时候，先遍历左边的所有数，再遍历中间的这个数，再遍历右边的所有数
可以用数学归纳法来证明出来整个遍历的序列是有序的
递归的本质就是数学归纳法
$$\begin{array}{c}ab+bc<ab+ad\\ bc<ad\\ bc<ad是条件，成立\\ bc+dc<ad+cd\\ bc<ad\\ 成立\end{array}$$
所以是有序的

时间复杂度$O(n^2)$

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;int n;void dfs(int a, int b, int c, int d)
{if (a + c > n)return;//先递归左边dfs(a, b, a + c, b + d);//输出中间的结果printf("%d/%d\n", b + d, a + c);//再递归右半边dfs(a + c, b + d, c, d);
}int main()
{//先读入一个nscanf("%d", &n);//输出左端点puts("0/1");//递归dfs(1, 0, 1, 1);//输出右端点puts("1/1");return 0;
}

这篇关于【AcWing】蓝桥杯集训每日一题Day10|递归|暴力|数学归纳法|1360.有序分数(C++)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---