Java implementiert Beispielcode, um schnell 21-stellige Blumennummern zu finden

Dieser Artikel führt Sie hauptsächlich in die relevanten Informationen zur Verwendung von Java ein, um die 21-stellige Blumennummer im Detail zu finden. Er wird eine Referenz für alle sein, die sie benötigen Lesen Sie es weiter unten.

Vorwort

In diesem Artikel werden hauptsächlich relevante Inhalte zur Verwendung von Java zum schnellen Auffinden von 21-stelligen Blumennummern vorgestellt und als Referenz bereitgestellt und studieren, im Folgenden gibt es nicht viel zu sagen, werfen wir einen Blick auf die ausführliche Einführung.

Ich bin auf ein Algorithmusproblem gestoßen, als ich mich auf den Wettbewerb vorbereitete. Ich möchte die Anzahl aller 21 Blumen als Referenz mitteilen.

Beispielcode

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, sum, 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, BigInteger sum, int remainCount)
 {
  if (sum.compareTo(preTable1[currentIndex][remainCount]) < 0)// 判断当前值是否小于PreTable中对应元素的值
  {
   return true;// 说明还有很多数没选
  }
  BigInteger max = sum.add(preTable1[currentIndex][remainCount]);// 当前情况的最大值
  max = max.pide(powerOf10[preTable2[currentIndex][remainCount]]);// 取前面一部分比较
  sum = sum.pide(powerOf10[preTable2[currentIndex][remainCount]]);

  while (!max.equals(sum))
  {
   // 检验sum和max首部是否有相同的部分
   max = max.pide(BigInteger.TEN);
   sum = sum.pide(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] - &#39;0&#39;]++;
  }

  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);
 }
}

Führen Sie aus, um die Ergebnisse anzuzeigen:

Auflösen nach 21-stelliger Blumennummer

Lösungszeit: 0,327537257s

Lösungsergebnis: [128468643043731391252, 44917739914603869 7307 ]

Zusammenfassung

Das obige ist der detaillierte Inhalt vonJava implementiert Beispielcode, um schnell 21-stellige Blumennummern zu finden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!