刷题记录————汉诺塔

借个不重要的课记录一下我做的题~
这周又开始懈怠了，还有超多的作业没有写完，难受……

第一题 汉诺塔

题目

答案

def hano(a, b, c, floor, step, plate):  # 输入汉诺塔的层数
    if floor == 1:
        print("[step %d] move plate %d# from %c to %c" % (step[0], plate[0], a, c))
        step[0] = step[0] + 1
        return None
    hano(a, c, b, floor - 1, step, plate)
    print("[step %d] move plate %d# from %c to %c" % (step[0], plate[floor - 1], a, c))
    step[0] += 1
    hano(b, a, c, floor - 1, step, plate)

# f(k+1)=2*f(k)+1 汉诺塔移动次数
if __name__ == "__main__":
    f = int(input())
    lst = [1]
    plt = []
    for i in range(1, f + 1):   # 创建一个数组放盘子，顶层为1，向下依次加1.
        plt.append(i)

    hano("a", "b", "c", f, lst, plt)  # step初始化为1,传入list时才能改变
    print(lst[0] - 1)

思路

这道题我是一步一步来做的。用递归的方式实现汉诺塔不难，但是又要添加具体是哪个汉诺塔的盘子在移动的信息，也要知道是第几步。由于我用的方法是递归，step必须要可以传出的变量表示。

1. 移动x层汉诺塔的思路：把x-1层汉诺塔移动到第二根杆，把最底层的盘子放到第三根杆，把x-1层汉诺塔移动到第三根杆。
2. floor和plate用数组传输。
   python数组是可以在传参后传出被改变的值。例如hano(a, b, c, floor, step, plate)中，step[0]和plate[0]在函数内赋值后都是可以直接传出函数的,传出后变量名对应hano("a", "b", "c", f, lst, plt)。
   通过以下方法访问：

   hano("a", "b", "c", f, lst, plt)  # step初始化为1,传入list时才能改变
   print(lst[0] - 1)

第二题

题目

答案

def findM(n, ansr):
    for i in ansr:
        if i % n == 0 and i != 0:
            return i // n
    return "No"

def answer_range(l, bits, sub, unic):  # 输出8位的结果
    if bits == 1:
        l.append(sub + unic)
    else:
        sub = sub + unic
        answer_range(l, bits - 1, sub, "0")
        answer_range(l, bits - 1, sub, "1")

if __name__ == "__main__":
    n = int(input())
    # 列出所有可能的m*n的结果：
    l = []
    answer_range(l, 8, "", "0")
    answer_range(l, 8, "", "1")
    t = [int(x) for x in l]  # 8位的所有结果
    # print(t)
    print(findM(n, t))

思路

这道题用枚举思路也可以实现，先算出N*M（M范围1~30000），最后判断乘积是不是由1、0构成的。
但是时间是O(n),问题规模很大，时间较长。
我这里使用的方法是列举所有由1和0能组成的8位数。然后做除法判断能否整除，这样既缩小了问题规模，也把时间缩小到O(1)。