利用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.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]

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对的支持。