P1062 最简分数
2024-10-08 14:31:11
P1062 最简分数
转跳点:
1062 最简分数 (20分)
一个分数一般写成两个整数相除的形式:N/M,其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。
现给定两个不相等的正分数 N1/M1 和 N2/M2,要求你按从小到大的顺序列出它们之间分母为 K 的最简分数。
输入格式:
输入在一行中按 N/M 的格式给出两个正分数,随后是一个正整数分母 K,其间以空格分隔。题目保证给出的所有整数都不超过 1000。
输出格式:
在一行中按 N/M 的格式列出两个给定分数之间分母为 K 的所有最简分数,按从小到大的顺序,其间以 1 个空格分隔。行首尾不得有多余空格。题目保证至少有 1 个输出。
输入样例:
7/18 13/20 12
输出样例:
5/12 7/12
乍一看没看明白题目以为要把分母变成K后保持值大小不变而且还是最简分数,当场吐槽了一句什么鬼,后来才发现是自己眼瞎了。它要求找出a~b之间分母为K的最简分数。瞎了瞎了。
如果这样这道题一个很简单才对哦,结果发现通过率0.18……嗯……肯定有坑。
果然第一个坑就是ab之间,两端不取。肯定不止一个,题目里还是明确给出了这一点的,嗯再读一遍。……果然要注意a,b的大小。坑啊,题目里没有明确给出……。(我错了四次,成功拉低了通过率)
两边不娶,那就得解决一下C语言的“地板除”了,关于这个我写过一篇向上取整的博客,U•ェ•*U,自行了解
- 开始点:需要 L > K * N1 / M1 >= L – 1,由于C语言整型的“地板除”运算,一定有 K * N1 / M1 = L – 1,那么初始点就是 L = K * N1 / M1 + 1。这样不需要用循环来确定。
- 结束点:要避免“地板除”带来的问题,使用 N2 * K > M2 * L 作为判断标准。
AC代码
#include <stdio.h>
#include <stdlib.h> int GDB(int a, int b); int main(void)
{
int N1, M1, N2, M2, K, L = 1; scanf("%d/%d %d/%d %d", &N1, &M1, &N2, &M2, &K); //直接交叉相乘得出AB的大小
if (N1 * M2 > N2 * M1)
{
L = N1;
N1 = N2;
N2 = L;
L = M1;
M1 = M2;
M2 = L;
} int count = 0;
for (L = N1 * K / M1 + 1; N2 * K > M2 * L; L++)
{ //避开C的地板除、题目说不能取两边
if (1 == GDB(L, K))
{
printf("%s%d/%d", count++ ? " " : "", L, K);
}
} return 0;
} int GDB(int a, int b)
{
for (int r; (r = a % b); a = b, b = r)
;
return b;
}
PAT不易,诸君共勉!
最新文章
- thinkPHP环境搭建小记
- 【WP开发】实现“摇一摇”功能
- Hibernate类中集合的映射
- iOS 推送消息长度
- JBPM4之decision节点:3、程序猿|菜鸟|攻城狮|牛人
- nargin函数的用法
- 实例:基于ListActivity实现列表
- chart.js使用常见问题
- 理解JDK1.5的自动装箱拆箱
- SQL命令语句小技巧
- DSAPI之摄像头追踪指定颜色物体
- SharePoint 2013 新特性 (三) 破改式 &mdash;&mdash; 设计管理器的使用 [1.设备通道]
- rcc时钟
- 通过修改Tomcat配置,解决乱码问题
- python基础一 ------如何根据字典值对字典进行";排序";
- 在web.xml中配置Spring的application.xml
- java,sort函数的深刻理解
- Bootstrap(3) 表格与按钮
- Python自动化开发 - Django【进阶篇】
- maven exclusions version
热门文章
- SpringBoot yml文件语法
- PageObject
- Mybatis的逆向工程以及Example的实例函数及详解
- 弹出USB大容量存储设备时出问题的解决方法
- HTML 5 <;em>; <;strong>; <;dfn>; <;code>; <;samp>; <;kbd>; <;var>; <;cite>; 标签
- CS231n -Assignments 1 Q1 and Q2
- Lesson 11 How to grow old
- Linux系统监控 zabbix-agent 主机添加的操作页面
- 十三、web应用中路径总结
- computed、methods、watch