给定一个正整数N,由所有分母小于或等于N的最简真分数按从小到大组成一个序列,例如,N=5,
1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5
编一个程序,输入一个正整数,输出上述序列。
#include<stdio.h> int jc(int x){ //阶乘 int i,n=1; for(i=1;i<=x;i++) n*=i; return n; } void maxY(int x,int y){ //找最大公约数 int i,max,min; max=x>y?x:y; min=x>y?y:x; for(i=min;i>0;i--) if(max%i==0&&min%i==0){ // i是最大公约数 printf("%d/%d ",min/i,max/i); //以真分数形式输出 break; } } void sort(int x){ //由小到大排序 int n=jc(x),num[n]={0}; //n是x的阶乘,在下面充当分母;num[]里存放通分之后的分子 int i,j,len=0; int k,temp; for(i=1;i<x;i++) for(j=x;j>i;j--){ if(i==1) //如果不加这一句,分子为1的真分数就取不到了 num[len++]=n/j*i; else if(j%i!=0) num[len++]=n/j*i;//把能取到的真分数全部通分,分子存在num[]里 } for(i=0;i<len-1;i++){ //冒泡排序(由小到大) k=i; for(j=i;j<len;j++) if(num[j]<num[k]) k=j; if(k!=i){ temp=num[k]; num[k]=num[i]; num[i]=temp; } } for(i=0;i<len;i++) maxY(num[i],n);//输出真分数形式 } int main(){ int n; scanf("%d",&n); sort(n); return 0; }
public static List<String> solution(int n) { Set<Data> set = new HashSet<>(); for (float i = 2; i <= n; i++) { for (float j = 1; j <= i - 1; j++) { StringBuilder builder = new StringBuilder(); String name = builder.append(j).append("/").append(i).toString().replace(".0", ""); set.add(new Data(name, j / i)); } } List<Data> list = new ArrayList<>(set); list.sort(new Comparator<Data>() { @Override public int compare(Data o1, Data o2) { return o1.getValue() > o2.getValue() ? 1 : -1; } }); List<String> result = list.stream().map(o -> { return o.getName(); }).collect(Collectors.toList()); return result; } static class Data { private String name; private float value; public Data(String name, float value) { this.name = name; this.value = value; } public String getName() { return name; } public void setName(String name) { this.name = name; } public float getValue() { return value; } public void setValue(float value) { this.value = value; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Data data = (Data) o; return Float.compare(data.value, value) == 0; } @Override public int hashCode() { return Objects.hash(value); } @Override public String toString() { return "Data{" + "name='" + name + '\'' + ", value=" + value + '}';
package cn.gof; import java.util.ArrayList; import java.util.List; public class Test3 { public static void main(String[] args) { List<String> list = new ArrayList<String>(); method(5, list); sort(list); } public static void method(int n, List<String> list) { for (int i = 1; i < n; i++) { if (i == 1 || n % i != 0) { list.add(i + "/" + n); } method2(i, list); } } public static void method2(int n, List<String> list) { for (int i = 1; i < n; i++) { if (i == 1 || n % i != 0) { list.add(i + "/" + n); } } } public static boolean compare(String a, String b) { String[] arr = a.split("/"); int a1 = Integer.valueOf(arr[0]); int a2 = Integer.valueOf(arr[1]); String[] arrb = b.split("/"); int b1 = Integer.valueOf(arrb[0]); int b2 = Integer.valueOf(arrb[1]); if (a1 * b2 > b1 * a2) { return true; } else { return false; } } public static void sort(List<String> list) { for (int i = 0; i < list.size() - 1; i++) { for (int j = 0; j < list.size() - i - 1; j++) { if (compare(list.get(j), list.get(j + 1))) { list.add(j + 1, list.get(j)); list.add(j, list.get(j + 2)); list.remove(j + 1); list.remove(j + 2); } } } for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i)); } } }