首页 > 21位水仙花数。

21位水仙花数。

N=21时,所有满足条件的花朵数。注意:这个整数有21位,它的各个位数字的21次方之和正好等于这个数本身。也就是21的水仙花数。希望解释下算法。枚举的方法有点没有理解,请高手详细解释下。


/**
 * 这是蓝桥杯java组往届中的一道题目,蓝桥杯官网上有详细的讲解
 * 主要是把问题转化为0~9出现次数和为21位数进行递归遍历和选择
 * 还有涉及大数据处理时候使用 BigInteger 类来处理。
 * 以下是根据官网上的讲解所写的代码,望对你有帮助
 */
import java.math.BigInteger;
public class Sxh {
    //初始化0~9的21次方
    static BigInteger []arr = new BigInteger[10];

    //判断21位数0~9出现次数是否和分配的次数一致
    public static boolean check(String str,int []jl)
    {
        int ar[] = {0,0,0,0,0,0,0,0,0,0};

        for(int i=0;i<21;i++)
            ar[str.charAt(i)-'0']++;
        for(int i=0;i<10;i++)
        {
            if(ar[i]!=jl[i])
                return false;
        }
        return true;
    }
    //times-->纪录当前分配数字   sy--剩余分配数      sum--当前总和   jl--纪录0~9每个数字分别占几次
    public static void bl(int times,int sy,BigInteger sum,int []jl){
        //若分配到数字9
        if(times==9)
        {
            sum = sum.add(arr[9].multiply(new BigInteger(String.valueOf(sy))));
            String str = sum.toString();
            //若当前和不为21位return
            if(str.length()!=21)
                return;
            jl[9] = sy;
            //若21位数0~9出现次数是否和分配的次数不一致,return
            if(!check(str,jl))
                return;
            //否则成立,输出结果
            System.out.println(str);
            return;
        }
        for(int i=0;i<=sy;i++)
        {
            jl[times]=i;
            BigInteger j = arr[times].multiply(new BigInteger(String.valueOf(i)));
            bl(times+1,sy-i,sum.add(j),jl);
        }
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //初始化0~9的21次方
        for(int i=0;i<10;i++)
            arr[i] = new BigInteger(String.valueOf(i)).pow(21);
        //初始化纪录0~9每次出现次数的数组
        int []jl = {0,0,0,0,0,0,0,0,0,0};
        bl(0,21,BigInteger.ZERO,jl);
    }
}

答案范围是闭区间 [0{21}, 9{21}] 的一个子集 枚举法就是遍历这个区间的整数,将符合结果的答案输出。

【热门文章】
【热门文章】