用c编程，给定一个正整数N,由所有分母小于或等于N的最简真分数按从小到大组成一个序列

Question

用c编程，给定一个正整数N,由所有分母小于或等于N的最简真分数按从小到大组成一个序列如1/5 1/4 1/3 2/5 1/2 3/5 3/4 4/5

Answer 1

新写两个函数，一个是求最大公约数的函数，一个是排序函数。

最简真分数，就是分子和分母最大公约数为1

按降序排列，把一个元素插入一个有序队列中。

#include <stdio.h>
struct struct_result{
int numerator;
int denominator;
float result;
};
struct struct_result list[999]={0};

int listLength = 0;
int getMaxFactor(int m, int n){
int r = m % n;
while(r > 0){
m = n;
n = r;
r = m % n;
}
return n;
}
void addList(struct struct_result res){
int i,j;
//添加进列表中
     for(i=0; i<listLength; i++){
      if(list[i].result > res.result){
      break;
     }
     }
     if(i<listLength){
      //找到自己所在的位置 
      for(j=listLength; j>i; j--){
      list[j] = list[j-1];
     }
     list[i] = res;
     listLength++;
     } else {
      //添加到列表末尾 
      list[listLength++] = res;
     }
}
int main(){
int n = 5;
int i,j;
printf("请输入一个正整数：");
scanf("%d", &n);
for(i=1; i<n; i++){
for(j=i+1; j<=n; j++){
if(1 == getMaxFactor(j, i)){
//找到一个符合条件的结果
 struct struct_result res;
 res.numerator = i;
 res.denominator = j;
 res.result = 1.0f*i/j;
 addList(res);
}
}
}
for(i=0; i<listLength;i++){
printf("%d/%d ", list[i].numerator, list[i].denominator);
if(i>0 && i % 10 == 0){
printf("\n");
}
}
}