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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注