币值为25分、10分、5分和1分，请编写代码计算n分有几种表示法

aswcy815174418 · 发表于 2021-1-25 14:22

题目：有数量不限的硬币，币值为25分、10分、5分和1分，请编写代码计算n分有几种表示法
例如：200分可由200个一分组成，其它全为0个看全网基本，要么迭代要么动态规划，
我想了想，迭代本质不就是for嵌套嘛，回溯法不也是嘛，我就写了一天没写出来
大家一起出来讨论讨论呗

闷骚小贱男 · 发表于 2021-1-25 14:38

一个一个的判断呗？如果能整除余数为0，就XX可由XX个组成

QingYi. · 发表于 2021-1-25 14:45

时间复杂度可不是这么算的小伙子

列明 · 发表于 2021-1-25 14:48

一個總的要求總是可以劃分成多個小的要求。
任意分，分解成零個或和多個25分、10分、5分、1分的，
你先寫：
1、任意分分解成25分的，輸出份數（含0）和餘數的組合；
2、任意分分解成10分的，輸出份數（含0）和餘數的組合；
3、任意分分解成5分的，輸出份數（含0）和餘數的組合；
4、任意分分解成1分的，輸出份數（含0）和餘數的組合；
然後再寫：
1、任意分分解成25分和10分的，輸出兩個份數和一個餘數的一系列組合，兩個份數需要是包含0,0的；
這一步是將上一步的1的結果餘數當作2的輸入，然後1的輸出份數和2的輸出份數與餘數結果聯合起來一起輸出。
接着再寫：
1、任意分分解成25分和10分和5分的，輸出叁個份數和一個餘數的一系列組合，叁個份數需要是包含0,0，0的；
這一步還是上一步的思路，多一道輸入輸出的過程，這也可以算是最後一步了，因為最後輸出的餘數完全可以當作是1分的分法了。

列明 · 发表于 2021-1-25 14:57

我怎麽感覺這有點像是概率論的問題呢？
這應該先給出一個算法，然後再按照算法編程。
直接編，有點費腦子。

VioletKiss · 发表于 2021-1-25 17:17

这个不是跟爬楼梯的算法差不多嘛，用的动态规划，你可以搜索一下

aswcy815174418 · 发表于 2021-1-26 06:24

VioletKiss 发表于 2021-1-25 17:17
这个不是跟爬楼梯的算法差不多嘛，用的动态规划，你可以搜索一下

我发帖的意思是用回溯法实现

aswcy815174418 · 发表于 2021-1-26 06:25

列明发表于 2021-1-25 14:48
一個總的要求總是可以劃分成多個小的要求。
任意分，分解成零個或和多個25分、10分、5分、1分的，
你先寫 ...

for循环嵌套你这个类似

aswcy815174418 · 发表于 2021-1-26 06:26

闷骚小贱男发表于 2021-1-25 14:38
一个一个的判断呗？如果能整除余数为0，就XX可由XX个组成

逐渐暴力？

闷骚小贱男 · 发表于 2021-1-26 08:43

aswcy815174418 发表于 2021-1-26 06:26
逐渐暴力？

咱小文盲一个... 搞不懂什么是回溯法...
要是我做这个题,反正都是for一个一个判断

帐号		自动登录	找回密码
密码			注册[Register]

[讨论] 币值为25分、10分、5分和1分，请编写代码计算n分有几种表示法