计蒜客 合法分数的组合

题目描述：

输入一个自然数 N，我们总可以得到一些满足“1≤b≤N,0≤a/b≤1”条件的最简分数 a/b（分子和分母互质的分数），请找出所有满足条件的分数。
比方说，当 N=5 时，所有解为：
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
现在，你需要对于一个给定的自然数 N，1≤N≤160，请编程按分数值递增的顺序输出所有解。

注：0 和任意自然数的最大公约数就是那个自然数、互质指最大公约数等于 1 的两个自然数。

输入包括一个给个给定的自然数 N

输出为一个列表，每个分数单独占一行，按照实际大小从小到大排列

样例输入

5

样例输出

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

思路：

  这是一道在枚举列表中的题目，有点类似暴力破解，b 从 1 到 N，然后 a 满足（分子和分母互质）的条件，将所有可能都枚举出来，接着排序，输出。

  满足（分子和分母互质）的条件：先枚举出一个 b，然后再枚举 a，用“辗转相除法”判断 a 和 b 是否满足要求，如果满足就放入相对应的数组中。

  排序：第一次遇到分数排序，没有找到思路，网上找了一些别人的代码，其实和冒泡差不多的思路。

代码：

//https://nanti.jisuanke.com/t/30
#include<iostream>
using namespace std;
int gcb(int x,int y)
{
    int c;
    c=x%y;
    while( c!=0 )
    {
        x=y;
        y=c;
        c=x%y;
    }
    return y;
}

int main()
{
    int N;
    int a[10000]={0},b[10000]={0};
    int c;
    int i,j;
    int k=0;
    scanf("%d",&N);
    for(i=2;i<=N;i++)
    {
        for(j=1;j<=i;j++)
        {
            c=gcb(i,j);
            if(c==1)
            {
                k++;
                a[k]=j;
                b[k]=i;
            }
        }
    }
    //SORT
    for(i=1;i<=k;i++)
    {
        for(j=i+1;j<=k;j++)
        {
            float c=a[i]*1.0/b[i];
            float d=a[j]*1.0/b[j];
            if(c>d)
            {
                int t;
                t=a[j];
                a[j]=a[i];
                a[i]=t;

                t=b[j];
                b[j]=b[i];
                b[i]=t;
            }
        }
    }
    cout<<"0/1"<<endl;
    for(i=1;i<=k;i++)
        cout<<a[i]<<"/"<<b[i]<<endl;
    cout<<"1/1"<<endl;
    return 0;
}