编辑

【递归】005 求21位的水仙花数

2019-11-13 2019-11-13 49 2 ---【递归】 Hoji

一、题目

需满足的条件:每个位上的数字21次方的和等于这个21位数字本身。long类型表示的最大范围是19位数。

水仙花数:指一个 n 位数 ( n≥3 ),它的每个位上的数字的 n 次幂之和等于它本身。(例如:1^3 + 5^3+ 3^3 = 153

二、解法

(1)暴力破解(超时)

对最小的21位数到最大的21位数进行逐一判断

(2)递归

//方法说明
vauleOf(int) 将整型数据转换为大数值 
multiply() 大数值乘法 
add() 大数值加法 
.ZERO/.ONE 大数值0、1的定义

(1)calc_21():不需要在循环中计算0~9的21次方是多少,可以实现计算出来,存入到一个BigInteger[10]数值中, (2)int[10] a:记录每一个数值出现的次数

import java.math.BigInteger;
public class X11 {
	static BigInteger[] x = new BigInteger[10];
	public static BigInteger calc_21(int n){
		BigInteger b = BigInteger.ONE;
		for(int i=0;i<21;i++){
		b = b.multiply(BigInteger.valueOf(n));//21次乘以n,得n^21
		}
		return b;
	}

	public static void test(int[] a){
		BigInteger sum = BigInteger.ZERO;//总和
		for(int i=1;i<10;i++){//加9次(0的21次方等于0,不需要加)
			sum = sum.add(x[i].multiply(BigInteger.valueOf(a[i])));//valueOf(int) 方法对int进行转换为BigInteger大整数
		}
		//接下来比较
		String s = sum.toString();//大整数,使用字符串进行比较
		if(s.length() != 21) return;

		int[] a1 = new int[10];//注意是与a[]进行比较,所以需要将大整数的结果字符串进行解析

		for(int i=0;i<21;i++){
			a1[s.charAt(i) - '0']++;//按位处理结果,转换为a1[] 的数据
		}
		//比较
		for(int i=0;i<10;i++){
			if(a1[i] != a[i]) return;
		}
		System.out.println(s);
	}

	//x存放数字的21次方数据 , a存放数字出现次数 , cur当前处理的数字 , use已经使用的位数
	public static void f(int[] a,int cur,int use){
		if(use == 21){
			test(a);
			return;
		}
		if(cur==9){//9个数字枚举完毕,进行计算判断
			a[9] = 21-use;
			test(a);//测试是否成功找到数字
			return;
		}
		//枚举
		for(int i=0; i<21-use; i++){

			a[cur] = i;//当前数字出现的次数:i
			f(a,cur+1,use+i);
			a[cur] = 0;//不要忘记回溯
		}
	}
	public static void main(String[] args) {
		//0~9的21次方给数组x[]
		for(int i=0; i<10; i++){
			x[i] = calc_21(i);
		}
		int[] a = new int[10];//记录每个数字出现的次数
		f(a,0,0);			 //递归主方法
	}
}
//结果
//128468643043731391252
//449177399146038697307

Hoji的CSDN(其中不乏各种框架教程、学习方法..) https://blog.csdn.net/qq_43539599

倘若小文于你有益,欢迎
  • 如果您的提问博主没能及时回复,通过分享文章获得援助,何尝不是一种查缺补漏的好做法
  • 版权声明:本文为博主原创文章,遵循CC 4.0 BY版权协议
  • 文章转载:请在文末添加原文章地址,这也是尊重他人劳动成果的一点体现,谢谢您的配合!
  • 评论信息 (注:评论收到回复后,会以邮箱的方式提醒您;您的邮箱不会显示到页面中)

    验证码信息 看不清?点击图片进行切换!
    精彩随处可见 更多精彩内容
    作者: 浏览 61 评论 1 赞 1 2020-01-15
    作者: 浏览 62 评论 1 赞 1 2019-11-29
    作者: 浏览 83 评论 1 赞 1 2019-11-29
    作者: 浏览 54 评论 1 赞 1 2019-11-29
    作者: 浏览 52 评论 1 赞 1 2019-11-29
    目录