求助！用递归实现硬币凑整(c 语言，复试上机题)

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2456 天前的主题，其中的信息可能已经有所发展或是发生改变。

各位，今天遇到一个递归问题：

用递归实现，显示用 1 分、2 分和 5 分的硬币凑成 1 元，一共有多少种方法。

我知道怎么用三重循环来实现，但是不知道递归怎么搞，试了几个总是不对。

求大佬帮助！

硬币

递

上机

实现

13 条回复 • 2018-03-06 00:19:12 +08:00

pual

2018-03-04 21:37:51 +08:00 via Android

计算机程序的构造与解释那本书有讲

dbw9580

2018-03-04 21:44:08 +08:00 via Android

if f(x,y,z) > 100: return []
if f(x,y,z) == 100: return [(x,y,z)]
if f(x,y,z) == 99: return [(x+1, y, z)]
if f(x,y,z) == 98: return [(x, y+1, z), (x+2, y, z)]
if f(x,y,z) == 95: return [(x+5,y,z), (x+3,y+1,z), ...]

return [flat(f(x+1, y, z)), flat(f(x, y+1, z)), flat(f(x, y, z+1))]

pual

2018-03-04 21:49:35 +08:00 via Android

具体说就是 1 元钱用 5 分与不用 5 分用剩下的钱币类型来计算，函数第一次运行后条件变为 9 角 5 分有多少种方法凑成和 1 元钱用 1 分，2 分有多少种方法凑成，通过递归调用将条件慢慢收敛

carlclone

2018-03-04 21:57:05 +08:00 via Android

递归问题基本都是树结构的，画个图就出来了

suikalo

2018-03-04 23:06:46 +08:00

```
package main
import (
"fmt"
)
func solve(money, x, y, z, last int) int{
if money == 0 {
return 1
}
count := 0
if money >= 1{
count = count + solve(money - 1, x + 1, y, z, 1)
}
if money >= 2 && last >= 2{
count = count + solve(money - 2, x, y + 1, z, 2)
}
if money >= 5 && last == 5{
count = count + solve(money - 5, x, y, z + 1, 5)
}
return count
}
func main(){
fmt.Println(solve(100, 0, 0, 0, 5))
}
```

Golang 版

skadi

2018-03-04 23:18:27 +08:00

现在的人写代码连个 dfs 都不会了么?

webjin1

2018-03-04 23:20:50 +08:00 via Android

迭代还是递归

aheadlead

2018-03-05 08:35:52 +08:00 via iPhone

这 tm 不就是线性 dp 吗？

用得着 dfs，递归啥的吗……

victor97

2018-03-05 09:35:52 +08:00 via Android

这应该用 dp 吧，当然记忆化递归搜索也可以

flavoury

2018-03-05 10:07:01 +08:00 via iPhone

@webjin1
@aheadlead
@victor97
题目要求使用递归，我也知道这个有更优解。。

carlclone

2018-03-05 23:59:07 +08:00

PHPer .... 闲得无聊写了一下

$count = 0;

function coinCombination($target)
{
if ($target == 0) {
global $count;
$count++;
} elseif ($target < 0) {
return;
}

coinCombination($target - 1);
coinCombination($target - 2);
coinCombination($target - 5);
}

coinCombination(5);
echo $count;

carlclone

2018-03-06 00:01:33 +08:00

@carlclone target 传 100...

carlclone

2018-03-06 00:19:12 +08:00

糟糕错了, 得用记忆化搜索 , 在 V2 发言一不小心就暴露智商