输入一个自然数 N 请写一个程序来增序输出分母小于等于 N 的既约真分数
输入格式: 单独的一行 一个自然数 N(1…160)
输出格式: 每个分数单独占一行
输入样例1: 在这里给出一组输入。例如：
5输出样例1: 在这里给出相应的输出。例如：
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1输入样例2:
4输出样例2:
0/1 1/4 1/3 1/2 2/3 3/4 1/1输入样例3:
10输出样例3:
0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1【思路】 1.一个分数值只对应一种既约真分数形式，与map中的 key-value 的一一对应关系相同， 且每个分数值都是唯一的，而 map 中的 key 也是唯一的。 故我使用map，把 “分数值” 作为 map 中的key，把 “分数形式” 作为map中的value， 储存为 “分数值-分数形式” 对；
2.为了保证 分数形式 为 即约真分数形式 利用map的覆盖功能，在遍历的同时更新 分数的形式；
3.map会自动对键进行从小到大排序 便于按从小到大顺序，遍历输出结果；
【源代码】
#include <iostream> #include <string> #include <map> using namespace std; int main() { float n; cin >> n; map<float, string> Map; // 创建一个 map，分数值作为 key， 分数形式作为 value； Map[0] = "0/1"; // 特定储存两个数据：(1)0/1， (2)1/1 = n/n； Map[1] = "1/1"; float frac = 0; // 分数的值 for (float i = n; i > 1; i--) // i:分母 { for (float j = 1; j < n; j++) // j:分子 { frac = j / i; if (frac < 1) // 保证储存key的是真分数 { Map[frac] = (to_string((int)j)) + "/" + (to_string((int)i)); // 更新分数值对应的真分数形式，保证该真分数为既约真分数； } } } map<float, string>::iterator iter; for (iter = Map.begin(); iter != Map.end(); iter++) { cout << iter->second << endl; } return 0; }