SPOJ - "TEST - Life, the Universe, and Everything"

TEST - Life, the Universe, and Everything

題目敘述：

Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely... rewrite small numbers from input to output. Stop processing input after reading in the number 42. All numbers at input are integers of one or two digits.

題目解析：

前面幾句都是廢話可以忽略，但其中 brute-force 有蠻力硬解的意思，就是在意指說這個題目的實作沒有限制執行時間，解題方向會比較廣；輸入數字串( 沒有指名長度，即沒有限制 )，並在輸入完成( 注意如何判定輸入完成 )後依序( FIFO )印出直到處理到「42」。所有輸入數字皆為整數並只有一到兩位數。

作為 Classical 類別裡面的第一題，難度設置很低，但也隱性讓有研修過資工領域資料結構的程式猿們去練習或是實作 queue 類別的意思，算是個很有靈性的入門暖身題。

練習重點：queue使用、理解其概念 或 自行實作。

開始實做：

選用語言為C++，編譯環境為Code::Blocks 17.12。

我們做的點有兩點：

1. 連續輸入數字儲存，後判定輸入結束

2. 依序印出，遇到「42」停止輸出

以下開始實作：

1. 通常連續輸入後中斷，有許多實作的方法，其中while(getline(cin,a))後偵測是否為空字串是作者偏好的方法。下為簡單的實作：



SPOJ的題目在沒有要求的情況下，是不需用寫防呆機制的，系統預設好的輸入默認就是在規則內，不會有預期外的輸入情況，但時間允許的話還是要有考慮一切東西進去的好習慣，所以：



已經有判定輸入情況結束程式運行( 空輸入 )，也有簡陋的防呆機制，那我們就可以進行下一步了......接著處理：要如何有效儲存輸入的數字並依照「先進先出FIFO」概念輸出，直到遇到「42」為止。

本步驟參考連結：

输入与输出(cout和cin的用法)--C++ ( 包含了許多除了cout和cin的用法 )

getline error ( cin後使用getline的緩存區錯誤方面更細的探討 )

2. 要實作出可以容納題目所需的數字串列有幾個選項：

a. 就用最基礎的方法，指派固定容量的記憶體，容量的初始值設定大一點，500左右，可以在一定程度上避免空間不夠的窘境，但因為「SPOJ」沒有提供隱藏測資，如果超出就會爆炸，建議不要使用。

b. #include<queue> 使用現有函式庫，直接解決動態容量的記憶體分配問題。

c. 嘗試自己實作 queue，運用指標的鏈結概念，此為資料結構的基礎入門題。

為了方便實作先選用b.，因為是現有的函式庫，先行了解其使用方式即可。在這次程式會用到 push() 將資料壓入佇列中、front() 提取佇列( queue )前端資料、pop() 將資料前端資料推出、size() 確認佇列大小。

Cplusplus.com「queue」

以下為最後實作結果，結合了前面的簡單程式，並多了放入 queue 後運用的過程，也確實在遇到 42 以後結束程式運行。