徐某


私信TA

用户名:1078110251

访问量:864

签 名:

等  级
排  名 5658
经  验 1521
参赛次数 0
文章发表 2
年  龄 0
在职情况 学生
学  校 西南石油大学
专  业

  自我简介:

TA的其他文章

解题思路:先读题意,其中的核心要点在于:

                                                                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的因子和,然后假设其存在亲密数BB的值自然应该等于sum(A)。在此基础之上,尝试继续推演是否满足条件2

        在这个思路下,可以很好的避免穷举法浪费大量时间的弊端,进一步精确寻找亲密数的对象。


注意事项:有一些小细节需要注意,即重复输出的问题。for循环的遍历效果会导致一对亲密数交换顺序后再次输出。QQ截图20211115140136.png
因此需要在最后输出时添加一个判断条件: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 人评分

新上线《蓝桥杯辅导》课程,近五年的蓝桥杯省赛与国赛真题都有,从读题开始理解题意、梳理思路、实现代码再提交评测全过程,可有效提升获奖比例甚至进国赛!课程介绍、试听请猛击这里

  评论区

  • «
  • »