前言
在昭陽等地區(qū),都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局,加強發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力,以專注、極致的服務(wù)理念,為客戶提供網(wǎng)站設(shè)計、成都網(wǎng)站制作 網(wǎng)站設(shè)計制作定制網(wǎng)站建設(shè),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站設(shè)計,成都營銷網(wǎng)站建設(shè),外貿(mào)營銷網(wǎng)站建設(shè),昭陽網(wǎng)站建設(shè)費用合理。
本文主要給大家介紹了關(guān)于利用Java快速查找21位花朵數(shù)的相關(guān)內(nèi)容,分享出來供大家參考學(xué)習(xí),下面話不多說了,來一起看看詳細的介紹吧。
以前備賽的時候遇到的算法題,求所有21位花朵數(shù),分享一下,供大家參考,效率已經(jīng)很高了。
示例代碼
package com.jianggujin; import java.math.BigInteger; import java.util.ArrayList; import java.util.List; /** * 水仙花數(shù) * * @author jianggujin * */ public class NarcissusNumber { /** * 記錄10的0~N次方 */ private BigInteger[] powerOf10; /** * 記錄0到9中任意數(shù)字i的N次方乘以i出現(xiàn)的次數(shù)j的結(jié)果(i^N*j) */ private BigInteger[][] preTable1; /** * 記錄離PreTable中對應(yīng)數(shù)最近的10的k次方 */ private int[][] preTable2; /** * 記錄0到9中每個數(shù)出現(xiàn)的次數(shù) */ private int[] selected = new int[10]; /** * 記錄水仙花數(shù)的位數(shù) */ private int length; /** * 記錄水仙花數(shù) */ private List<BigInteger> results; /** * 記錄當(dāng)前的進制 */ private int numberSystem = 10; /** * @param n * 水仙花數(shù)的位數(shù) */ 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次方出現(xià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 * 記錄當(dāng)前正在選擇的數(shù)字(0~9) * @param sum * 記錄當(dāng)前值(如選了3個9、2個8 就是9^N*3+8^N*2) * @param remainCount * 記錄還可選擇多少數(shù) */ private void search(int currentIndex, BigInteger sum, int remainCount) { if (sum.compareTo(powerOf10[length]) >= 0) { return; } if (remainCount == 0) { // 沒數(shù)可選時 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)// 見結(jié)束條件2 { return; } if (currentIndex == 0) { // 選到0這個數(shù)時的處理 selected[0] = remainCount; search(-1, sum, 0); } else { for (int i = 0; i <= remainCount; i++) { // 窮舉所選數(shù)可能出現(xiàn)的情況 selected[currentIndex] = i; search(currentIndex - 1, sum.add(preTable1[currentIndex][i]), remainCount - i); } } // 到這里說明所選數(shù)currentIndex的所有情況都遍歷了 selected[currentIndex] = 0; } /** * @param currentIndex * 記錄當(dāng)前正在選擇的數(shù)字(0~9) * @param sum * 記錄當(dāng)前值(如選了3個9、2個8 就是9^N*3+8^N*2) * @param remainCount * 記錄還可選擇多少數(shù) * @return 如果當(dāng)前值符合條件返回true */ private boolean preCheck(int currentIndex, BigInteger sum, int remainCount) { if (sum.compareTo(preTable1[currentIndex][remainCount]) < 0)// 判斷當(dāng)前值是否小于PreTable中對應(yīng)元素的值 { return true;// 說明還有很多數(shù)沒選 } BigInteger max = sum.add(preTable1[currentIndex][remainCount]);// 當(dāng)前情況的最大值 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])// 見結(jié)束條件3 { return false; } } for (int i = 0; i <= currentIndex; i++) { remainCount -= counter[i]; } return remainCount >= 0;// 見結(jié)束條件4 } /** * 檢查sum是否是花朵數(shù) * * @param sum * 記錄當(dāng)前值(如選了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 * 需要檢驗的數(shù) * @return 返回value中0到9出現(xiàn)的次數(shù)的集合 */ 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; } /** * 獲得結(jié)果 * * @return */ public List<BigInteger> getResults() { return results; } public static void main(String[] args) { int num = 21; System.err.println("正在求解" + num + "位花朵數(shù)"); 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("求解結(jié)果:\t" + results); } }
運行查看結(jié)果:
正在求解21位花朵數(shù)
求解時間: 0.327537257s
求解結(jié)果: [128468643043731391252, 449177399146038697307]
總結(jié)
以上就是這篇文章的全部內(nèi)容了,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,如果有疑問大家可以留言交流,謝謝大家對創(chuàng)新互聯(lián)的支持。
標(biāo)題名稱:利用Java快速查找21位花朵數(shù)示例代碼
分享鏈接:http://bm7419.com/article32/igdpsc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供微信公眾號、外貿(mào)網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、微信小程序、網(wǎng)站營銷、App設(shè)計
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)