-
-
-
-
-
在G. Polya 的名著” 如何解题” 中最后一题是: 你能用多少种方式兑换一个美元?(如果已知凑整一美元所需每一种钱币: 一分币、五分币、 一角币,二角五分币、五角币——各有多少个,就确定一种兑换方式)。 提示: 设An , Bn , Cn ,Dn , En 都是支付n 分钱的支付方式的数目 An :只用一分币 Bn :只用一分币与五分币 Cn :一分币、五分币、一角币 Dn :一分币、五分币、一角币、二角五分币 En :一分币、五分币、一角币、二角五分币、五角币 我们推出En = Dn + En−50 . 同理, Dn = Cn + Dn−25 , Cn =Bn + Cn−10 , Bn = An + Bn−5 . 该问题可以用动态规划解决, 那么, 1. 动态规划的主要特征是什么? 2. 就本题而言, 其递归算法的终止条件(也就是迭代算法的初始条 件) 是什么? 3. 你能否计算出问题的答案? 即一美元有多少种组合方式? ...
阅读题目
问答题
经典指数
-
-
-
-
-
扫描后移动端查看
相关标签
同类标签
|
微信公众号
|
|
欢迎加入,一起群聊
|