当前位置: 首页 > news >正文

蓝桥杯每日一题:有序分数(递归)

给定一个整数 N,请你求出所有分母小于或等于 N,大小在 [0,1] 范围内的最简分数,并按从小到大顺序依次输出。

例如,当 N=5 时,所有满足条件的分数按顺序依次为:

0/1,1/5,1/4,1/3,2/5,12/,35,2/3,3/4,4/5,1/1

输入格式

共一行,包含一个整数 N。

输出格式

按照从小到大的顺序,输出所有满足条件的分数。

每个分数占一行,格式为 a/b,其中 a为分子, b 为分母。

数据范围

1≤N≤160

输入样例:
5
输出样例:
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

参考代码:

1.暴力求解参考代码:

/*
暴力枚举i,1-i中与i gcd=1的数
*/
#include<iostream>
#include<algorithm>#define x first
#define y secondusing namespace std;
const int N = 200;
typedef pair<int,int>PII;
PII q[N*N];
int n;int gcd(int a,int b)
{return b ? gcd(b,a%b) : a;
}bool cmp(PII a,PII b)
{return a.y*b.x > a.x*b.y;
}int main()
{cin>>n;int cnt = 0;for(int i=0;i<=n;i++)for(int j=0;j<=i;j++){if(gcd(i,j)==1) q[cnt++] = {j,i};}sort(q,q+cnt,cmp);for(int i=0;i<cnt;i++) printf("%d/%d\n",q[i].x,q[i].y);return 0;
}

 2.递归:

stern brocot tree原理:Stern–Brocot 树与 Farey 序列 - OI Wiki (oi-wiki.org)

#include<iostream>
#include<algorithm>using namespace std;
int n;void dfs(int a,int b,int c,int d)
{if(b+d>n) return;dfs(a,b,a+c,b+d);printf("%d/%d\n",a+c,b+d);dfs(a+c,b+d,c,d);
}int main()
{cin>>n;puts("0/1");dfs(0,1,1,1);puts("1/1");return 0;
}

 

相关文章:

蓝桥杯每日一题:有序分数(递归)

给定一个整数 N&#xff0c;请你求出所有分母小于或等于 N&#xff0c;大小在 [0,1] 范围内的最简分数&#xff0c;并按从小到大顺序依次输出。 例如&#xff0c;当 N5 时&#xff0c;所有满足条件的分数按顺序依次为&#xff1a; 0/1,1/5,1/4,1/3,2/5,12/,35,2/3,3/4,4/5,1/…...

SpringBoot学习之Kibana下载安装和启动(Mac版)(三十二)

一、简介 Kibana是一个开源的分析与可视化平台,设计出来用于和Elasticsearch一起使用的。你可以用kibana搜索、查看存放在Elasticsearch中的数据。Kibana与Elasticsearch的交互方式是各种不同的图表、表格、地图等,直观的展示数据,从而达到高级的数据分析与可视化的目的。 …...

Mac下Docker Desktop starting的解决方法

记录下自己在新增了一个新的容器后&#xff0c;Disk Size过大导致启动Docker Desktop会一直卡在Docker Desktop starting&#xff0c;并且重启无效的解决方法。该方法无需重新卸载&#xff0c;并且能保留原有的镜像和容器。 一、确认问题 首先确认Docker.raw大小以确认是否和笔…...

Leetcode面试经典150_Q80删除有序数组中的重复项 II

题目&#xff1a; 给你一个有序数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使得出现次数超过两次的元素只出现两次 &#xff0c;返回删除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件…...

android 使用ollvm混淆so

使用到的工具 ndk 21.1.6352462&#xff08;android studio上下载的&#xff09;cmake 3.10.2.4988404&#xff08;android studio上下载的&#xff09;llvm-9.0.1llvm-mingw-20230130-msvcrt-x86_64.zipPython 3.11.5 环境配置 添加cmake mingw环境变量如下图: 编译 下载…...

Swift:在 Win10 上编程入门

访问 https://swift.org/download/ 找到 Windows 10&#xff1a;x86_64 下载 swift-5.10-RELEASE-windows10.exe 大约490MB 建议安装在 D:\Swift\ &#xff0c;安装后大约占2.56GB 官网文档&#xff1a;https://www.swift.org/documentation/ 中文教程&#xff1a;The swift…...

Linux多进程通信(4)——消息队列从入门到实战!

Linux多进程通信总结——进程间通信看这一篇足够啦&#xff01; 1.基本介绍 1&#xff09;消息队列的本质其实是一个内核提供的链表&#xff0c;内核基于这个链表&#xff0c;实现了一个数据结构&#xff0c;向消息队列中写数据&#xff0c;实际上是向这个数据结构中插入一个…...

[Flutter]导入singular_flutter_sdk后运行到Android报错

