## can u help me to solve this ...plzzz

Discussion of Common Lisp
ketan
Posts: 2
Joined: Wed Aug 04, 2010 12:53 am

### can u help me to solve this ...plzzz

You can view the process of making changes as recursive. You first see if any dollars are required, subtract them from the total, and then make change for what remains. The following function implements such a recursive approach to making change. The function make-change converts a given number of cents into dollars, half-dollars, quarters, and so forth.

Complete the LISP program to achieve the above requirements:

(defun make-change (money)
(cond ((>= money 100)
(cons (list (truncate money 100) 'dollars)
(make-change (rem money 100))))
((>= money 25)
(cons â€¦.

The use of above function is:
> (make-change 123)
((1 DOLLARS) (2 DIMES) (3 CENTS))

Jasper
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands
Contact:

### Re: can u help me to solve this ...plzzz

You could make

Code: Select all

``````(defgeneric coin-value (coin)
(:method ((coin (eql 'dollar)) 100)
(:method ((coin (eql 'dime)) 10)) ;..Etcetera, just a way to list values of the different types.``````
And then you feed the function a list, starting with the higher-value coins ending with the lower value coins, and then go down that list with a recursive function, each time seeing how many coins/bills you can use with (floor money (coin-value top-of-the-list)), subtracting the associated value from the total amount, and then doing the same with the other types of money.

Your approach seems like it would work, but if i were you i'd prefer something with the values and coins not so hard-coded in. Also in the forum please use \[code\] tags, and indent.(Indentation is also good for clarity as you read your own code..)

Warren Wilkinson
Posts: 117
Joined: Tue Aug 10, 2010 11:24 pm
Location: Calgary, Alberta
Contact:

### Re: can u help me to solve this ...plzzz

I actually did this yesterday. I wanted to run a genetic algorithm to see what set of 'coins denominations' made for the least amount of change. Anyway, here was mine:

Code: Select all

``````(defun currency (a amounts results)
(if (null amounts)
(nreverse (cons a results))
(multiple-value-bind (n remainder) (truncate a (car amounts))
(currency remainder (cdr amounts) (cons n results)))))

(currency 10 '(3 2) nil)
(3 0 1)
``````
See, 10 is 3 3-unit coins, 0 2-unit coins and 1 1-unit coin.
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.

Paul Donnelly
Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

### Re: can u help me to solve this ...plzzz

Warren Wilkinson wrote:I actually did this yesterday. I wanted to run a genetic algorithm to see what set of 'coins denominations' made for the least amount of change.
Come up with anything interesting?

Warren Wilkinson
Posts: 117
Joined: Tue Aug 10, 2010 11:24 pm
Location: Calgary, Alberta
Contact:

### Re: can u help me to solve this ...plzzz

Well, not anything too interesting. The results are highly dependent on the heuristic for deciding 'best'. For example, a set of coins that had denominations for 1, 2, 3, 4, 5, 6 ... , 97, 98, 99, 100 would perform well -- only 1 coin is ever needed. If you add a cost for the number of unique coins, you get different results depending on that cost.

For a cost of (+ ( expt 1.85 num-coins ) average-number-of-coins-needed) the best candidates were:
• 30 5 1
• 16 3 1
• 25 5 1
For a cost of (+ (expt 1.35 num-coins) average-number-of-coins-needed) the best candidates were
• 47 13 5 1, (score 6.74)
• 27 13 5 1, (score 6.83)
• 27 7 5 1, (score 6.86)
By comparison 25, 10, 5, 1 scored 7.14

These results also depend on the amount of change you are making. If you are trying to find the most efficient ways to make change up to 10 dollars worth, the numbers become around 3010, 1145, 313, 64, 10, 1.

In my case, I wanted Starcraft 2 players to be able to write 'cheque -number-' and spawn a unit with that many 'amount' buffs on it. The problem was that applying 6000 1+amount buffs to a unit caused the game to pause, but applying 6 1000+amount buffs was quick. So I wanted to design the best set of buff amounts to make any number the user typed quickly applied. I assumed most users would type human numbers like 300, 6000 25000, &c and only rarely have strange numbers like 31567. Under these circumstances power of tens buffs were by far the best performer.
Need an online wiki database? My Lisp startup http://www.formlis.com combines a wiki with forms and reports.