一种21位水仙花数算法思路

《一种21位水仙花数算法思路》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、这里我主耍是换个思路，穷举这个数中的每个位置上的数字的总数。从一开始，我们假设共有该数中存在9个9,我们将这个数的信息存到几个特定的数组中去：Java代码—1.privateint[]countArray=newint[10];//个数列表2.privateintcountSumArray=newint[10];//个数总数3.privateBiginteger[]sumArray=newBiginteger[10];//值总数4.privateintoffset二0;//浮标countArray记录依次从9到0每个数的个数，countSumArray是countArray中的各个数

2、与其之前所有数的个数的总和(即countSumArray[n]=countSumArray[n~l]+countNum),sumArray是当前数的总值(即sumArray[n]=sumArray[n-1]+num)。offset是浮标，即当前判定的数的位置我们对该个数进行判断，9个9后面还有12位数，那么9个9最小就是9个9的平方+12个0的平方,最大是9个9的平方+12个8的平方。我们从以下三个方面来判断：1.最小值不大于9999999999999999999992.最大值不小于1000000000000000000003.最大值与最小值从首部是否相同的部分，如777700000

3、000000000000与777799999999999999999,存在7777相同的部分，如果该相同的部分中有某个数的个数大于offset中相同的值的个数，那么该值也判定为失败还有一个很重要的判断就是，如果countSumArray中对应的offset中的值为21,那么即所有的位数都有值，那么直接判定如果该值二其各个位置上的数的21次方之和，如果不等返冋失败，反之，这个数就是要求的数。总体判断如上所述，如果失败我们即查询下一个数nextO,countSumArray[offset]=21,那么就是查到头了，就返回查找back()0用到了几个技巧，就是将Biginteger的运算结

4、果直接存储到hashtable中去，可以节约大量运算吋间。题中给予了4分钟的时间，以为很需要一段吋间，就设置了多线程，后来发现，不使用多线程也只要花费2秒种，多线程的意义也就不复存在了。设一个长度为10的数组.分别记录从9到0中每个数的个数。设定：MAX是扌旨21位数的最大值999999999999999999999MN为1000000000000000000000以21位数的水仙花数为例，其最大可以拥有MAX/（9-21）个9,超出这个数就越界了从以下4方面判昕：L是否满足最大值条件（这个值最小可能为9-21f是不是比MAX还大）2•是否满足最小值条件（这个值最大可能为9-21+1

5、2*（8-21）.是不是比MIN还小）3判断当前值是最大值与最小值存在的首部相同部分是否比数组中个数还多.F图演示）4.当这是个21位的数，判断其21次方的总和是否等于该值.这是題意.满足条件：912当满足条件是.查找与之相近的最大可能值游标指到下一位上.即12开始：9我们假设这个数组通过上面的3个条件。9+12,这是21位的数，进行第4个判断.发现不满足条件。使用F—个数：911对原有12减一这个数也通过前3个条件.在第4个条件上因为这不是21位数，判断不一个垃使用F—个数：9111游标指向1同样这个数也不满足条件，判断匸一个数911091101同样不满足如此继续直到：911000

6、00000当浮标指到了0的位子上.并且这里也没找到满足条件的值.回溯。9109101除了上述查找到最后一位，没找到相应的值.还有一种原因会引起回溯，那就是检验失败。如：9100不满足上述4个条件中的任意一个.因此需进行下一个减一操作.但是此时该位置已为0因此进行回溯上述4个条件.124都很好理解.3的意思是如F图所示：37这里3和7的最大值为199987956456799765253最小值为199987928733746266472存在相同的首SP1999879,但是明显，这里有4个9,超出上面的3的限制。判定失败。（以上垃据只是用来描述逻辑，可能是错溟的，请注意区分）