问题&#xff1a; 接入归因之前&#xff0c;flutter项目一起正常。接入归因之后&#xff0c;iOS正常Android有问题。 dependencies: # Singular归因singular_flutter_sdk: ^1.3.3 针对 Flutter 的 Singular SDK 集成指南 https://support.singular.net/hc/zh-cn/articles/…...

ChatGPT新手指南:如何用AI写出专业学术论文

ChatGPT无限次数:点击直达 ChatGPT新手指南&#xff1a;如何用AI写出专业学术论文 在当今信息爆炸的时代&#xff0c;人工智能技术的快速发展为我们提供了许多新的可能性。ChatGPT作为一种先进的自然语言处理技术&#xff0c;不仅能够进行对话和文本生成&#xff0c;还可以辅助…...

【ZZULIOJ】1047: 对数表(Java)

目录 题目描述 输入 输出 样例输入 Copy 样例输出 Copy code 题目描述 输入两个正整数m和n&#xff0c;输出m到n之间每个整数的自然对数。 输入 输入包括两个整数m和n(m<n)&#xff0c;之间用一个空格隔开。 输出 每行输出一个整数及其对数&#xff0c;整数占4…...

thinkphp6使用阿里云SDK发送短信

使用composer安装sdk "alibabacloud/dysmsapi-20170525": "2.0.24"封装发送短信类 发送到的短信参数写在env文件里面的 #发送短信配置 [AliyunSms] AccessKeyId "" AccessKeySecret "" signName"" templateCode"&…...

file_get_contents(‘php://input‘); 这个postman要如何传参

在 Postman 中传递参数给 file_get_contents(php://input); 是通过请求的 Body 部分来实现的。使用 Postman 进行 API 接口测试时&#xff0c;可以按照以下步骤来传递参数&#xff1a; 打开 Postman 并创建一个新的请求。在请求的 URL 地址栏输入你的 API 地址。选择请求方法为…...

HDFS [MSST‘10] 论文阅读笔记

原论文:The Hadoop Distributed File System (MSST’10) HDFS关键技术要点概览 设计目标:HDFS旨在可靠地存储大型数据集,并以高带宽流式传输这些数据集到用户应用程序。它通过在大量服务器上分布存储和计算资源,使得资源可以随着需求的增长而扩展,同时保持经济高效。架构组…...

Feature Pyramid Networks for object detection

FPN 总述1.引言2.相关工作3. Feature Pyramid NetworksBottom-up pathwayTop-down pathway and lateral connections 4. 应用用于 RPN用于 Fast R-CNN 核心代码复现FPN网络结构ResNet Bottleneck完整代码 总述 下图中&#xff0c;蓝色边框表示的是特征图&#xff0c;边框越粗表…...

Linux下docker运行python

前言 本机开发环境众多&#xff0c;python版本都好多个&#xff0c;虽然可以通过conda管理多个虚拟环境&#xff0c;但还是不能像容器那样进行进程间的隔离。于是打算试下docker下运行python&#xff0c;而且生产环境很多时候也是用容器来跑应用&#xff0c;环境统一、方便扩容…...

MacOS下载和安装HomeBrew的详细教程

在MacOS上安装Homebrew的详细教程如下&#xff1a;&#xff08;参考官网&#xff1a;macOS&#xff08;或 Linux&#xff09;缺失的软件包的管理器 — Homebrew&#xff09; 步骤1&#xff1a;检查系统要求 确保你的MacOS版本至少为macOS Monterey (12) (or higher) 或更高版本…...

AI技术在金融领域/银行业的应用和风险

前言 随着科技的不断发展&#xff0c;人工智能&#xff08;AI&#xff09;技术已经在各行各业得到了广泛的应用&#xff0c;其中包括银行业。银行业作为经济的重要组成部分&#xff0c;一直在不断地探索和应用新技术&#xff0c;以提升服务效率、风险管理和客户体验。然而&…...

每日OJ题_两个数组dp⑤_力扣10. 正则表达式匹配

目录 力扣10. 正则表达式匹配 解析代码 力扣10. 正则表达式匹配 10. 正则表达式匹配 难度 困难 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符* 匹配零个或多个前面的那一个元素 所谓匹配&#xff0c…...

开源区块链系统/技术 总结(欢迎补充,最新)

一、联盟链 1. FISCO BCOS FISCO BCOS 2.0 技术文档 — FISCO BCOS 2.0 v2.9.0 文档https://fisco-bcos-documentation.readthedocs.io/ 2. ChainMaker&#xff08;长安链&#xff09; 文档导航 — chainmaker-docs v2.3.2 documentationhttps://docs.chainmaker.org.cn/v2…...

LeetCode 994—— 腐烂的橘子

阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 1.记录下初始新鲜橘子的位置到 notRotting&#xff0c;我们按照行把二维数组拉成一维&#xff0c;所以&#xff0c;一个vector 就可以实现了&#xff1b;2.如果没有新鲜橘子&#xff0c;那么第 0 分钟所有橘子已经…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...