V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
flavoury
V2EX  ›  问与答

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

  •  
  •   flavoury · 2018-03-04 20:57:42 +08:00 · 2308 次点击
    这是一个创建于 2215 天前的主题,其中的信息可能已经有所发展或是发生改变。

    各位,今天遇到一个递归问题:

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

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

    求大佬帮助!

    13 条回复    2018-03-06 00:19:12 +08:00
    pual
        1
    pual  
       2018-03-04 21:37:51 +08:00 via Android   ❤️ 1
    计算机程序的构造与解释那本书有讲
    dbw9580
        2
    dbw9580  
       2018-03-04 21:44:08 +08:00 via Android   ❤️ 1
    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
        3
    pual  
       2018-03-04 21:49:35 +08:00 via Android   ❤️ 1
    具体说就是 1 元钱用 5 分与不用 5 分用剩下的钱币类型来计算,函数第一次运行后条件变为 9 角 5 分有多少种方法凑成和 1 元钱用 1 分,2 分有多少种方法凑成,通过递归调用将条件慢慢收敛
    carlclone
        4
    carlclone  
       2018-03-04 21:57:05 +08:00 via Android   ❤️ 1
    递归问题基本都是树结构的,画个图就出来了
    suikalo
        5
    suikalo  
       2018-03-04 23:06:46 +08:00   ❤️ 1
    ```
    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
        6
    skadi  
       2018-03-04 23:18:27 +08:00
    现在的人写代码连个 dfs 都不会了么?
    webjin1
        7
    webjin1  
       2018-03-04 23:20:50 +08:00 via Android
    迭代还是递归
    aheadlead
        8
    aheadlead  
       2018-03-05 08:35:52 +08:00 via iPhone
    这 tm 不就是线性 dp 吗?

    用得着 dfs,递归啥的吗……
    victor97
        9
    victor97  
       2018-03-05 09:35:52 +08:00 via Android
    这应该用 dp 吧,当然记忆化递归搜索也可以
    flavoury
        10
    flavoury  
    OP
       2018-03-05 10:07:01 +08:00 via iPhone
    @webjin1
    @aheadlead
    @victor97
    题目要求使用递归,我也知道这个有更优解。。
    carlclone
        11
    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
        12
    carlclone  
       2018-03-06 00:01:33 +08:00
    @carlclone target 传 100...
    carlclone
        13
    carlclone  
       2018-03-06 00:19:12 +08:00
    糟糕错了, 得用记忆化搜索 , 在 V2 发言一不小心就暴露智商
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3951 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 36ms · UTC 10:23 · PVG 18:23 · LAX 03:23 · JFK 06:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.