Re: [問題]有關用 ved c++解高中生程式解題系統之題

看板C_and_CPP (C/C++)作者loveme00835 (最愛朴素妍)時間15年前 (2011/01/05 02:11)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串2/2 (看更多)

※ 引述《sean819 (阿翔)》之銘言： : ※ [本文轉錄自 Programming 看板 #1D8laqkA ] : 作者: sean819 (阿翔) 看板: Programming : 標題: [問題]有關用 ved c++解高中生程式解題系統之題 : 時間: Tue Jan 4 18:40:50 2011 : 我是C++初學者 : 想請問一下 : 高中生程系解題系統 : http://zerojudge.tw/Problems : 的第D133題 : 老師教的公式是f[b]+=f[b-C[a]]; : 我照老師教的寫 : #include <iostream> : #define T 30000 : using namespace std; : int main () { : long long int a,b,c; : long long int C[5]={1,5,10,25,50}; : long long int f[T+1]={0}; : f[0]=1; : for(a=0;a<5;a++) : for(b=C[a];b<=T;b++) : f[b]+=f[b-C[a]]; : while(cin>>c){ : if (f[c]==1) : cout<<"There is only "<<f[c]<<" way to produce "<<c<<" : cents change."<<endl; : else : cout<<"There are "<<f[c]<<" ways to produce "<<c<<" cents : change."<<endl; : } : return 0; : } : 問題1.define是做什麼用的? 原文推文的連結麻煩撥空看一下. : 問題2.for(b=C[a];b<=T;b++) : f[b]+=f[b-C[a]];是什麼意思 for(b=C[a];b<=T;b++) → 選一個硬幣C[a], 包含此硬幣能組成的各種金額都試一遍 f[b]+=f[b-C[a]]; → 組成某一個金額 k的方法數, 除了用之前選過的硬幣去組成以外, 還可以經由 '組成金額 k - C[a] 的方法數' 加上 C[a] 來湊成. 簡化一下問題好了, 假設面額只有兩種:{ 1, 5 }, 我要產生 10 分錢. 第一次外層迴圈選擇 1分錢, 內層迴圈跑完後, f陣列會長成這樣: 1分錢 5分錢 10分錢 ↓ ↓ ↓ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ 1│ 1│ 1│ 1│ 1│ 1│ 1│ 1│ 1│ 1│ 1│ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ 這是因為只拿 1分錢去產生 1 ~ 10分錢的方法都只有一種可能. 再來第二次外層迴圈選擇 5分錢, b 從 5開始往上加. 1分錢 5分錢 10分錢 ↓ ↓ ↓ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ 1│ 1│ 1│ 1│ 1│ 2│ 1│ 1│ 1│ 1│ 1│ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ │ ↑ └─────────┘ 5 分錢除了用之前選的 1分錢組成以外, 還可以從0 分錢的組成方法數額外加上一個 5 分錢來組成 b 繼續遞增, 表格中的數值一直增加.. 1分錢 5分錢 10分錢 ↓ ↓ ↓ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ 1│ 1│ 1│ 1│ 1│ 2│ 2│ 1│ 1│ 1│ 1│ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ │ ↑ └─────────┘ 1分錢 5分錢 10分錢 ↓ ↓ ↓ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ 1│ 1│ 1│ 1│ 1│ 2│ 2│ 2│ 1│ 1│ 1│ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ │ ↑ └─────────┘ ........................ ........................ ........................ 一直到 10分錢為止, 因為多出了一個可能性:從 5分錢的組成方法數額外加上一個 5分錢來組成. 1分錢 5分錢 10分錢 ↓ ↓ ↓ ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ 1│ 1│ 1│ 1│ 1│ 2│ 2│ 2│ 2│ 2│ 3│ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ │ ↑ └─────────┘ 各別是: 1×10 、 1×5 + 5 、 5 + 5這三種情況, 兩種顏色的組合各在不同階段所產生. 我把你程式稍微修改了一下, 變成這樣: http://codepad.org/Ef6dldrY 對我而言是比較好讀啦! @_@ : 我現在高一請大家能不能用簡單說法解釋畫個圖, 從頭到尾推演一下很快就懂了. -- ◢████ ◢█ ◢██◣ ◢█ ◢███ ◢█ T-ara版怎麼去 ████◤ ██ ◢██◣█ ██ ████ ██ s ~> T-ara █／███ ██ ██ ██ █／█ ◢███ █／█ 歡迎您的光臨 ████◤ ██ ██ ██ ██◤ ███◤ ██◤ 恩靜、智妍、孝敏 █／███ ██ █／██◤ ██ █／██ ██ 素妍、居麗、寶藍 ████◤ █◤ ◥██◤ █◤ ████◤█◤ 花英 ψmakigoto123 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.121.197.115 ※ 編輯: loveme00835 來自: 140.121.197.115 (01/05 02:39)