Wei-Zhong Program design notes

簡介 題目來源：e-tutor平台 [C_AR182-中] 翻轉吧陣列 翻轉吧陣列，先儲存資料後，經題目的命令，做出三種不同的二維陣列翻轉，做完這題可以使我們對陣列更加的了解 讓我們先了解題目內容 問題描述： 假設一個 N * N 的陣列 ( N <= 20 )，每個位置從左到右，從上到下，依序填入 1 ~ N ²  的數字，假設 N = 4，陣列的初始狀態如圖所示。接著，這裡有三種翻轉動作，分別是水平、垂直與對角翻轉，從初始狀態分別進行這三種翻轉動作後對應的結果分別如圖所示：   請撰寫一個程式，可以先讀取一個正整數 N，接著讀入一串由 H V D 所組成的翻轉字串，接著輸出初始狀態經過一連串翻轉後的結果。 Input： 輸入資料有兩行，第一行是陣列大小 N ( N <= 20 )，第二行是一個由 H V D 所組成的字串，長度 <= 20。 Output： 輸出初始狀態經過指定之一連串翻轉動作後的結果。 範例： 解題想法： 先把題目所需的方陣中數字填進去，依照命令分開寫不同的迴圈來翻轉矩陣，並且每次翻轉完取代原本的陣列，最後再輸出答案。 第一步、處理題目所需的輸入格式 1.宣告題目所需的陣列大小，number 2.宣告整數 count 等於 1，這個計數器後面會派上用場 3.宣告題目需讀入的翻轉指令字串 s 4.輸入整數 number 和字串 s ※輸入 number 後，再輸入字串 s 前要先加入 cin.ignore(1000,'\');     避免輸入完數字後按 enter，程式會誤以為 enter 就是字串 s 5.使用 vector 功能建立一個用來儲存方陣的二維整數陣列，OriginalArray 第二步、依測試資料提供的陣列大小，把數字放進二維陣列 題目並沒有給我們整個二維陣列裡的值 每次陣列的大小也不一定 因此陣列裡的值只能有我們自己放進去 1.設置一個迴圈為陣列中的列 2.迴圈內宣告一個整數陣列 buf1，為放數字用 3.迴圈內設置第二個迴圈為陣列中的行     這時 count 就派上用場了     ...

簡介 題目來源：e-tutor平台 [C_AR183-易] 數字跑馬燈 數字跑馬燈，這題在輸入資料與如何處理資料這部分比較麻煩，讀進字串後還要切割，甚至還需要把字串轉整數，需要多個步驟。 讓我們先了解題目內容 問題描述： 請讀入二行資料，第一行是一串空白隔開的數字 ( 個數 N <= 20 )，假設這是要顯示的跑馬燈，第二行是一串讓跑馬燈資訊左右轉動的命令，可以指定這一串數字向左或者向右轉的次數，當一個數字從第一個位置向左轉出時，會移動到最後一個數字，反之亦然，一個數字從最後一個位置向右轉出時，會移動到第一個數字。下面例子說明跑馬燈轉動的過程：假設讀入的一串數字如下： 20 -5 -18 6 18 22 5 7 12 51 19 讀入的轉動命令為 L 5 R 13 R 2 L 7，L 表示向左移動，R 表示向右移動，所以 L 5 表示向左移動 5 個位置，R 13 表示向右移動 13 個位置等，則這些命令依序轉動過程如下： L 5 → 22 5 7 12 51 19 20 -5 -18 6 18 R 13 → 6 18 22 5 7 12 51 19 20 -5 -18 R 2 → -5 -18 6 18 22 5 7 12 51 19 20 L 7 → 12 51 19 20 -5 -18 6 18 22 5 7 最後一行即是全部轉動完畢之後，要輸出的結果。 Input： 輸入資料有兩行，第一行是由空白隔開的一串數字 ( 最多 20 個 )，第二行是一串左轉或右轉的命令，命令之間由空白字元隔開，每個命令包含一個 L 或 R 字元 ( 皆為大寫字元 )，接著一個整數 S ( S >= 0 ) ，表示往左或者往右轉動 S 個位置。最多 25 個命令。 Output： 輸出該串數字經過這一連串的轉動命令之後的結果。 範例： 解題想法： 先處理輸入資料，把輸入的數字先存起來，再用兩個陣列儲存命令，一個是只有經過切割字串，另一個則是切割完後轉整數，資料分開後再去計算所有的左轉和右轉互相抵銷，到底該往哪個方向移動位置，接著不要去更動到原本的數字陣列，使用不同的輸出方式輸出答案。 第一步、處理題目所需的輸入格式 1.使用 vector 功能建立二個一維的 字串 陣列，分別為...

簡介 題目來源：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...

簡介 題目來源：e-tutor平台 [C_AR186-易] 道路修補 道路修補，每筆測資都給我們不只一段修補路段，每段路段皆不同地方，甚至還有重複修補的地方，而題目需要我們幫他找出總共有多少修補路段，而且不能計算到重複的區域，那我們該怎麼處理那麼多不同的道路修補路段呢？ 讓我們先了解題目內容 問題描述： 因為有民眾投訴道路坑坑窪窪的，容易發生意外，考量到用路人的安全，政府決定對該道路進行修補。但基於成本考量，沒辦法將道路從頭到尾整修一遍，於是派出數支調查隊針對整條道路進行評估，再根據各隊評估結果計算出需進行修補的長度。舉例來說，現在有 3 個評估結果，分別為：(1) 3 到 5 公里處 (2) 6 到 13 公里處 (3) 10 到 14 公里處，則最後需要修補路段為 3 到 5 公里處以及 6 到 14 公里處，共計 10 公里的長度。現在請你寫個程式，根據每個評估結果，計算出需要修補的道路總長度。 Input： 第一行會有一個整數代表測資筆數。每筆測資第一行有一個整數 n 表示有 n 個評估結果 (1   ≤ n  ≤ 1000)。接下來有 n 行，每行有兩個整數 s 、 e ，表示在該評估結果中需要修補的路段，其中 0 ≤ s < e  ≤ 10000 ，數值間以一個空白隔開。 Output： 每筆測資輸出需要修補的道路總長度於一行。 範例： 解題想法： 把整條路段想像成一塊白色有格子的長方形，只要有修補的路段，就把修補路段的格子塗顏色，最後再去算有幾個格子有塗顏色。 例子： ※只要修補過就塗顏色，就可以解決重複修部部分會混亂的問題 第一步、要先處理輸入，宣告題目所需的條件 1. test 為測資筆數 2. number 為評估後需要修幾段路 3. ans 為最後要計算修補長度為多少 4. road 陣列為題目限制最大路段，全部預設0 輸入測資筆數、評估後修幾段路 第二步、設定評估後修幾段路的迴圈 迴圈：使用第一步輸入的 number 定為限制迴圈的變數 第三步、輸入路段的頭尾，並且塗顏色 宣告 2 個變數，begin 為修補路...

簡介 題目來源：e-tutor平台 [C_MM080-易] 音樂CD盒 這個題目大家第一眼看時，可能會覺得很亂，分成兩種 CD 盒，兩種 CD 盒的價錢與容量也都不盡相同，而在題目只給有多少片 CD 的情況下，詢問到底該怎麼裝才會最省錢，那我們該怎麼找出最省錢的方法呢？ 讓我們先了解題目內容 問題描述： 小明是個很喜歡聽音樂的人，他擁有很多音樂 CD ，現在他想要買 CD 盒來裝 CD 。市面上只有兩種 CD 盒，一種可以裝 n 1 片並且售價  d 1 元，另一種可以裝 n 2 片並且售價 d 2 元。小明希望買到的 CD 盒在使用上都是裝滿的，而且希望花最少的錢來買。現在請你幫小明寫一個程式來決定小明該買這兩種盒子各多少個才好。 Input： 輸入總共有三列資料。第一列是輸入一個正整數 N (小明的 CD 數)，第二列是輸入正整數 n 1 、 d 1 ，第三列是輸入正整數 n 2 、 d 2 ， (1 ≤ N 、 n 1 、 d 1 、 n 2 、 d 2 ≤ 1000000) 。 Output： 輸出為一列資料，包含兩個大於等於零的整數分別代表兩種盒子買的數量，如果找不到滿足題意的解，就輸出 ”false” 。 範例： 解題想法： 兩種 CD 盒到底該各買多少個才能分配完所有的 CD，可以設定雙重迴圈，來記錄兩種 CD 盒取或不取的紀錄，並且把所有的可能都記錄下來，再來找取最佳的組合。 ※以下把兩種 CD 盒稱為 A 與 B 第一步、要先處理輸入，宣告題目所需的條件 1. CDnumber 為 CD 總數 2. n1 、 n2 分別為兩種 CD 盒的容量 3. d1 、 d2 分別為兩種 CD 盒的價錢 這裡多設置了一個之後會使用到的計數器 count 使用 vector 功能 建立了 3 個一維陣列，分別用來儲存 A、B 兩種 CD 盒的數量以及最後花費的價錢 接著輸入題目要求的變數 第二步、找尋所有可能的組合 設置雙重迴圈，來列舉所有的組合 第一個迴圈：A 種 CD 盒從 0 個開始，直到大於 n1 / CDnumber 時停。 第二個迴圈：B 種 CD 盒從 0 個開始，直到大於 n2 / CDnumber 時停。 那為什...