题目描述
牛村村口要架设一个矩形的广告屏,村长要求广告屏的总像素必须为n,还要求广告屏的长和宽最大可能的接近,而且宽不能大于长,村长找你来计算一下宽和长分别为多少?
输入描述:
输入一行,包含一个正整数n表示像素点个数。 (1 <= n <= 1000000)
输出描述:
宽和长,两个整数之间用空格隔开。 ------------------------------------------------------------- 1、一开始看到这道题的时候首先想到的是,先找到所有的n的因数 然后再去找里面相乘能得到n的两个因数,使之为一个组,然后比较所有组,找出两数之差最小的那一组,然后输出就可以了。 然而在真正去编程的时候发现想要把这些不定长个数的数据存到一个数组里面多少有点难度, 需要链表来使存储的数据的长度可变。这就人为的增加了解题的难度。 为了能够更好的解题,又进行了进一步的思考,其实因数都是成对存在的。 正如10有一个因数2存在,那必定有5(10/2=5)存在。2和5都是成对存在的。 也就是说,可以先用穷举法挨个找出每个成对存在的数据组。 2、然后结束条件是找到的这两个数据在该数由小到大的因数排序中是挨着的。 在开始编写程序的时候又想到了一种特殊情况,如果这两个数相等怎么办? 我一开始的想法是先判断该数能否经过平方根变换后依旧是整数,如果是,那直接就能得出答案。 可是新的问题又来了,如何判断一个数是不是整数,我搜了老半天也找不到对应的函数。(想了很久,没有思路,于是决定先记下这些思考) 3、(在记录第二个思考轨迹的时候,突然想到其实不用这么麻烦) 遇到两个相等的数相乘等于给定的数,只要判断一下除数与被除数的结果是否和除数相等, 就能明了该除数是否是所求解。于是我开始用这种思路编程。 一开始的思路是直接判断除数与结果是否相等,但是后来看到不管你是否判断除数与结果的大小, 你都需要保存上一个因数的值。来判断下一个因数是否与上个因数的乘积是否是给定的数。 而我就开始想着能否把这两种情况合二为一,刚才试了一下(并没有捋清解题思路),结果是错的。 感觉以后可以减少这种做法,先把思路理清或许可以节省更多的时间。 只不过,在你没有思路且不知道思路对不对的时候,这种做法或许可以让你对解题思路有一个更清晰的认识。 经过试错之后,慢慢明白了这种情况其实是错的,因为保存的值如果正好是给定数的平方根, 那么循环会继续往下走,会自增,这样除数就已经变了,就算再计算出一个结果,那也已经不是真正的平方根了。 因此,应该分为两种情况来看待这个问题。 #include <iostream> #include <math.h> using namespace std; int main(){ int num; cin>>num; int temp=1; for(int i=1;i<=num;i++){ if(i==num/i){ cout<<i<<" "<<i; break; } if(num%i==0){ if(num==temp*i){ cout<<temp<<" "<<i; break; }else{ temp=i; } } } } 4、经过编程之后,只有60%的样例通过,但是也不知道到底哪里出错了,于是看了一下其他人的正确答案。 发现他们的思路好厉害,我虽然考虑过那种思路,但是并不能把那种思路变成代码。 那个人的思路就是,既然要找出相近的两个因数并且乘积是给定数,那么这两个因数必定分为两种情况。 第一种,给定数的平方根正好解释此题的解,第二种此题的解中较大的那个数必定是大于平方根的最小因数。 然后顺便就能求出较小的那个因数。 ---------------------------------------------------------------------- 基础版#include <iostream>#include <math.h>usingnamespacestd;intmain(){intnum;cin>>num;inttemp=floor(sqrt(num));if(num==temp*temp){cout<<temp<<" "<<temp;return0;}for(inti=temp+1;;i++){if(num%i==0){cout<<num/i<<" "<<i;break;}}}----------------------------------------------------------------------------------------- 改进版#include <iostream>#include <math.h>usingnamespacestd;intmain(){intnum;cin>>num;inttemp=floor(sqrt(num));for(inti=temp;;i++){if(num%i==0||temp*i==num){cout<<min(i,num/i)<<" "<<max(i,num/i);break;}}------------------------------------------------------------------------------------在由基础班改进到改进版中间出现过一个问题,就是输出语句不用比较函数时输出的两个数是颠倒的。我再调试一下看看这到底是什么情况。经过思考,这是由于我担心会出现平方根出现不能识别的情况,所以,采取了保守的策略,把平方根之前的那个整数也包含了进来。用的函数是向下取整,但是,这种情况会导致一些边界测试的乱序,比如8的正确答案是2 4但8开根之后是2.82左右,向下取整是2,如果此时从2开始判断,会出现满足情况的状况。这个时候输出的结果就会是4 2,然后经过进一步的思考,就算只是向上取整,平方根的解也是不会漏掉的,因为一个整数向上取整还是这个整数。所以可以放心使用向上取整。经过测试,向上取整确实可以得到正确的结果,而且,这个程序还少用了两个比较函数,速度能够更快一些,使用空间也能缩小一些。程序思路也比较清晰严谨。下面是最终的解答程序。#include <iostream> #include <math.h> using namespace std; int main(){ int num; cin>>num; int temp=ceil(sqrt(num)); for(int i=temp;;i++){ if(num%i==0||temp*i==num){ cout<<num/i<<" "<<i; break; } } }