Here is a recursive program that prints all the possible ways that an amount x (in cents)
Question:
Here is a recursive program that prints all the possible ways that an amount x (in cents) can be made up using Australian coins (which come in 5, 10, 20, 50, 100, and 200 cent denominations). To avoid repetition, each possible decomposition is ordered.
change <- function(x, y.vec = c()) {
# finds possible ways of making up amount x using Australian coins
# x is given in cents and we assume it is divisible by 5
# y.vec are coins already used (so total amount is x + sum(y.vec))
if (x == 0) {
cat(y.vec, "")
} else {
coins <- c(200, 100, 50, 20, 10, 5)
new.x <- x - coins
new.x <- new.x[new.x >= 0]
for (z in new.x) {
y.tmp <- c(y.vec, x - z)
if (identical(y.tmp, sort(y.tmp))) {
change(z, y.tmp)
}
}
}
return(invisible(NULL))
}
Rewrite this program so that instead of writing its output to the screen it returns it as a list, where each element is a vector giving a possible decomposition of x.
Probability and Statistics
ISBN: 978-0321500465
4th edition
Authors: Morris H. DeGroot, Mark J. Schervish