CODEWITHSUNDEEP
python
Gyros
Gyros

Reputation: 31

How to recursively write any large amount as a sum of 5 and 7 coins?

I am taking a discrete mathematics course and I do not figure it out how to make a recursive function in Python which transform any large amount in a sum of 5- and 7- coins.

I tried it for with 3- and 5- coins and it is working, but for 5- and 7- it does not and I did not find something about it like a rule or something.

    def change(amount) :
      assert( amount>= 12 )
      if amount==12 :
       return [5,7]
      if amount==14 :
       return [7,7]
      if amount==15:
       return [5,5,5]
      coins=change(amount-7)
      coins.append(7)
      return coins

I expect the output of the coins used, but it just does not work, it says "RunTime Error" when i send it.

Upvotes: 1

Views: 1363

Answers (3)

Manu E Thomas
Manu E Thomas

Reputation: 73

Since 24, 25, 26, 27, 28 can all be represented by 5 and 7, we can create an algorithm that reduces the amount by 5 during each recursive call. Finally the recursion will achieve one of the base conditions listed in the if else statements. The code is shown below

def change(amount):
  if amount == 24:
    return [5, 5, 7, 7]
  if amount == 25:
    return [5, 5, 5, 5, 5]
  if amount == 26:
    return [7, 7, 7, 5]
  if amount == 27:
    return [5, 5, 5, 5, 7]
  if amount == 28:
    return [7, 7, 7, 7]
  coins = change(amount-5)
  coins.append(5)
  return coins

Upvotes: 0

Romain Reboulleau
Romain Reboulleau

Reputation: 306

The problem is not the python code here, but the algorithm. As stated in the comments, always removing 7 first can lead you in cases with infinite recursion.

If the "amount" is large enough (I guess higher than 35 works, but you might want to do the math to find the exact limit), you can proceed like this:

def change(amount):
    if (amount % 5 == 0):
        return [5] * int(amount/5)
    elif (amount % 7 == 0):
        return [7] * int(amount/7)
    else:
        coins = change(amount-5)
        return coins.append(5)

This works for large enough values because after max 7 times removing 5, you will always get a result which is a multiple of 7.

There should be more clever ways to do this but it should work.

Knowing that the minimum value of 23, another approach (non recursive) would be to look at the modulo 5 division (amount % 5), and give 5 different solutions.

If it's 0, amount can be divided by 5, so it's just a list of 5s; if it's 1, remove 3*7 = 21, and what remains is a list of 5s; and so on. The following code gives you a correct answer for all amount greater than 23. You then just have to deal with the remaining cases, if necessary.

def change(amount):
    d = amount % 5
    if d == 0:
        return [5] * int(amount/5)
    elif d == 1:
        return [7] * 3 + [5] * int((amount-21)/5)
    elif d == 2:
        return [7] + [5] * int((amount-7)/5)
    elif d == 3:
        return [7] * 4 + [5] * int((amount-28)/5)
    elif d == 4:
        return [7] * 2 + [5] * int((amount-14)/5)

Upvotes: 2

kpie
kpie

Reputation: 11080

Just for fun it might help you to look at a change making program that is actually recursive.

# amount paid and cost due in dollars.
def process(paid,cost):
    amount = int((float(paid)-float(cost))*100)
    names = ['penny','nickle','dime','quarter','halfdollar','dollar','2Piece','5Spot','Tenner','Dub','Fifty','CNote']
    made = {k:0 for k in names}
    return(makeChange(amount,made))

def makeChange(amount,made):
    # coin and bill values in cents 
    coins = [1,5,10,25,50,100,200,500,1000,2000,5000,10000]
    coins.reverse()
    names = ['penny','nickle','dime','quarter','halfdollar','dollar','2Piece','5Spot','Tenner','Dub','Fifty','CNote']
    names.reverse()
    decode = {coins[n]:names[n] for n,k in enumerate(coins)}
    i = 0
    if(amount>0):
        while(coins[i]>amount):
            i+=1
        amount-=coins[i]
        made[decode[coins[i]]]+=1
    else:
        return(made)
    return(makeChange(amount,made))

test = process(20,11.73)
for k in test:
    if(test[k]!=0):
        print(k+":"+str(test[k]))

Upvotes: 0

Related Questions