欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  Java

Java实现快速查找21位花朵数的示例代码

程序员文章站 2022-05-12 09:45:20
...
这篇文章主要给大家介绍了关于利用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, 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] - '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位花朵数的示例代码的详细内容,更多请关注其它相关文章!