算法1
(暴力枚举)
思路:
看不出来任何数学规律,以纯暴力的角度思考这题
TreeSet存结果,正好排了序
HashSet判断最简,以这个结果的分子的值大小判断是不是最简
怕精度问题,取8位长度(太暴力了)
Java 代码
package 每日一题2024;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.TreeMap;
public class 递归_有序分数 {
static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
int n=Integer.parseInt(cin.readLine());
//需要从小到大,如何符合这个规律?
//而且要最简,这个怎么做?
//0/1最小,1/1最大
//0/1,然后是n/1-n/2-n/3-n/n之间满足的
//这之中的数学规律我找不到
//循环暴力试试,去重来保证最简?
//Treemap:键:除法的值(限定6位精确?)
//第一次10/11,会不会是精确度不够?是,要八位精度
//过了,纯暴力解法,需要学一下通法
TreeMap<Double, String> tr=new TreeMap<>();//存结果
HashMap<Double, Integer> min=new HashMap<>();//判最简
for(int i=0;i<=n;i++) {//分子
for(int j=i;j<=n;j++) {//分母
if(j==0) continue;
//分子<=分母,且分母不能为0
String tmp=(i/(double)j+"");
if(tmp.length()>8) {
tmp=tmp.substring(0, 8);//怕出现精度问题
}
String val=i+"/"+j;//存结果
double t1=Double.parseDouble(tmp);//这个分数值
if(!min.containsKey(t1)) {//未曾出现过
min.put(t1, i);//放就完事
tr.put(t1, val);
}else {
int last=min.get(t1);
if(last>i) {//不是最简,更新最简,且放入结果
min.put(t1, i);
tr.put(t1, val);
}
}
}
}
for(String s:tr.values()) {
cout.println(s);
}
cin.close();
cout.flush();
}
}