5位黑洞数

5位黑洞数

时间： 1ms        内存：128M

描述：

任意一个5位数，比如：34256，把它的各位数字打乱，重新排列，可以得到一个最大的数：65432，一个最小的数23456。求这两个数字的差，得：41976，把这个数字再次重复上述过程（如果不足5位，则前边补0）。如此往复，数字会落入某个循环圈（称为数字黑洞）。
比如，刚才的数字会落入：[82962, 75933, 63954, 61974] 这个循环圈。

输入：

输出：

请编写程序，找到5位数所有可能的循环圈，并输出，每个循环圈占1行。其中5位数全都相同则循环圈为 [0]，这个可以不考虑。

其中数字的先后顺序可以不考虑。

示例输入：

示例输出：

[82962, 75933, 63954, 61974]

提示：

参考答案（内存最优[1120]）：

#include<stdio.h>
int main()
{
    printf("[74943, 62964, 71973, 83952]\n[63954, 61974, 82962, 75933]\n[53955, 59994]");
}

参考答案（时间最优[0]）：

#include<bits/stdc++.h>
using  namespace std;
#define maxn 100005
int use[maxn],vis[maxn];
bool ju(int x){
    if(x%10!=x/10%10)return 0;
    if(x%10!=x/100%10)return 0;
    if(x%10!=x/1000%10)return 0;
    if(x%10!=x/10000)return 0;
    return 1;
}
void doit(int x){
    int a[6],b[6],c[6];
    queue<int>q;
    while(1){
        a[1]=x/10000;
        a[2]=x/1000%10;
        a[3]=x/100%10;
        a[4]=x/10%10;
        a[5]=x%10;
        sort(a+1,a+1+5);
        int i,j;
        for(i=1,j=5;i<=5;++i,--j)b[i]=a[j];
        int minn=a[1]*10000+a[2]*1000+a[3]*100+a[4]*10+a[5];
        int maxx=b[1]*10000+b[2]*1000+b[3]*100+b[4]*10+b[5];
        x=maxx-minn;
        if(use[x])break;
        if(vis[x]){
            while(q.front()!=x)q.pop();
            cout<<"[";
            i=1;
            while(!q.empty()){
                if(i!=1){cout<<", ";}
                int x=q.front();
                use[x]=1;
                cout<<x;
                q.pop();
                i++;
            }
            cout<<"]\12";
        }
        else {
            vis[x]=1;
            q.push(x);
        }
    }
}
int main(){
    /*memset(use,0,sizeof(use));
    for(int i=10000;i<100000;++i){
        if(ju(i))continue;
        memset(vis,0,sizeof(vis));
        doit(i);
    }*/
    printf("[74943, 62964, 71973, 83952]\n[63954, 61974, 82962, 75933]\n[53955, 59994]\n");
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。