PAT 甲级 1069 The Black Hole of Numbers (20 分)

题目描述

For any 4-digit integer except the ones with all the digits being the same, if we sort the digits in non-increasing order first, and then in non-decreasing order, a new number can be obtained by taking the second number from the first one. Repeat in this manner we will soon end up at the number 6174 – the black hole of 4-digit numbers. This number is named Kaprekar Constant.
For example, start from 6767, we’ll get:
7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
… …
Given any 4-digit number, you are supposed to illustrate the way it gets into the black hole.

输入

Each input file contains one test case which gives a positive integer N in the range $(0,10^4)$.

输出

If all the 4 digits of N are the same, print in one line the equation N - N = 0000. Else print each step of calculation in a line until 6174 comes out as the difference. All the numbers must be printed as 4-digit numbers.

思路

照着遍历就行

代码

#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int big[10];
int small[10];
int ans[10] = { 0 };
int before[10];
bool cmp(int a, int b)
{
	return a > b;
}
int pan()
{
	for (int i = 0; i < 4; i++)
	{
		if (before[i] != ans[i])
		{
			return 1;
		}
	}
	return 0;
}
void print()
{
	for (int i = 0; i < 4; i++)
	{
		printf("%d", big[i]);
	}
	printf(" - ");
	for (int i = 0; i < 4; i++)
	{
		printf("%d", small[i]);
	}
	printf(" = ");
	for (int i = 0; i < 4; i++)
	{
		printf("%d", ans[i]);
	}
	printf("\n");
}
int main()
{
	char str[10] = { 0 };
	cin.getline(str, 10);
	for (int i = 0; i < 4; i++)
	{
		before[i] = -1;
	}
	if (strlen(str) == 4)
		for (int i = 0; str[i] != 0; i++)
		{
			ans[i] = str[i] - '0';
		}
	else
	{
		int cha = 4 - strlen(str);
		for (int i = cha; i < 4; i++)
		{
			ans[i] = str[i - cha] - '0';
		}

	}
	int temp = 0;
	for (int i = 0; i < 4; i++)
	{
		temp += ans[i];
	}
	if (temp == 0)
	{
		print();
		return 0;
	}
	while (1)
	{
		for (int i = 0; i < 4; i++)
		{
			big[i] = ans[i];
			small[i] = ans[i];
		}
		sort(big, big + 4, cmp);
		sort(small, small + 4);
		for (int i = 0; i < 4; i++)
		{
			ans[i] = 0;
		}
		for (int i = 3; i >= 0; i--)
		{
			ans[i] = big[i] - small[i] + ans[i];
			if (ans[i] < 0)
			{
				ans[i - 1]--;
				ans[i] += 10;
			}
		}
		if (pan())
		{
			print();
		}
		else
		{
			break;
		}
		for (int i = 0; i < 4; i++)
		{
			before[i] = ans[i];
		}
	}
}