大佬教程收集整理的这篇文章主要介绍了利用Java快速查找21位花朵数示例代码,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
前言
本文主要给大家介绍了关于利用Java快速查找21位花朵数的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧。
以前备赛的时候遇到的算法题,求所有21位花朵数,分享一下,供大家参考,效率已经很高了。
示例代码
package com.jianggujin; import java.math.bigInteger; import java.util.ArrayList; import java.util.List; /** * 水仙花数 * * @author jianggujin * */ public class Narcissusnumber { /** * 记录10的0~N次方 */ private BigInteger[] powerOf10; /** * 记录0到9中任意数字i的N次方乘以i出现的次数j的结果(i^N*j) */ private BigInteger[][] preTable1; /** * 记录离PreTable中对应数最近的10的k次方 */ privatE int[][] pretable2; /** * 记录0到9中每个数出现的次数 */ privatE int[] SELEcted = new int[10]; /** * 记录水仙花数的位数 */ privatE int length; /** * 记录水仙花数 */ private List<BigInteger> results; /** * 记录当前的进制 */ private int numberSystem = 10; /** * @param n * 水仙花数的位数 */ private Narcissusnumber(int n) { powerOf10 = new BigInteger[n + 1]; powerOf10[0] = BigInteger.oNE; length = n; results = new ArrayList<BigInteger>(); // 初始化powerPowerOf10 for (int i = 1; i <= n; i++) { powerOf10[i] = powerOf10[i - 1].multiply(BigInteger.TEN); } preTable1 = new BigInteger[numberSystem][n + 1]; pretable2 = new int[numberSystem][n + 1]; // preTable[i][j] 0-i的N次方出现0-j次的值 for (int i = 0; i < numberSystem; i++) { for (int j = 0; j <= n; j++) { preTable1[i][j] = new BigInteger(new Integer(i).toString()).pow(n) .multiply(new BigInteger(new Integer(j).toString())); for (int k = n; k >= 0; k--) { if (powerOf10[k].compareTo(preTable1[i][j]) < 0) { pretable2[i][j] = k; break; } } } } } public static List<BigInteger> search(int num) { Narcissusnumber narcissusnumber = new Narcissusnumber(num); narcissusnumber.search(narcissusnumber.numberSystem - 1,BigInteger.ZERO,narcissusnumber.length); return narcissusnumber.getResults(); } /** * @param currenTindex * 记录当前正在选择的数字(0~9) * @param sum * 记录当前值(如选了3个9、2个8 就是9^N*3+8^N*2) * @param remainCount * 记录还可选择多少数 */ private void search(int currenTindex,BigInteger sum,int remainCount) { if (sum.compareTo(powerOf10[length]) >= 0) { return; } if (remainCount == 0) { // 没数可选时 if (sum.compareTo(powerOf10[length - 1]) > 0 && check(sum)) { results.add(sum); } return; } if (!precheck(currenTindex,sum,remainCount)) { return; } if (sum.add(preTable1[currenTindex][remainCount]).compareTo(powerOf10[length - 1]) < 0)// 见结束条件2 { return; } if (currenTindex == 0) { // 选到0这个数时的处理 SELEcted[0] = remainCount; search(-1,0); } else { for (int i = 0; i <= remainCount; i++) { // 穷举所选数可能出现的情况 SELEcted[currenTindex] = i; search(currenTindex - 1,sum.add(preTable1[currenTindex][i]),remainCount - i); } } // 到这里说明所选数currenTindex的所有情况都遍历了 SELEcted[currenTindex] = 0; } /** * @param currenTindex * 记录当前正在选择的数字(0~9) * @param sum * 记录当前值(如选了3个9、2个8 就是9^N*3+8^N*2) * @param remainCount * 记录还可选择多少数 * @return 如果当前值符合条件返回true */ private Boolean precheck(int currenTindex,int remainCount) { if (sum.compareTo(preTable1[currenTindex][remainCount]) < 0)// 判断当前值是否小于PreTable中对应元素的值 { return true;// 说明还有很多数没选 } BigInteger max = sum.add(preTable1[currenTindex][remainCount]);// 当前情况的最大值 max = max.divide(powerOf10[pretable2[currenTindex][remainCount]]);// 取前面一部分比较 sum = sum.divide(powerOf10[pretable2[currenTindex][remainCount]]); while (!max.equals(sum)) { // 检验sum和max首部是否有相同的部分 max = max.divide(BigInteger.TEN); sum = sum.divide(BigInteger.TEN); } if (max.equals(BigInteger.ZERO))// 无相同部分 { return true; } int[] counter = getCounter(maX); for (int i = 9; i > currenTindex; i--) { if (counter[i] > SELEcted[i])// 见结束条件3 { return false; } } for (int i = 0; i <= currenTindex; i++) { remainCount -= counter[i]; } return remainCount >= 0;// 见结束条件4 } /** * 检查sum是否是花朵数 * * @param sum * 记录当前值(如选了3个9、2个8 就是9^N*3+8^N*2) * @return 如果sum存在于所选集合中返回true */ private Boolean check(BigInteger sum) { int[] counter = getCounter(sum); for (int i = 0; i < numberSystem; i++) { if (SELEcted[i] != counter[i]) { return false; } } return true; } /** * @param value * 需要检验的数 * @return 返回value中0到9出现的次数的集合 */ privatE int[] getCounter(BigInteger value) { int[] counter = new int[numberSystem]; char[] sumChar = value.toString().toCharArray(); for (int i = 0; i < sumChar.length; i++) { counter[sumChar[i] - '0']++; } return counter; } /** * 获得结果 * * @return */ public List<BigInteger> getResults() { return results; } public static void main(String[] args) { int num = 21; System.err.println("正在求解" + num + "位花朵数"); long time = System.nanoTime(); List<BigInteger> results = Narcissusnumber.search(num); time = System.nanoTime() - time; System.err.println("求解时间:\t" + time / 1000000000.0 + "s"); System.err.println("求解结果:\t" + results); } }
运行查看结果:
正在求解21位花朵数
求解时间: 0.327537257s
求解结果: [128468643043731391252,449177399146038697307]
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对编程小技巧的支持。
以上是大佬教程为你收集整理的利用Java快速查找21位花朵数示例代码全部内容,希望文章能够帮你解决利用Java快速查找21位花朵数示例代码所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。