机试小课堂丨搜索周·例题讲解①《分数拆分》

【声明：本文为原创文章,未经同意,严禁转载和抄袭,违者将追究其法律责任】

苏世机试小课堂，考研机试不再慌！

公主号：苏世学社考研  苏世计算机考研

分数拆分

题目描述

现在输入一个正整数k,找到所有的正整数x>=y,使得1/k=1/x+1/y。

示例

输入

第一行输入一个整数n，代表有n组测试数据；接下来n行每行输入一个正整数k。

输出

先输出所有组数，然后按顺序输出对应每行的k找到所有满足条件1/k=1/x+1/y的组合。

样例输入

   2

   1

   2

样例输出

   1

   1/1=1/2+1/2

   2

   1/2=1/6+1/3

   1/2=1/4+1/4

    

答案

①读题:

题目描述显而易见。

②想出思路：

暴力枚举所有的x、y，找到所有的x、y，所以先确定x、y的数据范围，根据题目中给出的数据关系，1/x<=1/y、1/k=1/x+1/y，所以1/k-1/y<=1/y即y<=2k，又因为x=k*y/(y-k)，所以在k到2k之间枚举y计算x即可。

③动手编程：

④测试样例：

⑤提交代码：

UVA10976，可进入UVA网站进行提交。

本题总结

暴力枚举题，注意根据题目给出的条件确定要枚举数据的范围，然后在范围内进行遍历。

未完待续

苏世学社旗下品牌，专注于计算机考研

计算机考研一手资讯，原创高质量干货

深度的学习分享丨咨询前辈丨个性化指导