合法分数的组合

骑猪看日落 2022-10-01 00:44 10阅读 0赞

输入一个自然数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

思路：

枚举分子分子（分子分母的关系要控制好）， 在将每组结果保存结构体中，按结果进行排序

代码：

#include<iostream>
    #include<string.h>
    #include<algorithm>
    #include<cstdio>
    using namespace std;
    struct node
    {
    	int aa;
    	int bb;
    	double s;
    }st[10000];
    int check(int a,int b)
    {
    	int t,i;
    	if (a==0)
    	{
    		if (b!=1)
    			return 0;
    		else
    			return 1;
    	}
    	if (a<=b)
    	{
    		t = a;
        }
        else
        {
    		t = b;
        }
        for (i=2; i<=t; i++)
        {
    		if (a%i==0 && b%i==0)
    			return 0;
        }
        return 1;
    }
    bool cmp(const struct node &x,const struct node &y)
    {
    	return x.s<y.s;
    }
    int main()
    {
    	int a,b,n,k=0,i;
    	cin>>n;
    	for (b=1; b<=n; b++)
    	{
    		for (a=0; a*1.0/b<=1; a++)
    		{
    			if (check(a,b))
    			{
    				st[k].aa=a;
    				st[k].bb=b;
    				st[k].s = a*1.0/b;
    				k++;
    			}
    		}
    	}
    	sort(st,st+k,cmp);
    	for (i=0; i<k; i++)
    	{
    		cout<<st[i].aa<<"/"<<st[i].bb<<endl;
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关组合数

1 const ll mod=1e9+7; 2 ll qpow(ll a,ll b) 3 { 4 ll c=1; 5

刺骨的言语ヽ痛彻心扉/ 2023年06月05日 12:33/ 0 赞/ 70 阅读

相关 1056 组合数的和 (15 分)

题目：[1056 组合数的和 (15 分)][1056_15] > 给定 N 个非 0 的个位数字，用其中任意 2 个数字都可以组合成 1 个 2 位的数字。要求所有可能

Bertha 。/ 2023年06月04日 15:58/ 0 赞/ 50 阅读

相关组合数的和

给定 N 个非 0 的个位数字，用其中任意 2 个数字都可以组合成 1 个 2 位的数字。要求所有可能组合出来的 2 位数字的和。例如给定 2、5、8，则可以组合出：25、28

布满荆棘的人生/ 2023年02月20日 07:28/ 0 赞/ 27 阅读

相关回溯算法之合法括号组合（回溯剪枝）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

忘是亡心i/ 2023年01月10日 10:00/ 0 赞/ 193 阅读

相关合法分数的组合

输入一个自然数N，我们总可以得到一些满足“1≤b≤N,0≤a/b≤1”条件的最简分数a/b（分子和分母互质的分数），请找出所有满足条件的分数。比方说，当N=5时，所有解为：

骑猪看日落/ 2022年10月01日 00:44/ 0 赞/ 11 阅读

相关组合数的计算

组合数的计算 Time Limit: 2000ms Memory limit: 32768K 有疑问？点这里^\_^ 题目描述给定n组整数(a,b)，计算组

太过爱你忘了你带给我的痛/ 2022年08月10日 04:58/ 0 赞/ 241 阅读

相关组合数

组合数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述找出从自然数1、2、... 、n（0<n<10）中任取r(0<r<=n)

Love The Way You Lie/ 2022年08月05日 07:26/ 0 赞/ 245 阅读

相关组合数

组合数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述找出从自然数1、2、... 、n（0<n<10）中任取r(0<r<=n)

怼烎@/ 2022年07月12日 13:14/ 0 赞/ 251 阅读

相关组合数(dfs)

给出一个正整数N，从集合\{1,2,3..N\} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整数T,代表T组测试数据。接下来T行

淡淡的烟草味﹌/ 2022年05月15日 01:11/ 0 赞/ 284 阅读

相关组合数模板

证明过程可参考此篇博客[https://www.cnblogs.com/liziran/p/6804803.html][https_www.cnblogs.com_lizira

灰太狼/ 2021年07月16日 13:32/ 0 赞/ 432 阅读