卡拉茲(Callatz)猜想已經在1001中給出了描述。在這個題目里，情況稍微有些複雜。 當我們驗證卡拉茲猜想的時候，為了避免重覆計算，可以記錄下遞推過程中遇到的每一個數。例如對 n=3 進行驗證的時候，我們需要計算 3、5、8、4、2、1，則當我們對 n=5、8、4、2 進行驗證的時候，就可以直接 ...
卡拉茲(Callatz)猜想已經在1001中給出了描述。在這個題目里，情況稍微有些複雜。
當我們驗證卡拉茲猜想的時候，為了避免重覆計算，可以記錄下遞推過程中遇到的每一個數。例如對 n=3 進行驗證的時候，我們需要計算 3、5、8、4、2、1，則當我們對 n=5、8、4、2 進行驗證的時候，就可以直接判定卡拉茲猜想的真偽，而不需要重覆計算，因為這 4 個數已經在驗證3的時候遇到過了，我們稱 5、8、4、2 是被 3“覆蓋”的數。我們稱一個數列中的某個數 n 為“關鍵數”，如果 n 不能被數列中的其他數字所覆蓋。
現在給定一系列待驗證的數字，我們只需要驗證其中的幾個關鍵數，就可以不必再重覆驗證餘下的數字。你的任務就是找出這些關鍵數字，並按從大到小的順序輸出它們。
輸入格式：
每個測試輸入包含 1 個測試用例，第 1 行給出一個正整數 K (<100)，第 2 行給出 K 個互不相同的待驗證的正整數 n (1<n≤100)的值，數字間用空格隔開。
輸出格式：
每個測試用例的輸出占一行，按從大到小的順序輸出關鍵數字。數字間用 1 個空格隔開，但一行中最後一個數字後沒有空格。
輸入樣例：
6
3 5 6 7 8 11
輸出樣例：
7 6
思路：用-1初始化數組，用0標記輸入的值，再遍歷找出每一個輸入的值通過卡拉茲(Callatz)猜想用1標記變化過程中出現的值，將一些輸入的值的標記0覆蓋，最後剩下的0為正解
1 #include<stdio.h>
2 #include<math.h>
3 #include<string.h>
4 #include<stdlib.h>
5 int main()
6 {
7 int mark[10000];//註意防止數組越界
8 memset(mark,-1,sizeof(mark));//memset初始化為-1
9 int N;
10 scanf("%d",&N);
11 int num;
12 while(N--)
13 {
14 scanf("%d",&num);
15 mark[num]=0;//輸入過的值標記為0
16 }
17 int temp;
18 for(int i=1;i<101;i++)
19 {
20 if(mark[i]==0)
21 {
22 temp=i;
23 while(temp!=1)
24 {
25 if(temp%2==1)
26 {
27 temp=(3*temp+1)/2;
28 mark[temp]=1;//變化過程中出現的所有值標記為1
29 }
30 else if(temp%2==0)
31 {
32 temp=temp/2;
33 mark[temp]=1;
34 }
35 }
36 }
37 }
38 int T=0;
39 int out[101];
40 for(int i=100;i>0;i--)
41 {
42 if(mark[i]==0)//未被1覆蓋的0，其i為正解
43 out[T++]=i;
44 }
45 for(int i=0;i<T-1;i++)
46 printf("%d ",out[i]);
47 printf("%d\n",out[T-1]);
48 return 0;
49 }
