2019-02-27-PAT乙级-1019-数字黑洞

编程描述

给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的 6174 ，这个神奇的数字也叫 Kaprekar 常数。

例如，我们从 6767 开始，将得到

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...

现给定任意 4 位正整数，请编写程序演示到达黑洞的过程。

辅助描述

作者: CHEN, Yue
单位: 浙江大学
时间限制: 200 ms
内存限制: 64 MB
代码长度限制: 16 KB

输入格式

输入给出一个 (0, $10^{4}$ ) 区间内的正整数 N。

输出格式

如果 N 的 4 位数字全相等，则在一行内输出 N - N = 0000 ；否则将计算的每一步在一行内输出，直到 6174 作为差出现，输出格式见样例。注意每个数字按 4 位数格式输出。

输入样例1

输出样例1

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174

输入样例2

输出样例2

1	2222 - 2222 = 0000

算法实现

JAVA(openjdk)

代码


import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int ans = ds(x) - xs(x);
        if (ans == 0) {
            System.out.printf("%04d - %04d = %04d\n", ds(x), xs(x), ans);
        } else {
            int n;
            do {
                n = ds(x) - xs(x);
                System.out.printf("%04d - %04d = %04d\n", ds(x), xs(x), n);
                x = n;
            } while (n != 6174);
        }
    }

    public static int ds(int x) {
        int[] a = new int[4];
        a[0] = x / 1000;
        a[1] = x / 100 % 10;
        a[2] = x / 10 % 10;
        a[3] = x % 10;
        Arrays.sort(a);
        int sum = a[3] * 1000 + a[2] * 100 + a[1] * 10 + a[0];
        return sum;
    }

    public static int xs(int x) {
        int[] a = new int[4];
        a[0] = x / 1000;
        a[1] = x / 100 % 10;
        a[2] = x / 10 % 10;
        a[3] = x % 10;
        Arrays.sort(a);
        int sum = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
        return sum;
    }
}

运行结果

状态	分数	题目	编译器	耗时	用户	
答案正确	20	1019	Java (openjdk)	158 ms	HibisciDai
测试点	结果	耗时	内存
0	答案正确	120 ms	11820 KB
1	答案正确	158 ms	11472 KB
2	答案正确	131 ms	11508 KB
3	答案正确	138 ms	11512 KB
4	答案正确	126 ms	11688 KB
5	答案正确	126 ms	11544 KB
6	答案正确	126 ms	11400 KB

备注

java输出格式

1	System.out.printf("%04d - %04d = %04d\n", ds(x), xs(x), ans);

格式控制字符	结果
%d	整数
%8d	整数，右对齐，输出宽度为8
-6%	整数，左对齐，输出宽度为6
%f	浮点数
%8f	浮点数，右对齐，输出宽度为8
%.2f	浮点数，精确到百分位
%16.3f	浮点数，精确到千分位，输出宽度为16

String字符串类似，替换 s

Java 字符串格式化详解

width 是可选参数，用于控制输出的宽度。

示例：

1	System.out.println(String.format("设置最小宽度为8，不满8位用0填充：%08d:%08d", 1, -10000000));

输出：

1	设置最小宽度为8，不满8位用0填充：00000001:-10000000