Additive Number

定义像这样的数是Additive number：112358，因为：1+1=2，1+2=3，2+3=5,3+5=8. 1212243660也是，虽然1+2！=1，但是12+12=24，12+24=36，24+36=60

对给定范围，如：从1到10，000，000，找出所有Additive number.

（我对题目有点疑惑：199100199算不算？1+99=100,99+100=199，如果算的话情形还挺复杂。不过话说回来，即使限定了说additive的因子都位数相同，我目前也没有好思路……）

首先你得明确你提到的那一点，是不是因子位数相同。
我觉得这个题应该罗列前两位的排列，比如11 12以及迭代次数就决定了生成的additive number。 迭代次数1 对应1112，迭代次数2对应111223,迭代次数3对应11122335就超出范围了。
考虑所有需要罗列的前两位数的组合最多是1000*1000的数量级，平均迭代次数是3次左右，应该能在给定时间算出来所有的组合。

我觉得这题暴力搜索挺好做的.

北美农民 发表于 2013-11-19 01:49
我觉得这题暴力搜索挺好做的.

用recursive呢？

kang1415926 发表于 2013-11-18 12:50
用recursive呢？

recursion只是一种implement手段， 你当然可以用了

北美农民 发表于 2013-11-19 02:08
recursion只是一种implement手段， 你当然可以用了

嗯，谢谢~ 我今天再写一写……先把暴力写出来，优化什么的还得再琢磨琢磨

kang1415926 发表于 2013-11-18 13:24
嗯，谢谢~ 我今天再写一写……先把暴力写出来，优化什么的还得再琢磨琢磨

这题生成的规则需要弄清楚， 比如100001能不能算100+1还是必须算10000+1. 接下来你只需要枚举前两个数，一旦这两个数确定，那么当前的答案就确定了。 当然你可能需要hash排除重复的答案

>< 占楼..刚才方法不对. 再想想
想起来了. 以前是做过. 这题复杂度很低的. 比如说2位的话, 总长度知道. 除一下看看是不是2位的倍数. 然后在看3位. 因为是做加法所以要满足A+B=C就是起码要有三个长度才可以. 在加上int本身的长度.其实复杂度很低