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;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。