问题描述:
查找所有n位黑洞数。这里黑洞数是指该自然数各位数字组成的最大数与最小数之差仍为原自然数本身,例如6174是4位黑洞数,有7641-1467=6174。
思路与优化:
对于上面的问题,很自然的想法是枚举所有n位数并检查是否为黑洞数。
当参数n较小时,上面的代码运行很好,但随着n的变大,代码运行时间急剧增加以至于无法忍受甚至在计算上不可行。
分析上面的代码,每次循环中的计算量并不大,之所以慢是因为循环次数太多,也就是搜索范围太大,并且其中很多测试是不必要的。
根据黑洞数的定义可知,同一组数字最多只能构成一个黑洞数,找到一个黑洞数之后这组数字的其他排列都可以直接跳过。
忽略顺序的话可以使用组合来求解,又因为黑洞数的各位数字是允许重复的,所以需要借助于允许重复的组合来求解。
同样是穷举算法,改写后的代码没有多余的测试,每组数字只测试一次,大幅度减少了搜索范围。那么效率提升具体怎样呢,写几行代码测试和比较一下,红色下画线为第一个函数的运行时间(单位:秒),绿色下画线为改写后第二个函数的运行时间。可以看到,在位数并不太大的时候,效率已经提升了几十万倍。
运行结果:
稍微改写代码,继续增加位数长度并单独测试第二个函数,第一个函数对于这样的长度已经无能为力了。n=28时第一个函数的搜索范围约为10**27,第二个函数搜索范围为组合数C(10+28-1,28)=124403620,第一个函数是第二个函数的10**18倍。n=35时,第一个函数的搜索范围约为10**34,第二个函数搜索范围为组合数C(10+35-1,35)=708930508,第一个函数是第二个函数的10**25倍。
运行结果: