Created
November 4, 2017 13:55
-
-
Save jerrypy/5235995a63bdbb85d66a1ff0a43af80b to your computer and use it in GitHub Desktop.
MIT 6.00 Assignments solutions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
# -*- coding: utf-8 -*- | |
def diophantine(n): | |
a = b = c = 0 | |
for a in range(20): | |
for b in range(20): | |
for c in range(20): | |
if 6 * a + 9 * b + 20 * c == n: | |
return (a, b, c) | |
# for i in range(35, 45): | |
# print(i, diophantine(i)) | |
''' | |
Theorem: If it is possible to buy x, x+1,..., x+5 sets of McNuggets, for some x, then it is | |
possible to buy any number of McNuggets >= x, given that McNuggets come in 6, 9 and 20 | |
packs. | |
''' | |
""" | |
if x, x+1, x+2, x+3, x+4, x+5, | |
then x+6 = x + 6 | |
x + 7 = x + 1 + 6 | |
... | |
x + 11 = x + 5 + 6 | |
x + 12 = x + 6 + 6 | |
... | |
For this type of problem, if you can find a string of sequential numbers | |
that is as long as the smallest counting unit then you can count to any | |
subsequent number by adding this smallest counting unit a member of this | |
base sequential series. | |
""" | |
def largest(x, y, z): | |
n = 1 | |
count = 0 | |
k = 0 | |
largest_not_valid = n | |
valid = False | |
while n <= 200: | |
for a in range(20): | |
for b in range(20): | |
for c in range(20): | |
if x * a + y * b + z * c == n: | |
valid = True | |
if valid: | |
count += 1 | |
if count == x: | |
print("Largest number of McNuggets that cannot be bought in exact quantity:" + str(largest_not_valid)) | |
return None | |
else: | |
largest_not_valid = n | |
count = 0 | |
valid = False | |
n += 1 | |
largest(6, 9, 20) | |
largest(16, 19, 20) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment