问题描述
There are four types of common coins in US currency:
quarters (25 cents)
dimes (10 cents)
nickels (5 cents)
pennies (1 cent)
There are 6 ways to make change for 15 cents:
A dime and a nickel;
A dime and 5 pennies;
3 nickels;
2 nickels and 5 pennies;
A nickel and 10 pennies;
15 pennies.
How many ways are there to make change for a dollar
using these common coins? (1 dollar = 100 cents).
问题说明
1 dollar = 100 cents ,现在有一美元需要兑换零钱。上面说明有四种单位, quarters (25 cents) dimes (10 cents) nickels (5 cents) pennies (1 cent)。 可以参看上面15 cents 有6种兑换方案。需要计算 1dollar 一共有多少种兑换方案 。
兑换方案举例:
100pennies 是一种
2 quarters + 50pennies 是一种
看到这道题后总是逃不过原来的习惯---想,一定要全部想明白了再做。结果导致想了半天,也没有开始做。看起Bob Deng 说的没错,需要每天一小时。TDD是需要刻意训练的。
测试用例
import static org.junit.Assert.assertEquals;
public class CountCoinsTest {
int[] coins = {25,10,5,1};
@Test
public void should_0_0(){
int count = CountCoins.makeChange(0);
assertEquals(0,count);
}
@Test
public void should_2_5(){
int count = CountCoins.makeChange(5);
assertEquals(2,count);
}
@Test
public void should_6_15(){
int count = CountCoins.makeChange(15);
assertEquals(6,count);
}
@Test
public void should_13_25(){
int count = CountCoins.makeChange(25);
assertEquals(13,count);
}
@Test
public void should_18_30(){
int count = CountCoins.makeChange(30);
assertEquals(18,count);
}
@Test
public void should_242_100(){
int count = CountCoins.makeChange(100);
assertEquals(242,count);
}
}
实现类
public class CountCoins {
public static int makeChange(int amount) {
int ways = 0;
if (amount < 1) return 0;
for (int quarters = 0; quarters <= amount; quarters += 25) {
for (int dimes = 0; dimes <= amount; dimes += 10) {
for (int nickels = 0; nickels <= amount; nickels += 5) {
int pennies = amount - quarters - dimes - nickels;
if (pennies < 0) break;
// System.out.println(quarters + " " + dimes + " " + nickels + " " + pennies);
ways++;
// for (int pennies = 0; pennies <= amount; pennies++) {
//
// if (quarters + dimes + nickels + pennies == amount) {
// System.out.println(quarters + " " + dimes + " " + nickels + " " + pennies);
// ways++;
// break;
// }
// }
}
}
}
return ways;
}
}
以上是对该题的一种简单的实现方法,比较直观。也可以参考武可写的,远程异步结对 - Count Coins 可以对本题以及TDD有更好的认识。
网友评论