Want to improve this question? Update the question so it's on-topic for Stack Overflow.
Closed 10 years ago.
Improve this questionHow can I solve this riddle programmatically? Could someone help me with some pseudo-code or something?
Nine 9s
Combining nine 9's with any number of the operators +, -, *, /, (, ), what is the smallest positive integer that cannot be expressed?
Hints:
The answer isn't zero. You开发者_运维问答 can express zero like this: (9 - 9) * (9 + 9 + 9 + 9 + 9 + 9 + 9). Also, zero isn't a positive integer.
The answer isn't one. You can express one like this: 9 - (9 * 9 - 9)/9 + 9 - 9 + 9 - 9
It's not a trick question.
Be sure to handle parentheses correctly.
Notes:
- You cannot use exponentiation.
- You cannot concatenate (for example, put two 9's together to make 99).
- The - operator can be used in either its binary or unary form.
- Assume base 10.
This is actually a famous puzzle and there are probably many solutions hovering around the internet. I am not sure if any of them is correct or not. Does anybody have a well explained solution?
The answer is 195, here is some Python code that simply builds up all possible expressions by forming new expressions from exp1 OP exp2
. It runs in 0.165s on my PC.
exp = [set() for _ in xrange(10)]
exp[0].add(0)
exp[1].update([9, -9])
for i in xrange(1, 10):
for a in list(exp[i]):
for j in xrange(i, 10):
for b in list(exp[j-i]):
exp[j].update([a+b, a-b, a*b])
if b != 0:
exp[j].add(a/b)
n = 0
while n in exp[9]:
n += 1
print n
EDIT: If the answers must be exact integers (and not just the rounded result of integer division) then a check must be done when division is done.
if ((b != 0) and ((a/b) == float(a)/b)):
exp[j].add(a/b)
Under this interpretation of the rules, the new answer is 138. (the existing version computes 1386/10 [or -1386/-10] and gets 138)
195, http://members.iinet.net.au/~tmorrow/mathematics/ninenines/ninenines.html
精彩评论