PTA 初级1019数字黑洞 & 测试点解析

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

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

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

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

输入格式：

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

输出格式：

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

输入样例 1：

6767

输出样例 1：

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

输入样例 2：

2222

输出样例 2：

2222 - 2222 = 0000

 

这道题的话，一共8个测试点，有六个是比较平常的，有两个是比较特殊的。

第一个测试点是输入的N四个数字都相同，

第三个测试点，在计算的时候可能会出现多个0 或者在接受输入的时候是0001 的这种形式。存为int N时会将其存为。

下面介绍我用到的函数。

 

 第一个是倒序的函数：

int Reverse(int x)
{
    int m=0;
    while (x!=0) {
        m=m*10+x%10;
        x=x/10;
    }
    return m;
}

第二个是按从大到小排的函数：第一部分将其导入数组，然后排序。

int Queue(int N)
{
    
    int a[5]={0};
    for (int i=0;i<4;i++)
    {
        a[i]=N%10;
        N=N/10;
    }
    
    for (int i=0;i<4;i++)
    {
        for (int j=i+1;j<4;j++)
        {
            if ( a[j]>a[i] )
            {
                int t=a[j];
                a[j]=a[i];
                a[i]=t;
            }
        }
    }
    N=0;
    for (int i=0;i<4;i++)
        N=10*N+a[i];
    
    return N;
}

第三个是计算位数的函数，比如原来是8900，排队候就是9800，倒序后就是0089，不过是89而不是0089，但是在输出的时候还是要输出0。

int Weishu(int x)
{
    int i=0;
    while (x!=0) {
        x=x/10;
        i++;
    }
    return i;
}

最后是主函数。在主函数里，第一个if语句是为了将0001的这种形式存为1000.

第二个if是为了第一个测试点。

需要注意的是，如果输入是0001，则第一行的输出应该是1000 - 0001 = 0999，就是说999前面也需要有个0。

int main(int argc, const char * argv[]) {
    
    int N;
    cin >> N;
    
    if (Weishu(N)==1)
        N=1000*N;
    
    if (N==Reverse(N))
    {
        cout << N << " - " << N << " = " << "0000" <<endl;
        exit(0);
    }
    
    N=Queue(N);
    
    int i=0,t;
    while (i!=6174)
    {
        t=Reverse(N);
        i=N-t;
        cout << N <<" - ";
        for (int j=0;j<4-Weishu(t);j++ )
            cout << "0" ;
        cout << Reverse(N) << " = ";
        for (int j=0;j<4-Weishu(i);j++ )
            cout << "0" ;
        cout << i <<endl;
        
        N=Queue(i);
        if (N==Reverse(N))
        {
            cout << N << " - " << N << "=" << "0000" <<endl;
            exit(0);
        }
        
    }
}