Question

(a) Write a SCHEME function (make-change n den) which outputs a list of change specifications. Namely, a call (make-change 11 (list 25 10 5 1) produces the list
((1 1 1 1 1 1 1 1 1 1 1) (1 1 1 1 1 1 5) (1 5 5) (1 10))
Hints: a helper function (helper n den cur) that takes as input cur, a list of coins given out so far will surely come in handy! Also, the order in which the "options" appear in the top list is immaterial.

(b) While getting the output above is helpful, it is not particularly readable. Indeed, the list (1 1 1 1 1 1 5) that states 6 pennies and 1 nickel could be far more readable as ((6 . 1) (1 . 5)) also stating 6 pennies and 1 nickel. That is, this is a list of pairs telling us how many of each denomination. Thankfully, the former can be translated into the latter by a conversion known as run length encoding that replaces sequences of an identical value by a pair giving the number of repetition of the value.
Write a SCHEME function (rle coins) which, given a list of coins, returns a list of pairs denoting the number of repetitions of each sequence of consecutive values. As a last example, the list
(list 1 1 1 1 1 1 1 5 5 5 5 1 1 1 10 10 10 1 1 25 25 25 25 25 25)
would be encoded as
( (17. 1) (4.5) (3 . 1) (3. 10) (2 . 1) (6. 25) )
Note how the tree sub-sequences of pennies are not collapsed into a single value. Those are kept as separate pairs. Naturally, this function only works for one element of the output from make-change.

Answer 1

Answer:

#include <iostream>

using namespace std;

// Function to find the total number of ways to get change of N

// from unlimited supply of coins in set S

int count(int S[], int n, int N)

{

// if total is 0, return 1

if (N == 0)

 return 1;

// return 0 if total become negative

if (N < 0)

 return 0;

// initialize total number of ways to 0

int res = 0;

// do for each coin

for (int i = 0; i < n; i++)

{

 // recur to see if total can be reached by including

 // current coin S[i]

 res += count(S, n, N - S[i]);

}

// return total number of ways

return res;

}

// Coin Change Problem

int main()

{

// n coins of given denominations

int S[] = { 1, 2, 3 };

int n = sizeof(S) / sizeof(S[0]);

// Total Change required

int N = 4;

cout << "Total number of ways to get desired change is "

  << count(S, n, N);

return 0;

}