文章目录
一、题目二、分析思路三、C语言代码四、相关链接
回复此贴：https://bbs.csdn.net/topics/394896625
一、题目
奇怪数为这样一个整数 @wowpH ①：除了自身以外所有因子之和大于这个数本身（首先必须是盈数） ②：除了自身以外所有因子的集合，没有任何一个子集中所有数的和等于这个数本身
例如：70就是一个奇怪数，求1000以内的第二个奇怪数 70的除自身外的因子有：1，2，5，7，10，14，35。 它们的和为：74 > 70，所以70是盈数。 不存在一个子集的和为70（或4），所以它是奇怪数。
二、分析思路
核心部分分两个函数：一个用于判断是否是盈数，一个用于判断是否存在子集和为自身。@pfdvnah
1、用数组保存所有除自身外的因子 2、for 循环查找所有因子。循环到平方根即可。一趟循环可以找出两个因子。 3、注意，如果数自身是平方数，那么循环里面就多加了一次。循环后面要减掉。 4、是盈数返回 1，不是返回 0
子集和通过回溯计算。更好的是 DP 实现，怕新手看不懂，所以直接用回溯解决。实际上思路差不多。 每个数有两种状态，加到子集中，不加到子集中。@wowpH 不断地这样选择，直到所有数都选择完后，看看还剩余多少，剩的刚好为 0 的话，说明有子集的和为 num，即不是奇怪数。
三、C语言代码
#include <stdio.h>
#include <math.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define MAX_FACTOR_NUM 1000
#define LEFT 71
#define RIGHT 1000
int strangeNumber(int);
int sum
;
int factor
[MAX_FACTOR_NUM
];
int factorNum
;
int abundantNumber(int);
int back(int, int);
int main(void) {
for (int i
= LEFT
; i
<= RIGHT
; ++i
) {
if (TRUE
== strangeNumber(i
)) {
printf("%d\n", i
);
}
}
return 0;
}
int strangeNumber(int num
) {
if (FALSE
== abundantNumber(num
)) {
return FALSE
;
}
if (FALSE
== back(0, num
)) {
return FALSE
;
}
return TRUE
;
}
int abundantNumber(int num
) {
memset(factor
, 0, sizeof(factor
));
factorNum
= 0;
factor
[factorNum
++] = 1;
sum
= 1;
int max
= (int)sqrt(num
);
for (int i
= 2; i
<= max
; ++i
) {
if (0 == num
% i
) {
factor
[factorNum
++] = i
;
factor
[factorNum
++] = num
/ i
;
sum
+= i
+ num
/ i
;
}
}
if (max
* max
== num
) {
--factorNum
;
sum
-= max
;
}
return sum
<= num
? FALSE
: TRUE
;
}
int back(int index
, int left
) {
if (index
>= factorNum
) {
return 0 == left
? FALSE
: TRUE
;
}
if (FALSE
== back(index
+ 1, left
)) {
return FALSE
;
}
if (FALSE
== back(index
+ 1, left
- factor
[index
])) {
return FALSE
;
}
return TRUE
;
}
四、相关链接
题目来源：https://bbs.csdn.net/topics/394896625 原文链接：https://blog.csdn.net/pfdvnah/article/details/102832648 盈数_百度百科：https://baike.baidu.com/item/%E7%9B%88%E6%95%B0/2567294?fr=aladdin
- End - wowpH - pfdvnah -
