解题思路:先读题意,其中的核心要点在于:
1.A的因子和(包括1但不包括A本身)等于B。即sum(A)==B
2.B的因子和(包括1但不包括B本身)等于A。即sum(b)==A
最开始打算直接穷举1~3000的所有自然数,用两层for循环(A从1~3000,再for循环B从1~3000穷举)来判断是否符合题意。
思路很自然,但很可惜超时了。在自己电脑上运行起来需要30秒左右甚至更长的时间才能得出全部结果。
那么就需要优化思路。因为上一个思路的弊端在于,两重for循环浪费了大量的时间来遍历基本不可能成为亲密数的自然数对
参照了很多C语言的题解思路,但是感觉自己愚钝,不是很能理解一些步骤的意图。
我很喜欢定义不同的函数,将小过程整体化,以增加主代码的可读性。所以看一些代码觉得很不适应。
后来摸索出一个适合的优化方法,假设法。
也就是说,可以先求出一个自然数A的因子和,然后假设其存在亲密数B,B的值自然应该等于sum(A)。在此基础之上,尝试继续推演是否满足条件2。
在这个思路下,可以很好的避免穷举法浪费大量时间的弊端,进一步精确寻找亲密数的对象。
注意事项:有一些小细节需要注意,即重复输出的问题。for循环的遍历效果会导致一对亲密数交换顺序后再次输出。
因此需要在最后输出时添加一个判断条件:b大于a。
另外还需要排除完数,即像(6,6)这样的数字,它的因子和等于自身,也是需要排除的特殊存在。因此需要添加判断条件:因子和不等于本身,sum(A)!=A.
参考代码:
#include <stdio.h> int sum(int x);//声明一个求和函数 int main() { int a, b;//两自然数A B for (a = 1; a < 3000; a++)//遍历3000以内自然数 { if (sum(a) != a)/*排除完数*/ { b = sum(a);//直接将A的因子和赋值给b,以便假设满足第一个条件,再推导此情况下是否满足第二个条件 if ((sum(b) == a)/*若满足第二个条件*/&&(b>a)/*并且b大于a*/) { printf("(%d,%d)", a, b); }/*输出结果*/ } } } int sum(int x)//求因子和函数 { int i;//循环变量 int s=0;//因子和 for (i = 1; i < x ; i++) { if (x % i == 0/*判定此时i是否为x的一个因子*/) { s = s + i; } } return s; }
0.0分
0 人评分