E-tutor [程式設計][C_MM080-易] 音樂CD盒

簡介

 題目來源：e-tutor平台
[C_MM080-易] 音樂CD盒

這個題目大家第一眼看時，可能會覺得很亂，分成兩種 CD 盒，兩種 CD 盒的價錢與容量也都不盡相同，而在題目只給有多少片 CD 的情況下，詢問到底該怎麼裝才會最省錢，那我們該怎麼找出最省錢的方法呢？

讓我們先了解題目內容

問題描述：

 小明是個很喜歡聽音樂的人，他擁有很多音樂 CD ，現在他想要買 CD 盒來裝 CD 。市面上只有兩種 CD 盒，一種可以裝 n1 片並且售價 d1 元，另一種可以裝 n2 片並且售價 d2 元。小明希望買到的 CD 盒在使用上都是裝滿的，而且希望花最少的錢來買。現在請你幫小明寫一個程式來決定小明該買這兩種盒子各多少個才好。

Input：

 輸入總共有三列資料。第一列是輸入一個正整數 N (小明的 CD 數)，第二列是輸入正整數 n1 、 d1 ，第三列是輸入正整數 n2 、 d2 ， (1 ≤ N 、 n1 、 d1 、 n2 、 d2 ≤ 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 時停。

那為什麼要把範圍鎖定在 n1 / CDnumber 和 n2 / CDnumber ？

舉例來說，假設 CD 總數 CDnumber 為 4 片

A 種 CD 盒可以裝 1 片CD，B種CD盒能裝 2 片CD

那麼考慮在只使用其中一種 CD 盒的情況下只有 2 種組合
這樣設定就不會使迴圈拿取太多某類的 CD 盒
避免所有 CD 都用某類 CD 盒裝，卻還有裝不滿的情況發生

那麼迴圈裡該放什麼？

 第三步、篩選所有的組合


列舉所有組合的途中，若有可以剛好把 CD 總數裝完的組合

就設定變數 price 把這個組合的價錢計算出來

分別把 A、B 種 CD 盒各需要幾個與組合的價錢，存入一開始用 vector 所設定的一維陣列中

並讓計數器 count 加一

 第四步、判斷


判斷計數器 count

如果所有組合中沒有一組剛好可以完全裝滿所有 CD 的話

count 就會為 0，並且輸出”false”

不符合以上結果的話，就列印出答案

但可以剛好完全裝滿所有CD的組合，可能不止一種

因此要從我們所存取的資料中，找尋最便宜的組合

第五步、找尋最佳的組合並印出答案

宣告 minn1、minn2、minprice 三個變數

分別用來記錄最佳組合的 A、B 盒數與最小價錢

而最小價錢在還不知道的情況下就以存價錢陣列中的第一項為預設

設定一個迴圈

使最小價錢從所有可能組合中價錢的陣列

一個一個比較，如果有更便宜的組合，就使用 minn1、minn2 紀錄

並且取代掉 minprice

最後迴圈跑完，輸出 minn1、minn2 就完成了！

完整程式碼如下

留言

張貼留言

這個網誌中的熱門文章

E-tutor [程式設計][C_AR183-易] 數字跑馬燈

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

圖片
簡介 題目來源：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_MM244-難] 複數的加減乘法

圖片
簡介 題目來源：e-tutor平台 [C_MM244-難] 複數的加減乘法 複數的加減乘法，雖然 e-tutor 把這題歸類在難，但這題其實很簡單，只要不把複數加減乘法公式中的變數搞混，這題很容易解出來！ 讓我們先了解題目內容 問題描述： 複數為實數的推廣，它使任一多項式都有根。複數當中有個「虛數單位」i，它是 -1 的一個平方根，即 i  ²  = -1。任一複數都可表達為 x + yi，其中 x 及 y 皆為實數，分別稱為複數之「 實部 」和「 虛部 」。 其加減乘法運算為： 加法 ：( a + b i ) + ( c + d i ) = ( a + c ) + ( b + d ) i 減法 ：( a + b i ) - ( c + d i ) = ( a - c ) + ( b - d ) i 乘法 ：( a + b i ) ( c + d i ) = a c + b c i + a d i + b d i  ²  = ( a c - b d ) + ( b c + a d ) i 本題輸入兩組複數，進行上述加法、減法、乘法運算並輸出結果。 Input： 請輸入兩組複數 ( 實數部分和虛數部分 ) 範圍：-10 ~ 10。 例如：                                                即表示為 -2.5 1                                                  (-2.5)+(1)i 1 9.252              ...
閱讀完整內容