找亲和数 - 虹狐 Home Hu

题目描述

如果整数A的全部因子（包括1，不包括A本身）之和等于B；且整数B的全部因子（包括1，不包括B本身）之和等于A，则A和B称为亲密数。求10000以内的亲密数。

思路

直接遍历到10000，每个数a找一次因子，计算因子和为b,再找b的因子，计算因子和是否等于a
跑肯定是能跑，但是这样未免也太过无聊，于是我在网上想找一下有没有什么好的算法研究一下

N=1e05;                 % 所取数范围
fac_sum=zeros();    
for A=1:N               % 被除数
    fac_sum(A)=0;       % 所有因式和
    for x=1:(A-1)       % 除数
        if (mod(A,x)==0) 
            fac_sum(A)=fac_sum(A)+x;    % 每个数所有真因式之和
        end
    end
end
fprintf('%g范围内的亲和数:\n',N);
for i=1:N
    B=fac_sum(i);   
    if B>0 && B<= N                     % 使得数字B在数组的索引范围内
        if fac_sum(B) == i && (B~=i)    % 亲和数的条件，同时剔除本身相等情况
            fprintf('%g,%g\n',B,i);
        end
    end
end

然后看到了c语言的代码实现，细细观察了一下，感觉发现了Matlab的最大特点——矩阵！
如此的话，也怪不得数模需要用Matlab了
网上查了一下，发现Matlab就是“矩阵实验室”😓汗。。。

#include <stdio.h>
int main()
{
    int a, b, i, n;
    for (a = 1; a < 10000; a++)
    {
        b = 0;
        for (i = 1; i <= a / 2; i++)
        {
            if (a % i == 0)
                b += i;
        }
 
        n = 0;
        for (i = 1; i <= b / 2; i++)
        {
            if (b % i == 0)
                n += i;
        }
        if (n == a && a < b)
            printf("(%4d,%4d)\n", a, b);
    }
 
    return 0;
}

头脑风暴

上面Matlab的思路是直接一个a[]数组，a[i]放的就是第i个数的因数和
所以第一次for循环就是在做这个数组，做完之后我只要看a[i]与a[(a[i])]是否相等就能判断是不是亲和数
不过很容易想到的一个弊端：

会出现重复比较的情况—— 一对亲和数出现两次 ，比如：
- 220,284
- 284,220

目前解决办法只想到链表代替，找到一个之后立刻删除另外一个对应结点，但是只用链表显然无法做到立刻删除一个index为i的结点，或许加一个 黑名单 ，每次比较之前判断在不在黑名单内？
但是这样有明显画蛇添足，还不如就让他多比较一次，因为本身亲和数就是相对于范围来说很少的(目前已经知道的有1000多对亲和数，而10000以内的只有5对，在100000以内有13对)，为了这少量的几次比较反而用更复杂的链表实在是。。。
不过貌似可以使用哈希表，嗯，非常可行，嗯对，可以。
突然想到这是Matlab啊，链表哈希表都没有！
唉，不考虑编程语言的话哈希表确实是比较完美的解决方案了，不过我貌似又忽略了使用哈希表本身也降低了程序的处理速度啊

如果你有更完美的方案，欢迎与我交流！

总结

这次最大的收获是意识到了Matlab的一个重要特点，今后写Matlab一定要着重发挥矩阵的作用。

解决了什么问题

怎样寻找最大亲和数
- 最大亲和数的标准
- 怎样实现，怎样不暴力地实现

得到了什么结果

寻找因数时快速减少运算量的标志—— x/2
Matlab的重要特性—— 矩阵

形成了什么结论

想要最大发挥Matlab的特性，一定要活用矩阵