编写程序一个三位正整数等于它的各位数字的立方和.docx

编写程序:一个三位正整数等于它的各位数字的立方和 经楼下朋友提醒，我这个算法求出的正好是21位水仙花数。于是我对其进行了稍微的修订，使得其支持任意位数的水仙花数求值，效果还不错，理论上的水仙花最大数为34位(我算了下，至少到39位还有解)，我的求解花了半分多钟，而21位数的求解只化了2秒多。原题一个21位的整数,它的各个位数的21次方的和加起来等于它本身. 要求:程序在三分钟内完成,Java语言实现.写道一个21位的整数,它的各个位数的21次方的和加起来等于它本身. 要求:程序在三分钟内完成,Java语言实现.解决思路 这个我最初的思路也是想找出其中是否有数学规律，无奈大学数学就混过来的，只能穷举解决了。 虽然是穷举，但是不同的实现，效果也不一样，如果要从100000000000000000000穷举到999999999999999999999，我想肯定麻烦大了。 这里我主要是换个思路，穷举这个数中的每个位置上的数字的总数。从一开始，我们假设共有该数中存在9个9，我们将这个数的信息存到几个特定的数组中去：Java代码privateintcountArray=newint10;/个数列表privateintcountSumArray=newint10;/个数总数privateBigIntegersumArray=newBigInteger10;/值总数privateintoffset=0;/浮标 countArray记录依次从9到0每个数的个数，countSumArray是countArray中的各个数与其之前所有数的个数的总和(即countSumArrayn=countSumArrayn-1+countNum)，sumArray是当前数的总值(即sumArrayn=sumArrayn-1+num)。offset是浮标，即当前判定的数的位置 我们对该个数进行判断，9个9后面还有12位数，那么9个9最小就是9个9的平方+12个0的平方，最大是9个9的平方+12个8的平方。我们从以下三个方面来判断： 1. 最小值不大于999999999999999999999 2. 最大值不小于100000000000000000000 3. 最大值与最小值从首部是否相同的部分，如777700000000000000000与777799999999999999999，存在7777相同的部分，如果该相同的部分中有某个数的个数大于offset中相同的值的个数，那么该值也判定为失败 还有一个很重要的判断就是，如果countSumArray中对应的offset中的值为21，那么即所有的位数都有值，那么直接判定如果该值=其各个位置上的数的21次方之和，如果不等返回失败，反之，这个数就是要求的数。 总体判断如上所述，如果失败我们即查询下一个数next()，countSumArrayoffset=21，那么就是查到头了，就返回查找back()。 用到了几个技巧，就是将BigInteger的运算结果直接存储到hashtable中去，可以节约大量运算时间。题中给予了4分钟的时间，以为很需要一段时间，就设置了多线程，后来发现，不使用多线程也只要花费2秒种，多线程的意义也就不复存在了。 应楼下朋友要求，贴图描述解题思路，很少画图，更没用Dia画过图，有粗制滥造之嫌，请勿怪了。代码实现Java代码importjava.math.BigInteger;importjava.util.Hashtable;publicclassMainprivatestaticfinalintSIZE=21;privateintcountArray=newint10;/个数列表privateintcountSumArray=newint10;/个数总数privateBigIntegersumArray=newBigInteger10;/值总数privateintoffset=0;/浮标/*设置当前浮标对应的个数，个数的总数，值总数*paramnum*个数*/privatevoidsetValue(intnum)countArrayoffset=num;if(offset=0)countSumArrayoffset=num;sumArrayoffset=p(9-offset).multiply(n(num);elsecountSumArrayoffset=countSumArrayoffset-1+num;sumArrayoffset=sumArrayoffset-1.add(p(9-offset).multiply(n(num);/*检验当前数据是否匹配*return*/privatebooleancheckPersentArray()BigIntegerminVal=sumArrayoffset;/当前已存在值BigIntegermaxVal=sumArrayoffset.add(p(9-offset).multiply(n(SIZE-countSumArrayoffset);/当前已存在值+可能存在的最大值/最小值匹配if(minVpareTo(MAX)0)returnfalse;/最大值匹配if(maxVpareTo(MIN)0?minVal.toString():MIN.toString();StringmaxStr=maxVpareTo(MAX)0?maxVal.toString():MAX.toString();/找到最小值与最大值间首部相同的部分intsameCountArray=newint10;for(inti=0;iSIZE;i+)charc;if(c=minStr.charAt(i)=maxStr.charAt(i)sameCountArrayc-0=sameCountArrayc-0+1;elsebreak;/判断如果相同部分有数据大于现在已记录的位数，返回falsefor(inti=0;i=offset;i+)if(countArrayisameCountArray9-i)returnfalse;/如果当前值的总数为SIZE位，那么判断该值是不是需要查找的值if(countSumArrayoffset=SIZE)StringsumStr=sumArrayoffset.toString();BigIntegersum=ZERO;for(inti=0;i0)offset-;elsereturntrue;if(offset0)setValue(countArrayoffset-1);returnfalse;elsereturntrue;/*测试程序*paramstartValue*测试匹配数中包含9的个数*paramstartTime*程序启动时间*/privatevoidtest(intstartValue,longstartTime)/设置9的个数offset=0;setValue(startValue);while(true)if(checkPersentArray()/检查当前提交数据是否匹配/匹配且总数正好为SIZE的位数，那么就是求解的值if(countSumArrayoffset=SIZE)success();/总数不为SIZE，且当前值不在第10位（即不等于0）if(offset!=9)next();continue;/总数不为SIZE，且当前值在第10位。if(back()break;elseif(back()break;System.out.println(Thread.currentThread()+End,Spendtime+(System.currentTimeMillis()-startTime)/1000+s);/*主函数*/publicstaticvoidmain(Stringargs)finallongstartTime=System.currentTimeMillis();ints=MAX.divide(p(9).intValue();for(inti=0;i=s;i+)/newMain().test(i,startTime);/启动十个线程同时运算finalintstartValue=i;newThread(newRunnable()publicvoidrun()newMain().test(startValue,startTime);).start();privatestaticfinalBigIntegerZERO=newBigInteger(0);privatestaticfinalBigIntegerMIN;privatestaticfinalBigIntegerMAX;/*0-SIZE间的BigInteger*/privatestaticfinalBigIntegern(inti)return(BigInteger)ht.get(n_+i);/*0-9的次方的BigInteger*/privatestaticfinalBigIntegerp(inti)return(BigInteger)ht.get(p_+i);/*用于缓存BigInteger数据，并初始化0-SIZE间的BigInteger和0-9的次方的BigInteger*/privatestaticHashtableht=newHashtable();staticints=SIZE10?10:SIZE;for(inti=0;i=s;i+)ht.put(n_+i,newBigInteger(String.valueOf(i);for(inti=0;i=10;i+)ht.put(p_+i,newBigInteger(String.valueOf(i).pow(SIZE);MIN=n(10).pow(SIZE-1);MAX=n(10).pow(SIZE).subtract(n(1);结论 运算结果如下：Console代码ThreadThread-0,5,mainEnd,Spendtime0sThreadThread-9,5,mainEnd,Spendtime0sThreadThread-5,5,mainEnd,Spendtime0sThreadThread-8,5,mainEnd,Spendtime0sfindamatchnumber:449177399146038697307ThreadThread-4,5,mainEnd,S