本帖最后由 oppo 于 2017-1-17 15:38 编辑
[tex=md]
## 题目
Consider this puzzle: by starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. How would you write a function that, given a number, tries to find a sequence of such additions and multiplications that produce that number? For example, the number 13 could be reached by first multiplying by 3 and then adding 5 twice, whereas the number 15 cannot be reached at all.
## 代码
```
import sys
global dot
dot = "[tex=gv,dot]digraph G{\n"
def findSolution(target):
def find(start, history):
global dot
if start == target:
dot += "\"" + history + "\"[style=\"filled\" fillcolor=\"green\"];"
dot += 'end[label="结束-右侧分支不会被执行" shape="record"];'
dot += '"' + history + '" -> end[style="filled", fillcolor="red"];'
return(history)
elif start > target:
dot += "\"" + history + "\"[style=\"filled\" fillcolor=\"yellow\"];"
return(None)
else:
h_a = "(" + history + "%2B5)"
h_b = "(" + history + "*3)"
dot += "\"" + history + "\" -> \"" + h_a + "\";\n"
dot += "\"" + history + "\" -> \"" + h_b + "\";\n"
a = find(start + 5, h_a)
b = find(start * 3, h_b)
if a:
dot += "\"" + history + "\" -> \"" + h_a + "\"[color=\"red\"];\n"
elif b:
dot += "\"" + history + "\" -> \"" + h_b + "\"[color=\"red\"];\n"
return(a or b)
return(find(1, "1"))
if __name__ == '__main__':
solution = findSolution(int(sys.argv[1]))
dot += "}[/tex]"
print(dot)
print(solution)
```
[/tex]
target=24
[tex=gv,dot]digraph G{
"1" -> "(1%2B5)";
"1" -> "(1*3)";
"(1%2B5)" -> "((1%2B5)%2B5)";
"(1%2B5)" -> "((1%2B5)*3)";
"((1%2B5)%2B5)" -> "(((1%2B5)%2B5)%2B5)";
"((1%2B5)%2B5)" -> "(((1%2B5)%2B5)*3)";
"(((1%2B5)%2B5)%2B5)" -> "((((1%2B5)%2B5)%2B5)%2B5)";
"(((1%2B5)%2B5)%2B5)" -> "((((1%2B5)%2B5)%2B5)*3)";
"((((1%2B5)%2B5)%2B5)%2B5)" -> "(((((1%2B5)%2B5)%2B5)%2B5)%2B5)";
"((((1%2B5)%2B5)%2B5)%2B5)" -> "(((((1%2B5)%2B5)%2B5)%2B5)*3)";
"(((((1%2B5)%2B5)%2B5)%2B5)%2B5)"[style="filled" fillcolor="yellow"];"(((((1%2B5)%2B5)%2B5)%2B5)*3)"[style="filled" fillcolor="yellow"];"((((1%2B5)%2B5)%2B5)*3)"[style="filled" fillcolor="yellow"];"(((1%2B5)%2B5)*3)"[style="filled" fillcolor="yellow"];"((1%2B5)*3)" -> "(((1%2B5)*3)%2B5)";
"((1%2B5)*3)" -> "(((1%2B5)*3)*3)";
"(((1%2B5)*3)%2B5)" -> "((((1%2B5)*3)%2B5)%2B5)";
"(((1%2B5)*3)%2B5)" -> "((((1%2B5)*3)%2B5)*3)";
"((((1%2B5)*3)%2B5)%2B5)"[style="filled" fillcolor="yellow"];"((((1%2B5)*3)%2B5)*3)"[style="filled" fillcolor="yellow"];"(((1%2B5)*3)*3)"[style="filled" fillcolor="yellow"];"(1*3)" -> "((1*3)%2B5)";
"(1*3)" -> "((1*3)*3)";
"((1*3)%2B5)" -> "(((1*3)%2B5)%2B5)";
"((1*3)%2B5)" -> "(((1*3)%2B5)*3)";
"(((1*3)%2B5)%2B5)" -> "((((1*3)%2B5)%2B5)%2B5)";
"(((1*3)%2B5)%2B5)" -> "((((1*3)%2B5)%2B5)*3)";
"((((1*3)%2B5)%2B5)%2B5)" -> "(((((1*3)%2B5)%2B5)%2B5)%2B5)";
"((((1*3)%2B5)%2B5)%2B5)" -> "(((((1*3)%2B5)%2B5)%2B5)*3)";
"(((((1*3)%2B5)%2B5)%2B5)%2B5)" -> "((((((1*3)%2B5)%2B5)%2B5)%2B5)%2B5)";
"(((((1*3)%2B5)%2B5)%2B5)%2B5)" -> "((((((1*3)%2B5)%2B5)%2B5)%2B5)*3)";
"((((((1*3)%2B5)%2B5)%2B5)%2B5)%2B5)"[style="filled" fillcolor="yellow"];"((((((1*3)%2B5)%2B5)%2B5)%2B5)*3)"[style="filled" fillcolor="yellow"];"(((((1*3)%2B5)%2B5)%2B5)*3)"[style="filled" fillcolor="yellow"];"((((1*3)%2B5)%2B5)*3)"[style="filled" fillcolor="yellow"];"(((1*3)%2B5)*3)"[style="filled" fillcolor="green"];"((1*3)%2B5)" -> "(((1*3)%2B5)*3)"[color="red"];
"((1*3)*3)" -> "(((1*3)*3)%2B5)";
"((1*3)*3)" -> "(((1*3)*3)*3)";
"(((1*3)*3)%2B5)" -> "((((1*3)*3)%2B5)%2B5)";
"(((1*3)*3)%2B5)" -> "((((1*3)*3)%2B5)*3)";
"((((1*3)*3)%2B5)%2B5)" -> "(((((1*3)*3)%2B5)%2B5)%2B5)";
"((((1*3)*3)%2B5)%2B5)" -> "(((((1*3)*3)%2B5)%2B5)*3)";
"(((((1*3)*3)%2B5)%2B5)%2B5)"[style="filled" fillcolor="green"];"(((((1*3)*3)%2B5)%2B5)*3)"[style="filled" fillcolor="yellow"];"((((1*3)*3)%2B5)%2B5)" -> "(((((1*3)*3)%2B5)%2B5)%2B5)"[color="red"];
"((((1*3)*3)%2B5)*3)"[style="filled" fillcolor="yellow"];"(((1*3)*3)%2B5)" -> "((((1*3)*3)%2B5)%2B5)"[color="red"];
"(((1*3)*3)*3)"[style="filled" fillcolor="yellow"];"((1*3)*3)" -> "(((1*3)*3)%2B5)"[color="red"];
"(1*3)" -> "((1*3)%2B5)"[color="red"];
"1" -> "(1*3)"[color="red"];
}[/tex] |