E-tutor [程式設計][C_CH10-中] The 3n + 1 problem
簡介
題目來源：e-tutor平台
[C_CH10-中] The 3n + 1 problem
The 3n+1 proble，看到題目時，第一個想法就是這題怎麼那麼佛心，題目的演算法直接給，只剩下直接幫題目所需轉成程式碼，結果仔細一看才發現案情並不單純，這題需要使用到多個判斷式與迴圈。
讓我們先了解題目內容
問題描述：
考慮以下演算法：
1.輸入 n
2.印出 n
3.如果 n = 1 結束
4.如果 n 是奇數，那麼 n = 3 * n + 1
5.否則 n = n / 2
6. GOTO 2
例如輸入 22，得到的數列：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
據推測此演算法對任何整數而言會終止 ( 當列印出 1 的時候 )。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的 n ( 0 < n < 1,000,000 ) 來說，以上的推測已經被驗證是正確的。
給一個輸入 n，透過以上的演算法我們可以得到一個數列 ( 1 作為結尾 )。此數列的長度稱為 n 的 cycle-length。上面提到的例子，22 的 cycle-length 為 16。
問題來了，對任 2 個整數 i、j，我們想要知道介於 i、j ( 包含 i、j ) 之間的數所產生的數列中最大的 cycle-length 是多少。
Input：
輸入可能包含了好幾列測試資料，每一列有一對整數資料 i、j。0 < i，j < 1,000,000。
Output：
對每一對輸入 i、j 你應該要輸出 i、j 和介於 i、j 之間的數所產生的數列中最大的 cycle-length。
範例：
解題想法：
1.先判斷輸入的兩個數字大小，才能得知迴圈起始與終點該用哪個數字
2.設定輸入兩個數字的範圍迴圈
3.範圍內的數字都要經過一個計算 cycle-length 的無窮迴圈
4.無窮迴圈內設定題目提供演算法
5.把每個數字的 cycle-length 儲存到一個陣列
6.尋找陣列最大元素並輸出
第一步、依題目要求輸入
1.題目要求輸入 2 個數字，分別宣告為 first 和 second
2.宣告 begin 和 end，用來判斷 first 與 second
3.使用 vecctor 功能宣告一個 all_cycle_lendth 陣列，用來儲存所有數的 cycle-length
4.輸入 first 和 second
第二步、判斷 first 和 second 的大小
如果 first 大於等於 second
則 begin 為 second，end 為 first
否則
則 begin 為 first，end 為 second
為什麼要判斷 first 和 second 的大小?
測試資料給的兩個數沒有固定是第一個數字大，或第二個數字大
為了要設定迴圈起始與終點所以要先判斷
使用二筆測試資料 10 和 1 與 1 和 10
以下程式碼當例子
若不先分辨大小的話就會出問題
除非把兩種可能分開寫，把 i + + 部分改成 i - -
但還是要判斷大小
第三步、設定題目所給的範圍迴圈與宣告演算法所需的變數
經過第二步的判斷後
分辨出哪個數為 begin 與 end
分別把 begin 與 end 放入迴圈內
宣告整數 number
number 為記錄現在演算法是在計算哪個數的 cycle-length
宣告整數 cycle_length，紀錄數字的 cycle-length
經過演算法後
在迴圈的最後把算出的 cycle-length 放進 all_cycle_length 陣列裡
第四步、設定無限迴圈與演算法規則
為什麼要設定無限迴圈？
每個數的 cycle-length 不盡相同
不一定會只經過題目所提供的演算法一次
也無法預測這個數字會再演算法裡徘徊幾次
因此設定無限迴圈讓它不斷執行
直到遇到設定終止條件再跳出
題目所提供的演算法有三種可能
1.如果 number = 1
則跳出迴圈
1 也算是 cycle-length
請記得在跳出迴圈前把 cycle_length + 1
2.奇數，如果 number 除以 2 取餘數不等於 0，且不能為 1
則 number 乘 3 加 1
數字的 cycle-length + 1
3.偶數，除了以上兩種判斷外的所有可能
則 number 除以 2
數字的 cycle-length + 1
做完以上步驟就已經把所有範圍內數字的 cycle-length 算出來了
剩下找出最大的 cycle-length
第五步、找出最大的 cycle-length 並輸出
因為還不知道 all_cycle_length 陣列內哪個元素大哪個元素小
因此先宣告整數 Bigcl 等於陣列中的第一個元素
設定一個以 all_cycle_length 陣列元素數量為限制的迴圈
迴圈每跑一次
如果陣列中有元素大於等於 Bigcl，則取代掉它
最後等迴圈跑完
在迴圈外輸出題目一開始所給的兩個數與 Bigcl 就完成了
記得每個數字間要穿插一個空白
完整程式碼如下
題目來源：e-tutor平台
[C_CH10-中] The 3n + 1 problem
The 3n+1 proble，看到題目時，第一個想法就是這題怎麼那麼佛心，題目的演算法直接給，只剩下直接幫題目所需轉成程式碼，結果仔細一看才發現案情並不單純，這題需要使用到多個判斷式與迴圈。
讓我們先了解題目內容
問題描述：
考慮以下演算法：
1.輸入 n
2.印出 n
3.如果 n = 1 結束
4.如果 n 是奇數，那麼 n = 3 * n + 1
5.否則 n = n / 2
6. GOTO 2
例如輸入 22，得到的數列：22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
據推測此演算法對任何整數而言會終止 ( 當列印出 1 的時候 )。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的 n ( 0 < n < 1,000,000 ) 來說，以上的推測已經被驗證是正確的。
給一個輸入 n，透過以上的演算法我們可以得到一個數列 ( 1 作為結尾 )。此數列的長度稱為 n 的 cycle-length。上面提到的例子，22 的 cycle-length 為 16。
問題來了，對任 2 個整數 i、j，我們想要知道介於 i、j ( 包含 i、j ) 之間的數所產生的數列中最大的 cycle-length 是多少。
Input：
輸入可能包含了好幾列測試資料，每一列有一對整數資料 i、j。0 < i，j < 1,000,000。
Output：
對每一對輸入 i、j 你應該要輸出 i、j 和介於 i、j 之間的數所產生的數列中最大的 cycle-length。
範例：
解題想法：
1.先判斷輸入的兩個數字大小，才能得知迴圈起始與終點該用哪個數字
2.設定輸入兩個數字的範圍迴圈
3.範圍內的數字都要經過一個計算 cycle-length 的無窮迴圈
4.無窮迴圈內設定題目提供演算法
5.把每個數字的 cycle-length 儲存到一個陣列
6.尋找陣列最大元素並輸出
第一步、依題目要求輸入
1.題目要求輸入 2 個數字，分別宣告為 first 和 second
2.宣告 begin 和 end，用來判斷 first 與 second
3.使用 vecctor 功能宣告一個 all_cycle_lendth 陣列，用來儲存所有數的 cycle-length
4.輸入 first 和 second
第二步、判斷 first 和 second 的大小
如果 first 大於等於 second
則 begin 為 second，end 為 first
否則
則 begin 為 first，end 為 second
為什麼要判斷 first 和 second 的大小?
測試資料給的兩個數沒有固定是第一個數字大，或第二個數字大
為了要設定迴圈起始與終點所以要先判斷
使用二筆測試資料 10 和 1 與 1 和 10
以下程式碼當例子
若不先分辨大小的話就會出問題
除非把兩種可能分開寫，把 i + + 部分改成 i - -
但還是要判斷大小
第三步、設定題目所給的範圍迴圈與宣告演算法所需的變數
經過第二步的判斷後
分辨出哪個數為 begin 與 end
分別把 begin 與 end 放入迴圈內
宣告整數 number
number 為記錄現在演算法是在計算哪個數的 cycle-length
宣告整數 cycle_length，紀錄數字的 cycle-length
經過演算法後
在迴圈的最後把算出的 cycle-length 放進 all_cycle_length 陣列裡
第四步、設定無限迴圈與演算法規則
為什麼要設定無限迴圈？
每個數的 cycle-length 不盡相同
不一定會只經過題目所提供的演算法一次
也無法預測這個數字會再演算法裡徘徊幾次
因此設定無限迴圈讓它不斷執行
直到遇到設定終止條件再跳出
題目所提供的演算法有三種可能
1.如果 number = 1
則跳出迴圈
1 也算是 cycle-length
請記得在跳出迴圈前把 cycle_length + 1
2.奇數，如果 number 除以 2 取餘數不等於 0，且不能為 1
則 number 乘 3 加 1
數字的 cycle-length + 1
3.偶數，除了以上兩種判斷外的所有可能
則 number 除以 2
數字的 cycle-length + 1
做完以上步驟就已經把所有範圍內數字的 cycle-length 算出來了
剩下找出最大的 cycle-length
第五步、找出最大的 cycle-length 並輸出
因為還不知道 all_cycle_length 陣列內哪個元素大哪個元素小
因此先宣告整數 Bigcl 等於陣列中的第一個元素
設定一個以 all_cycle_length 陣列元素數量為限制的迴圈
迴圈每跑一次
如果陣列中有元素大於等於 Bigcl，則取代掉它
最後等迴圈跑完
在迴圈外輸出題目一開始所給的兩個數與 Bigcl 就完成了
記得每個數字間要穿插一個空白
完整程式碼如下
留言
張貼留言