題目: 對任何一個正整數 n，如果它是偶數，那麼把它砍掉一半；如果它是奇數，那麼把 (3n+1) 砍掉一半。 當我們驗證卡拉茲猜想的時候，為了避免重覆計算，可以記錄下遞推過程中遇到的每一個數。例如對 n=3 進行驗證的時候，我們需要計算 3、5、8、4、2、1，則當我們對 n=5、8、4、2 進行驗 ...
題目:
對任何一個正整數 n，如果它是偶數，那麼把它砍掉一半；如果它是奇數，那麼把 (3n+1) 砍掉一半。
當我們驗證卡拉茲猜想的時候，為了避免重覆計算，可以記錄下遞推過程中遇到的每一個數。例如對 n=3 進行驗證的時候，我們需要計算 3、5、8、4、2、1，則當我們對 n=5、8、4、2 進行驗證的時候，就可以直接判定卡拉茲猜想的真偽，而不需要重覆計算，因為這 4 個數已經在驗證3的時候遇到過了，我們稱 5、8、4、2 是被 3“覆蓋”的數。我們稱一個數列中的某個數 n 為“關鍵數”，如果 n 不能被數列中的其他數字所覆蓋。
現在給定一系列待驗證的數字，我們只需要驗證其中的幾個關鍵數，就可以不必再重覆驗證餘下的數字。你的任務就是找出這些關鍵數字，並按從大到小的順序輸出它們。
思路:
一開始是沒有清晰的思路的,在紙上做下草稿,發現關鍵的點在於如何判定覆蓋以及判定覆蓋後怎樣進行處理?那就用一個很笨的辦法
1.設定一個數組用來存放每個數驗證時所需計算的數字,然後將其和已知數列一一比較
2.比較過後將原數列中被覆蓋的數置零,從這點又引申出來的想法是在第一層迴圈中加入if判定是否為零,若為零可直接跳過比較,這樣也省去了不必要的步驟
遞推過程函數較為簡單,傳入n(給定數列的個數),比較數組(copy[]),返回值為int,即遞推過程中的數的個數
int callatz(int n,int copy[]){ int i = 0; do{ if(n%2==0) n = n/2; else n = (n*3+1)/2; copy[i++] = n; }while (n!=1); i = i-1; return i; }
主函數,題目要求是將結果從大到小順序輸出,那首先要把它們找出來放到數組裡,用迴圈來搞定
int n; (void)scanf("%d",&n); int str[n];//存放已知數列 int copy[SIZE];//存放遞推過程里的數 for(int i = 0;i < n;i++){ (void)scanf("%d",&str[i]); } for(int y = 0;y < n;y++){ if(str[y]!=0){//判定是否為零,為零說明該數已被覆蓋 int size = callatz(str[y], copy);//遞推過程中數的個數 //開始和已知數列比較,同時更新已知數列 for(int i = 0;i < size;i++){ for(int z = 0;z < n;z++){ if(str[z]==copy[i]) str[z] = 0; } } } }
然後定義一個新數組存放結果,進行排序然後輸出
int z = 0; int new[n]; for(int i = 0;i < n;i++){ if(str[i]!=0) new[z++] =str[i]; } //排序 最簡單的選擇排序.... int min = 0,temp; for(int i = 0;i < z-1;i++){ temp = i; for(int j = i+1;j <z;j++){ if(new[j] > new[temp]){ temp = j; } } min = new[i]; new[i] = new[temp]; new[temp] = min; } int i = 0; for(i = 0;i < z-1;i++){ printf("%d ",new[i]); } printf("%d",new[z-1]); printf("\n");//輸出格式的要求
因為排序出了錯而報錯了,要重新好好研究一下排序了...基本功太汗顏了
