借个不重要的课记录一下我做的题~
这周又开始懈怠了,还有超多的作业没有写完,难受……
第一题 汉诺塔
题目
答案
1 | def hano(a, b, c, floor, step, plate): # 输入汉诺塔的层数 |
思路
这道题我是一步一步来做的。用递归的方式实现汉诺塔不难,但是又要添加具体是哪个汉诺塔的盘子在移动的信息,也要知道是第几步。由于我用的方法是递归,step必须要可以传出的变量表示。
- 移动x层汉诺塔的思路:把x-1层汉诺塔移动到第二根杆,把最底层的盘子放到第三根杆,把x-1层汉诺塔移动到第三根杆。
- floor和plate用数组传输。
python数组是可以在传参后传出被改变的值。例如hano(a, b, c, floor, step, plate)
中,step[0]和plate[0]在函数内赋值后都是可以直接传出函数的,传出后变量名对应hano("a", "b", "c", f, lst, plt)
。
通过以下方法访问:1
2hano("a", "b", "c", f, lst, plt) # step初始化为1,传入list时才能改变
print(lst[0] - 1)
第二题
题目
答案
1 | def findM(n, ansr): |
思路
这道题用枚举思路也可以实现,先算出N*M(M范围1~30000),最后判断乘积是不是由1、0构成的。
但是时间是O(n),问题规模很大,时间较长。
我这里使用的方法是列举所有由1和0能组成的8位数。然后做除法判断能否整除,这样既缩小了问题规模,也把时间缩小到O(1)。