MIT OpenCourseWare 6.00 Introduction to Computer Science and Programming: Lesson 3, HW 1
I came up with a recursive approach to solving this problem. I have posted the code for problem 3 and 4 alone. I felt that the recursive approach was more intuitive because we can keep subtracing 6 or 9 or 20 from the input number and check if the resulting number is divisible by any of these.
#
# Problem 3
#
#function isBuyable(n)
def isBuyable(n):
#if n is divisible, return true
if n%6==0 or n%9==0 or n%20==0:
return True
#if not divisible, subtract 20, 9 and 6 and
#keep looking again recursively
if n>20:
return isBuyable(n-20)
return isBuyable(n-9)
return isBuyable(n-6)
else:
if n>9:
return isBuyable(n-9)
return isBuyable(n-6)
else:
if n>6:
return isBuyable(n-6)
#the function returns false when
#n is less than 6
return False
#function isBuyable(n) END
maxNotBuyable=1
sixConsecBuyableFound=False
n=1
consecBuyableCount=0
while sixConsecBuyableFound==False :
if isBuyable(n):
consecBuyableCount+=1
else:
consecBuyableCount=0
maxNotBuyable=n
if consecBuyableCount==6:
sixConsecBuyableFound=True
n+=1
print 'Largest number of Mcnuggets not buyable : ', maxNotBuyable
#
# Problem 4
#
#function isBuyable(n,x,y,z)
def isBuyable(n,x,y,z):
if n%x==0 or n%y==0 or n%z==0:
return True
if n>z:
return isBuyable(n-z,x,y,z)
return isBuyable(n-y,x,y,z)
return isBuyable(n-x,x,y,z)
else:
if n>y:
return isBuyable(n-y,x,y,z)
return isBuyable(n-x,x,y,z)
else:
if n>x:
return isBuyable(n-x,x,y,z)
return False
#function isBuyable(n,x,y,z) END
maxNotBuyable=1
smallNumConsecBuyableFound=False
n=1
consecBuyableCount=0
x=int(raw_input('enter x:'))
y=int(raw_input('enter y:'))
z=int(raw_input('enter z:'))
packages=(x,y,z)
while smallNumConsecBuyableFound==False :
if isBuyable(n,packages[0],packages[1],packages[2]):
consecBuyableCount+=1
else:
consecBuyableCount=0
maxNotBuyable=n
if consecBuyableCount==packages[0]:
smallNumConsecBuyableFound=True
n+=1
if n>1000:
maxNotBuyable='Beyond what could be bought'
break
print 'Largest number of Mcnuggets : ', maxNotBuyable
