Python 编程训练4：a到b，increment & square 两个操作下需要多少步

increment & square 游戏

我们构造这样一个游戏：

• 进能够进行 increment(-1) 和 square(平方) 两种操作
• 由 a 到 b （a < b）

比如：1 到 5
1 increment 2
2 square 4
4 increment 5
共需要4步，操作序列：increment square increment

编程解决

如何输出从 a 到 b 的操作序列

imperative programming 命令式编程

def increment(n):return n+1def square(n):return n**2def findSequence(initial, goal):# root nodecandidates = [(str(initial), initial)]# loopfor i in range(1, goal - initial + 1):newCandidates = []for (action, result) in candidates:for (a, r) in [(' increment', increment), (' square', square)]:newCandidates.append((action + a, r(result)))print (i, ': ', newCandidates[-1])if newCandidates[-1][1] == goal:return newCandidates[-1]candidates = newCandidates

Functional Programming 函数式编程

def increment(n):return n+1def square(n):return n**2def apply(opList, arg):if len(opList) == 0:return argelse:return apply(opList[1:], opList[0](arg))def addLevel(opList, fctList):return [x+[y] for y in fctList for x in opList]def findSequence2(initial, goal):opList = [[]]for i in range(1, goal-initial+1):opList = addLevel(opList, [increment, square])for seq in opList:if apply(seq, initial) == goal:return seq

apply(opList, arg) 的解释：

opList 存放操作序列：比如[increment, increment, square, increment]
arg 存放初始参数

递归调用，比如: 传入参数opList = [increment, increment, square, increment]; arg = 10

apply(opList, 1) # opList = [increment, increment, square, increment]; arg = 1apply(opList, increment(1)) # opList = [increment, square, increment]; arg = 2apply(opList, increment(2)) # opList = [square, increment]; arg = 3apply(opList, square(3)) # opList = [increment]; arg = 9apply(opList, increment(9)) # opList = []; arg = 10return 10return 10return 10return 10
return 10

addLevel(opList, fctList) 的解释：

用于生成操作序列，该操作序列会使用 apply(opList, arg) 作用在一个 arg 初始参数上。

其中：x+[y] for y in fctList for x in opList
两层循环，外层参数为y，内层参数为x
返回值是 x+[y]

fctList 用于记录每个原子操作，比如这里是 [increment, square]