题目要求

给定两个整数 a <= b，求由a转换到b的一个最短操作序列，可用操作为+1或*2

分析

1. 首先要明确解决这个问题的数学形式是什么，再考虑如何把这个数学形式化为程序实现
2. 如何实现最短？这是个优化问题，最直接的想法是遍历所有可能性，再取最短。本题的思路是用直接的算法得出最短序列
3. 这个算法是递归的形式

代码1：官方的

def f(a, b):
    if a == b:
        return str(a)

    if b % 2 == 1:
        return "(" + f(a, b - 1) + " + 1)"

    if b < a * 2:
        return "(" + f(a, b - 1) + " + 1)"

    return f(a, b / 2) + " * 2"


print("43 = " + f(9, 43))

43 = (((9 + 1) * 2 + 1) * 2 + 1)

代码2：我的

def f(a, b):
    if a == b:
        return str(a)
    if b < 2 * a:
        return "(" + f(a, b - 1) + ")" + "+1"
    if b % 2 == 0:
        return "(" + f(a, b // 2) + ")" + "*2"
    else:
        return "(" + f(a, b - 1) + ")" + "+1"


print("43 = " + f(9, 43))

43 = (((((9)+1)*2)+1)*2)+1

思考

1. 把算法的数学形式转化为递归形式
2. 两种代码的逻辑是等价的，只是逻辑判定顺序不同

Tips

1. 字符串首尾相连用+