【算法分析与设计】数学黑洞

发布时间:2024年01月07日

?数学黑洞

引言

????????在数字的世界中,有一种神奇的现象被称为Kaprekar常数。Kaprekar常数是一个四位数,通过特定的运算步骤,无论你从哪个四位数开始,最终都会收敛到6174。这一奇妙的现象引发了人们对数学和算法的深刻思考。在本文中,我们将深入探讨Kaprekar算法,并通过Java代码实现这一数字黑洞的奇妙旅程。

Kaprekar算法简介

????????Kaprekar算法是由印度数学家D.R. Kaprekar于1949年提出的一种数学算法。该算法的基本思想是将一个四位数重新组合成最大和最小的两个数,然后计算它们的差,并将得到的结果作为新的四位数。重复这个过程,最终将会收敛到6174,然后无论怎么进行运算,都会得到6174。

题目:

1、数学黑洞(程序文件名)
【问题描述】
任给一个4位正整数,其各位数位上的数字不全相同,将数字重新组合成一个最大的数与最小的数相减,重复这个过程,最多7步,必得6174,

对任给的4位正整数(各位数位上的数字不全相同),编程输出掉进黑洞的步数。

【输入】一行,一个4位正整数n(1000<n<9999)

【输出】掉进黑洞的步数输入1234输出
?

题目分析流程:

  1. 输入处理:接受用户输入,获得一个4位正整数 n。

  2. 判断不全相同条件:确保输入的数字的各位数位上的数字不全相同。如果条件不满足,可能需要提示用户重新输入符合条件的数字。

  3. 进入循环:使用一个循环,直到数字变为6174为止,或者达到最大步数7。

  4. 数字拆分:将4位整数 n 拆分为各个位上的数字。可以将数字转为字符串,然后提取每一位的字符,或者直接进行数学运算获得千位、百位、十位和个位的数字。

  5. 数字排序:将拆分的数字进行排序,得到升序和降序的两个数字。

  6. 计算差值:计算降序数字减去升序数字的差值。

  7. 更新步数:步数加1。

  8. 更新数字:将差值作为新的数字,回到循环开始。

  9. 终止条件:当数字等于6174或者步数达到7时,退出循环。

其各位数位上的数字不全相同,是1113满足条件,1111不满足条件

?算法思路:

  1. 将输入的整数转换成字符串,再将字符串转换为字符数组,以便后续排序操作。
  2. 使用 Arrays.sort() 对字符数组进行升序排序,然后通过 Integer.parseInt() 转换为整数,得到升序排列的整数 min
  3. 使用 StringBuilder 反转字符数组,再转换为整数,得到降序排列的整数 max
  4. 计算新的数值 num,即 max - min
  5. 重复上述步骤,直到 num 等于 Kaprekar 常数(6174)为止,计算步骤数。

算法实现:

(第一版)
package algorithm;

import java.util.Arrays;

public class TopicSecond {
    public static void main(String[] args) {
        System.out.println(getResult(2148));
    }
    public static Integer getResult(Integer num){

        int steps = 0;
        while (num != 6174) {
            //将num转化为字符串
            String numStr =num+"";
            //将字符串变换为字符数组
            char[] digits = numStr.toCharArray();
            //数组工具类排序
            Arrays.sort(digits);
            //之后利用构造函数转为字符串
            String str=new String(digits);
            //利用可变字符串,主要是为了反转字符串方便有API
            StringBuilder builder=new StringBuilder(str);
            int min = Integer.parseInt(str);
            Arrays.sort(digits);
            int max = Integer.parseInt(builder.reverse().toString());
            num = max - min;
            steps++;
        }
        return steps;

    }
}

????????无法处理9998等数据,因为9998-8999=999,而这样就导致了这个数字无法到达四位数,不满足在变换过程中不符合题目了。

????????所以需要在变换过程中不足四位要进行补全

?(第二版)代码修正

String numStr =String.format("%04d",num);

"%04d" 是一个格式化字符串的格式,表示将整数格式化为至少4位,不足的地方用零进行填充。

例如,如果 num 是 123,String.format("%04d", num) 将返回字符串 "0123"。

package algorithm;

import java.util.Arrays;

public class TopicSecond {
    public static void main(String[] args) {
//        for(int i=1000;i<10000;i++){
//            if(i%1111==0)
//                continue;
//            System.out.println(getResult(i));
//        }
        System.out.println(getResult(9998));

    }
    public static Integer getResult(Integer num){

        int steps = 0;
        while (num != 6174) {
            //将num转化为字符串 
            String numStr =String.format("%04d",num);
            //将字符串变换为字符数组
            char[] digits = numStr.toCharArray();
            //数组工具类排序
            Arrays.sort(digits);
            //之后利用构造函数转为字符串
            String str=new String(digits);
            //利用可变字符串,主要是为了反转字符串方便有API
            StringBuilder builder=new StringBuilder(str);

            int min = Integer.parseInt(str);
            Arrays.sort(digits);

            int max = Integer.parseInt(builder.reverse().toString());
            num = max - min;

            steps++;
        }
        return steps;

    }
}

?

经过遍历可以找到所有的结果,我随机找了一部分,事实证明,是真的。

文章来源:https://blog.csdn.net/m0_62645012/article/details/135433570
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。