python做题记录002

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

第一题 汉诺塔

题目

汉诺塔.png

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)
    通过以下方法访问:
    1
    2
    hano("a", "b", "c", f, lst, plt)  # step初始化为1,传入list时才能改变
    print(lst[0] - 1)

第二题

题目

integ.png

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)。


----本文结束啦感谢您阅读----

欢迎关注我的其它发布渠道