第31题-换硬币的方法

本文包含欧拉项目第31题的解法

问题描述

第31题图

题目意思是：

在英国硬币可以分为如下几种：

1便士，2便士，10便士，20便士，50便士，1英镑（100便士），2英镑（200便士）

求解：如果有2英镑，能有几种硬币兑换方式

解题思路

脑海中闪过最简单的方法就是列多元方程然后求解，先试试这个办法吧

rust语言实现

p31.rs

pub fn count_coins(n: usize) -> usize {
    let mut num = 0;
    for h in 0..=1 {
       for g in 0..=2 {
           for f in 0..=4 {
               for e in 0..=10 {
                   for d in 0..=20 {
                       for c in 0..=40 {
                           for b in 0..=100 {
                               for a in 0..=200 {
                                   if 1 * a
                                        + 2 * b
                                        + 5 * c
                                        + 10 * d
                                        + 20 * e
                                        + 50 * f
                                        + 100 * g
                                        + 200 * h
                                        == n
                                    {
                                        num += 1;
                                    }
                               }
                           }
                       }
                   }
               }
           }
       }
    }
    return num;
}

pub fn f(money: isize, coins: &[isize]) -> isize {
    let l = coins.len();
    if l <= 0 {
        return 0;
    }
    if money == 0 {
        return 1;
    }
    if money < 0 {
        return 0;
    }
    return f(money-coins[0], coins) + f(money, &coins[1..l]);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_2_pounds() {
        assert_eq!(73682, count_coins(200));
        assert_eq!(73682, f(200, &[200, 100, 50, 20, 10, 5, 2, 1]));
    }
}

代码解释

这里列出了2中解法，分别是暴力算法和递归算法，暴力解法很简单很容易理解，但是需要运行很久（计算量太大了），现在来分析下递归算法的原理

可以得到这样的递归式：

硬币的分法等于包含了某种硬币的分法加上不包含此种硬币的分法，如：

f(200, [200, 100, 50, 20, 10, 5, 2, 1] = f(200-200, [200, 100, 50, 20, 10, 5, 2, 1]) + f(200, [100, 50, 20, 10, 5, 2, 1])

得到这个递归式之后代码就好写了，如上，瞬间就计算出结果了