《算法競賽入門經典》5.3排序與檢索，算法競賽入門經典
1 /*
2 *假設你有一個各位數字互不相同的四位數，把所有數字從大到小排序後得到a，從小到大排序後得到b，然後用a-b替換原來這個數，並且繼續操作。
3 *假如，從1234出發，依次可以得到4321-1234=3087、8730-378=8352、8532-2358=6174。有趣的是，7641-1467=6174，回到了它自己。
4 *輸入一個n位數，輸出操作序列，直到出現循環（即新得到的數曾經得到過）。輸入保證在循環之前最多只會產生1000個整數。
5 *樣例輸入：1234
6 *樣例輸出：1234->3087->8352->6174->6174
7 */
8
9 #include <stdio.h>
10 #include <string.h>
11 int num[2000], count;
12
13 int get_next(int x)
14 {
15 int a, b, n;
16 char s[10];
17 //轉化成字符串
18 sprintf(s, "%d", x); //用法見隨筆<常用函數>
19 n = strlen(s); //string.h
20 //冒泡排序
21 for(int i= 0; i < n; i++) //臨時定義變量，不屬於ANSI C，建議擴展名保存為.cpp；
22 for(int j = i+1; j < n; j++)
23 if(s[i] > s[j])
24 {
25 char t = s[i]; s[i] = s[j]; s[j] = t;
26 }
27 sscanf(s, "%d", &b); //用法見隨筆<常用函數>
28 //字符串反轉
29 for(int i = 0; i < n/2; i++)
30 {
31 char t = s[i]; s[i] = s[n-1-i]; s[n-1-i] = t;
32 }
33 sscanf(s, "%d", &a);
34 return a - b;
35 }
36
37 int main()
38 {
39 scanf("%d", &num[0]);
40 printf("%d", num[0]);
41 count = 1;
42 for(; ; )
43 {
44 //生成並輸出下一個數
45 num[count] = get_next(num[count-1]);
46 printf(" -> %d", num[count]);
47 //在數組num中尋找新生成的數
48 int found = 0;
49 for(int i = 0; i < count; i++)
50 if(num[i] == num[count]) {found = 1; break;}
51 //如果找到，則退出循環
52 if(found) break;
53 count++;
54 }
55 printf("\n");
56 return 0;
57 }
58 /*分析：
59 *第一步：使用“冒泡排序”的方法對各個數字排序，編寫get_next函數得到下一個數；
60 *第二步：逐個生成各個數，並判斷是否曾經出現過，常用的方法是用數組。
61 */
