[TOC] ### 題目描述 1005. 繼續(3n+1)猜想 (25) 卡拉茲(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 ### 分析（偽代碼和知識點） ### 代碼 ``` #include<stdio.h> int main() { int k,i; int key[101]={0}; int number[1000]={0}; /* 用key數組記錄0-100是否被其他數覆蓋，用number數組記錄用戶輸入的數字。 初始化key數組為0，用戶輸入過的所有序號置為1，完成猜想過程中出現過得數組序號置為0，最后key中為1的元素的編號及為未被覆蓋的元素*/ scanf("%d",&k); if(k<100) { for(i=0;i<k;i++) { scanf("%d",&number[i]); if(number[i]>1&&number[i]<=100) { key[number[i]]=1; } } for(i=0;i<k;i++) { int n; n=number[i]; while(n!=1) { if(n%2) { n=(3*n+1)/2; if(n<=100){ key[n]=0; } /*這里n可能會超過100，造成數組越界，這邊要加一個判斷*/ }else { n/=2; if(n<=100){ key[n]=0; } } } } int cnt=0; for(i=101;i>0;i--) { if(key[i]==1) { if(cnt>0){ printf(" "); } printf("%d",i); cnt++; } } } return 0; } ```