对于一个正整数而言，长度是n，如果它的各位上的数字的n次方之和正好等于它本身，那么我们称这样的数为自幂数.
(例如：当n为3时，有1^3 + 5^3 + 3^3 = 153，153即是n为3时的一个自幂数)
n为1时，自幂数称为独身数。
n为2时，没有自幂数。
n为3时，自幂数称为水仙花数。
n为4时，自幂数称为玫瑰花数。
n为5时，自幂数称为五角星数。
n为6时，自幂数称为六合数。
n为7时，自幂数称为北斗七星数。
n为8时，自幂数称为八仙数。
n为9时，自幂数称为九九重阳数。
n为10时，自幂数称为十全十美数。
基础版(最慢):
下面的代码参考了http://www.oschina.net/code/snippet_1439376_33874
public class 自幂数 {
public static void main(String[] args) {
basicFun(7);
}
/**
* 限制n<=9,9以上速度慢的无法忍受
*/
public static void basicFun(int n) {
switch (n) {
case 1:
System.out.println("独身数:");
System.out.print("0" + "\t");
break;
case 2:
System.out.println("两位自幂数:");
System.out.println("没有自幂数！");
break;
case 3:
System.out.println("水仙花数:");
break;
case 4:
System.out.println("玫瑰花数:");
break;
case 5:
System.out.println("五角星数:");
break;
case 6:
System.out.println("六合数:");
break;
case 7:
System.out.println("北斗七星数:");
break;
case 8:
System.out.println("八仙数:");
break;
case 9:
System.out.println("九九重阳数:");
break;
default:
System.out.println("坐等屏蔽:");
break;
}
if (n >= 10 || n <= 0) {
System.out.println("----------------已屏蔽,程序结束----------------");
return;
}
// 缓存结果
Map<Integer, Long> cacheMap = new HashMap<Integer, Long>();
for (int i = 0; i < 10; i++) {
cacheMap.put(i, (long) Math.pow(i, n));
}
Map<Integer, Long> numCacheMap = new HashMap<Integer, Long>();
for (int i = 0; i < n; i++) {
numCacheMap.put(i, (long) Math.pow(10, i));
}
for (long number = (long) Math.pow(10, n - 1), len = (long) Math.pow(
10, n); number < len; number++) {
long num = 0;
for (int i = 0; i < n; i++) {
int temp = (int) (number / numCacheMap.get(i)) % 10;
num += cacheMap.get(temp);
}
// 符合条件
if (number == num) {
System.out.print(number + "\t");
}
}
}
}
缺点如下：
n=9运算非常慢，n=10基本没指望了，改进算法是尽早排除掉不符合条件的。
网上的解决方案：
参考讨论：http://bbs.csdn.net/topics/360185693
结论：理论上，最大的水仙花数不超过34位
方法1:组合combination(n+9,n)，然后一一检验是否满足条件;
方法2：双向搜提前剪枝:根据高位提前剪枝，看是否要继续递归下去
网上Java版的解决方案,使用了剪枝: http://bbs.csdn.net/topics/360188055#r_73147548
import java.math.BigInteger;
/**
* 水仙花数：N位整数，它等于各位上的数字的N次方之和，例如有一个N位数字，a1a2a3a4.....aN = a1^N +a2^N+......aN^N
*
* 算法原理： 注意：以下 sum 为各位上的数字的N次方之和 sum_a为集合a中的数的sum
*
* 对于任意的N位数字，定义形如315，351，513等这样的数字都属于“1出现1次，3出现1次，5出现1次”的集合a
* 明显可以看出“包含在集合a中的数的sum都相同”，即sum_a="1^N（位数）*T1(1出现的次数)+3^N*T3+5^N*T5"，
* 观察得，如果集合a包含水仙花数，则该水仙花数=水仙花数的sum（水仙花数定义）=sum_a（充要条件）。
* 可以随便举个反例215,512，125在集合b中，但b的sum_a=134明显不属于集合b，所以b不是包含水仙花数的集合
* 总结：将寻找水仙花数，转换为寻找包含水仙花数的集合，从而减少判断的次数。
*
* 结束条件：（楼主在这里进行了优化） 首先不是一次选完，而是从0到N个9，0到N个8...这样选，总数由remainCount控制 设当前情况为集合a
* 1.如果当sum_a大于最大数即10^N-1，矛盾 2.因最小的数字为10^(N -
* 1)，注意到，如果选某数时sum_a小于最小值，则后面的情况不用讨论了。
* 例如3位数，已选1个3选2，发现sum_a最大为=3^3*1+2^3*2=43<100，可以断定不用选2,1,0了；
* （当前情况能表示的最大数：比如说3位数我选了1个9，8的情况选完了不行，现在开始选7，最大数就是977不可能是987）
* 3.判断sum_a和当前情况能表示的最大数首部相同部分中某数出现的次数是否比已经选择的集合中该数出现的次数多
* 设sum_a=99900当前情况能表示的最大数为99988，则当前情况的数肯定在这之间即999XX，而当前情况9已经选了且只选了1次，则矛盾。
* 4.同上：相同部分中还没选的数 的出现次数比剩余的总数还多 例如相同部分为789111,1还没选而且只剩2个数没选了，则矛盾
* 5.当选完所有数时如果sum_a属于集合a，则sum_a为水仙花数。
*
*/
public class NarcissisticNumber {
/**
* 记录10的0~N次方
*/
private static BigInteger[] PowerOf10;
/**
* 记录0到9中任意数字i的N次方乘以i出现的次数j的结果（i^N*j）
*/
private static BigInteger[][] PreTable;
/**
* 记录可能为水仙花数的下限与PreTable中对应数的差
*/
// private static BigInteger[][] PreTable2; 没什么用，变量定多了不容易理解
/**
* 记录离PreTable中对应数最近的10的k次方
*/
private static int[][] PreTable3;
/**
* 记录0到9中每个数出现的次数
*/
private static int[] Selected = new int[10];
/**
* 记录水仙花数的位数
*/
private static int Length;
/**
* 记录水仙花数出现的个数
*/
private static int Count = 0;
/**
* 记录当前的进制
*/
private static int NumberSystem = 10;
public static void main(String[] args) {
long time = System.nanoTime();
for (int i = 1; i < 11; i++) {
NarcissisticNumber narcissisticNumber = new NarcissisticNumber(i);
narcissisticNumber.show();
}
time = System.nanoTime() - time;
System.out.println("time:\t" + time / 1000000000.0 + "s");
}
// 初始化计算时使用的数据结构，这也是提高效率的地方
/**
* @param n
* 水仙花数的位数
*/
public NarcissisticNumber(int n) {
PowerOf10 = new BigInteger[n + 1];
PowerOf10[0] = BigInteger.ONE;
Length = n;
for (int i = 1; i <= n; i++){
PowerOf10[i] = PowerOf10[i - 1].multiply(BigInteger.TEN);
}
PreTable = new BigInteger[NumberSystem][n + 1];
// PreTable2 = new BigInteger[NumberSystem][n + 1];
PreTable3 = new int[NumberSystem][n + 1];
for (int i = 0; i < NumberSystem; i++) {
for (int j = 0; j <= n; j++) {
PreTable[i][j] = new BigInteger(new Integer(i).toString()).pow(
n).multiply(new BigInteger(new Integer(j).toString()));
// PreTable2[i][j] = PowerOf10[Length - 1]
// .subtract(PreTable[i][j]);
for (int k = n; k >= 0; k--) {
if (PowerOf10[k].compareTo(PreTable[i][j]) < 0) {
PreTable3[i][j] = k;
break;
}
}
}
}
}
private void show() {
Search(NumberSystem - 1, BigInteger.ZERO, Length);
}
/**
* @param currentIndex
* 记录当前正在选择的数字(0~9)
* @param sum
* 记录当前值（如选了3个9、2个8 就是9^N*3+8^N*2）
* @param remainCount
* 记录还可选择多少数
*/
private static void Search(int currentIndex, BigInteger sum, int remainCount) {
if (sum.compareTo(PowerOf10[Length]) >= 0)// 见结束条件1
{
return;
}
if (remainCount == 0) {// 没数可选时
if (sum.compareTo(PowerOf10[Length - 1]) > 0 && Check(sum)) {// 见结束条件5
Count++;
System.out.print(Count + " ");
System.out.println(sum);
}
return;
}
if (!PreCheck(currentIndex, sum, remainCount))// 见结束条件3,4
return;
if (sum.add(PreTable[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(PreTable[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 static Boolean PreCheck(int currentIndex, BigInteger sum,
int remainCount) {
if (sum.compareTo(PreTable[currentIndex][remainCount]) < 0)// 判断当前值是否小于PreTable中对应元素的值
return true;// 说明还有很多数没选
BigInteger max = sum.add(PreTable[currentIndex][remainCount]);// 当前情况的最大值
max = max.divide(PowerOf10[PreTable3[currentIndex][remainCount]]);// 取前面一部分比较
sum = sum.divide(PowerOf10[PreTable3[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
}
/**
* @param sum
* 记录当前值（如选了3个9、2个8 就是9^N*3+8^N*2）
* @return 如果sum存在于所选集合中返回true
*/
private static 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出现的次数的集合
*/
public static 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;
}
}
运行结果：
1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 153 10 370 11 371 12 407 13 1634 14 8208 15 9474 16 54748 17 92727 18 93084 19 548834 20 1741725 21 4210818 22 9800817 23 9926315 24 24678050 25 24678051 26 88593477 27 146511208 28 472335975 29 534494836 30 912985153 31 4679307774 time: 0.080869496s
基本上是光速。佩服。
欢迎各位朋友给出更快更优的方法，全文完。
相关推荐
Java编程语言可以用来实现各种数学概念的计算，其中包括自幂数和特定情况下的自幂数，如水仙花数。自幂数是一个正整数，它的每一位数字的n次方之和等于它自身。比如，当n为3时，153是一个自幂数，因为1^3 + 5^3 + 3^...
本文将深入探讨接口幂等性的概念及其在Java语言中的实现方法，旨在帮助开发者更好地理解和应用这一关键技术。 #### 二、幂等性概念解析 幂等性是指对于同一操作，无论执行多少次，其结果都是一致的。具体到接口设计...
文档中提到的关键词，包括复杂网络、Java应用系统、幂律分布、类依赖图和函数依赖图等，它们各自代表了本文研究的核心概念。复杂网络是网络分析领域中的一个重要分支；Java应用系统是指使用Java语言开发的应用程序...
水仙花数是指一个n位正整数（n≥3），它的每个位上的数字的n次幂之和等于它本身的一个数。在本例中，我们关注的是三位数的水仙花数，即该数由三个数字组成，并且这三个数字各自的立方和等于这个数本身。例如，153...
在编程领域，水仙花数（也称为 Narcissistic Number）是一种特殊的数字，它在特定基数下，每个位上的数字的幂之和等于该数字本身。例如，在十进制下，370、371 和 407 是水仙花数。本Java学习资源主要围绕如何使用...
描述中的“有listView 输出，简单的实现”暗示了这是一个编程项目，可能是在某种编程语言中，比如Python、Java或C++，利用ListView控件（常见于Windows应用程序）来展示分解的过程或结果。ListView通常用于显示列表...
在进行Java代码优化时，有多个方面需要考虑，本文档提供的是一系列详细的优化建议，涵盖了异常处理、资源管理、数据结构使用、性能提升等多个角度。首先，异常处理是代码优化的重要环节。不应该对所有异常都使用通用...
在Java世界中，分布式应用程序设计是一项关键技能，它允许开发者构建可扩展的、高可用性的系统，能够跨越多个网络节点协同工作。以下是对标题和描述中所提及知识点的详细阐述： 1. **Java分布式计算基础**：Java为...
水仙花数（Narcissistic number）是指一个 n 位正整数（n≥3），它的每个位上的数字的n次幂之和等于它本身。例如，153是一个3位数，1^3 + 5^3 + 3^3 = 153，因此153是水仙花数。 #### 二、Java程序设计基础 为了...
水仙花数是一个三位数，它的每个位上的数字的三次幂之和等于它本身。 **答案解析**： - 使用for循环遍历100到999之间的所有数，然后将每个数分解为个位、十位和百位。 - 分别计算每个位上数字的立方和，判断是否...
分布式JAVA应用基础与实践是Java开发领域中的一个重要主题，它涉及到如何通过网络连接将多个独立的Java应用程序协同工作，以实现更大规模、更高性能、更可靠的服务。在本教程中，我们将深入探讨Java在分布式环境中的...
Java性能优化是一个重要的主题...总的来说，Java性能优化需要结合具体的应用场景和需求，综合运用上述技巧，以达到最佳的性能表现。不断学习和实践这些最佳实践，能够帮助开发者写出更加高效、资源利用率高的Java代码。
Java中的位运算是一种高效的操作方式，它可以直接对二进制数据进行操作，广泛应用于各种算法和数据处理中。本文将详细介绍这些位运算的应用，并通过具体的例子来解释它们的工作原理。 1. **奇偶数判断**：`a&1`可以...
左移操作符（）是位运算符之一，它在Java中有着特定的应用和理解。本篇文章将深入探讨Java中的左移操作符及其相关知识点。 一、位运算符概述 位运算符直接作用于二进制位，它们包括：左移（），右移（>>），无符号...
- **米勒-拉宾素性检验**是一种概率算法，它通过幂次取模的奇偶性测试来判断一个数是否为素数。虽然存在极小的概率误判，但在实际应用中非常高效。 - **埃拉托斯特尼筛法**是找到一定范围内所有素数的常用方法。...
在iOS应用开发中，为了实现在用户不使用应用程序时也能接收到消息，苹果公司提供了Apple Push Notification service（APNs）服务。本篇文章将详细介绍如何在服务器端使用Java来实现iPhone的推送通知功能。 首先，...
Continuation可能涉及到如何在Java Web应用中实现和利用这种技术来优化网络请求的处理，提高系统效率。 【标签】"Continuation java java教程 java电子书 教程下载"表明这是一个关于学习和理解Continuation的资源，...
因此，在实际应用中，可能需要采用更高级的算法，如斯特林公式或者矩阵快速幂等优化方法。 ### 结论 在Java中，计算10000的阶乘需要利用`BigInteger`类处理大整数，并选择适合的算法策略。递归方法虽然直观，但在...
"kafka的java的jar包"就是用于Java应用程序与Kafka进行通信的一系列库文件集合。 Kafka主要提供了消息队列的功能，能够高效地处理实时数据流，具有高吞吐量、低延迟和容错性等特点。在Java项目中，开发者会使用这些...
标题中的“Java实现的线程池、消息队列功能”是指在Java编程中，如何利用编程技术实现线程池和消息队列这两种重要的并发处理机制。...理解并熟练运用这些知识对于提升Java应用的性能和稳定性至关重要。