【藍橋杯】ADV-170 數字黑洞

2019 年 11 月 8 日
筆記

本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/89841277

題目描述：

任意一個四位數，只要它們各個位上的數字是不全相同的，就有這樣的規律： 1)將組成該四位數的四個數字由大到小排列，形成由這四個數字構成的最大的四位數； 2)將組成該四位數的四個數字由小到大排列，形成由這四個數字構成的最小的四位數(如果四個數中含有0，則得到的數不足四位)； 3)求兩個數的差，得到一個新的四位數(高位零保留)。重複以上過程，最後一定會得到的結果是6174。比如：4312 3087 8352 6174，經過三次變換，得到6174

輸入格式：

一個四位整數，輸入保證四位數字不全相同。

輸出格式：

一個整數，表示這個數字經過多少次變換能得到6174。

輸入樣例：

輸出樣例：

解題思路：

這道題跟【PAT乙級】數字黑洞和【PAT甲級】The Black Hole of Numbers類似。假設輸入的數字經過cnt次變換後能得到6174，先將輸入的那個四位整數拆成4個數字放入一個數組中，然後用這4個數字升序排列、降序排列分別組成最小的數字和最大的數字，用大數減去小數可以得到一個新的數字，如果新的數字是6174就輸出cnt即可。看了PAT的那倆題之後就會發現藍橋杯這題有個小小的疏漏：當輸入的數字各十百千位的數都是一樣的時候，是得不到6174的，比如2222。

AC程式碼：

#include <bits/stdc++.h>  using namespace std;    int arr2num(int a[])   //把數組中的數按照下標順序組成一個新的數字  {      int n = 0;      for(int i = 0; i < 4; i++)      {          n = n*10 + a[i];      }      return n;  }    int main()  {      int n;      cin >> n;      int a[4];      int cnt = 0;   //經過cnt次變換能得到6174      do{          for(int i = 0; i < 4; i++)   //把各位數存入數組裡面          {              a[i] = n%10;              n /= 10;          }          sort(a,a+4);   //升序排列          int x = arr2num(a);   //得到由數組a中元素組成的最大數字          sort(a,a+4,greater<int>());  //降序排列          int y = arr2num(a);  //得到由數組a中元素組成的最小數字          n = y-x;   //作差得到一個新的四位數          cnt++;      }while(n != 6174);      cout << cnt << endl;      return 0;  }