五位黑洞数 任意一个5位数，比如：34256，把它的各位数字打乱，重新排列，可以得到一个最大的数：65432，一个最小的数23456。 求这两个数字的差，得：41976，把这个数字再次重复上述过程（如果不足5位，则前边补0）。 如此往复，数字会落入某个循环圈（称为数字黑洞）。 比如，刚才的数字会落入：[82962,75933,63954,61974]这个循环圈。 请编写程序，找到5位数所有可能的循环圈，并输出，每个循环圈占1行。其中5位数全都相同则循环圈为 0，这个可以不考虑。 循环圈的输出格式仿照： [82962,75933,63954,61974]
最简单的思路是对所有五位数进行运算判断，若落入黑洞，则输出这个黑洞循环，当然还要判断这个黑洞之前是否已经输出。但是这并不是好的解决办法，有很多重复运算，效率较低，怎样降低时间开销呢，试想一下，如果一个数经过一系列运算不会落入黑洞的话，最终一定会得到0，那么所有计算得到的中间值也一定不会落入黑洞，因为他们计算后也会得到0，这些数就可以不必再次计算了，因此可以开一个VIS数组用来记录已经计算过的数，但还有一个问题，如何避免两次落入同一个黑洞，这里可以对VIS数组设置不同的值，第一次计算时所有中间值设为1，第二次计算时所有中间值为2
#include<iostream> #include<vector> #include<algorithm> using namespace std; int vis[100000]; int cha(int num)//计算差值 { int a[5]={0},i=0,max,min; while(num) { a[i++]=num; num=num/10; } sort(a,a+5); max=a[4]*10000+a[3]*1000+a[2]*100+a[1]*10+a[0]; min=a[0]*10000+a[1]*1000+a[2]*100+a[3]*10+a[4]; return max-min; } int main() { vector<int> s; vector<int>::iterator it; int number=0; for(int i=10000;i<100000;i++) if(!vis[i]) { s.clear(); s.push_back(i); int t=cha(i); vis[i]=number++; while(!vis[t]) { s.push_back(t); vis[t]=number; t=cha(t); } if(vis[t]==number&&t)//出现循环，输出该循环 { it=find(s.begin(),s.end(),t); cout<<'['<<*it; for(it=it+1;it!=s.end();it++) cout<<','<<*it; cout<<']'<<endl; } } return 0; } 。代码如下
