13.png
P13.2 Ladder
Count the number of different ways of climbing to the top of a ladder.
-
P13.2 爬梯子
计算爬到梯子顶端的不同方式的个数
梯子有N个横档，编号从1到N。每爬一步，可以上升一或者2个横档。也就是说：如果在编号为K的横档上，爬一步可以到K+1或K+2横档上。爬行第一步后，可以到达 编号为1或者编号为2的横档上，但是最终需要站到编号为N的横档上(梯子的顶端)。计算爬到梯子顶端的不同方式的数量。
例如，如果N=4，则有5种不同的攀爬方式，分别是：
(1) 1、1、1和1级：每一步都上1个；
(2) 1、1和2级：前2步上1个，最后一步上2个；
(3) 1、2和1级：第一步上1个，第二步上2个，第三步上1个；
(4) 2、1和1级：第一步上2个，最后两步上1个；
(5) 2和2个梯级：每一步都上2个；
如果N=5，你有8种不同的攀爬方式，分别是：
(1) 1、1、1、1和1级；
(2) 1、1、1和2级；
(3) 1、1、2和1级；
(4) 1、2、1和1级；
(5) 1、2和2级；
(6) 2、1、1和1级；
(7) 2、1和2级；
(8) 2、2和1级；
不同方法的数目可能非常大，因此对于给定的整数P，返回mod2^P的值。
编写函数：
def solution(A, B)
给定两个由L的整数组成的非空数组A和B，则同样返回一个长度为L的数组，该数组的位置i上的元素为：爬到横档数为A[i]的梯子的顶部的所有方法的个数mod2^B[i]的值。
例如，给定L=5和：
A[0]=4，A[1]=4，A[2]=5，A[3]=5，A[4]=1；B[0]=3，B[1]=2，B[2]=4，B[3]=3，B[4]=1
函数应该返回序列[5，1，8，0，1]。
假定：
-
L是区间[1，50000]中的整数；
-
数组A的每个元素都是区间[1，L]内的整数；
-
数组B的每个元素都是区间[1，30]内的整数；
- 解题思路
利用动态规划的思想来计算爬梯子的方法的个数。站在编号为K的横档上，则可知道前一步是在K-1或者K-2的横档上，因此到达编号为K的方法个数就等于到达K-1的横档上的方法数与到达K-2的横档上的方法数之和。详细讲解参见。
如果利用%运算计算mod。例如函数solution_normal，则最终的程序不能满足时间要求。因此需要对大数的求模运算进行优化。一种是分解的方法：也就是将大数按照如下原则分解为小数，其性能会比%较差。见函数big_mod。
def big_mod(M, N):
"""
M是一个比较大的整数:原则：(A+B)%N=(A%N+B%N)%N，(A*B)%N=(A%N*B%N)%N
根据上面的原则可以把一个大的整数拆分为比较小的数之和
这种方法比%运算稍慢。
:param M: 大的整整
:param N: 模
:return: M%N
"""
divided_list = []
str_m = str(M)
length = len(str_m)
for i in range(len(str_m)):
if int(str_m[i]) != 0:
divided_list.append([int(str_m[i]), length - i - 1]) # 数位上的数字，数位
sum_mod = 0
for j in divided_list:
son_mod = j[0] % N
times = j[1]
while times != 0: # 乘法原则
son_mod *= 10 % N
times -= 1
sum_mod += son_mod % N # 加法原则
return sum_mod % N
另一种比较好的方法就是利用位运算，在不产生溢出的情况下：
- 取模运算： a % (2^n) 等价于 a & (2^n - 1)
- 乘法运算： a * (2^n) 等价于 a<< n
- 除法运算： a / (2^n) 等价于 a>> n
- Python3代码
# -*- coding：utf-8 -*-
# &Author AnFany
# Lesson 13：Fibonacci numbers
# P 13.2 Ladder
def ladder(n):
"""
计算爬到横档数为n的梯子的顶端的方式的个数
:param n: 梯子的横档数
:return: 爬的方式的个数
"""
methods = [1] * (n + 1) # 横档数n：方式个数
methods[1] = 2
for i in range(2, n+1):
methods[i] = methods[i-1] + methods[i-2]
return methods
def solution_normal(A, B):
"""
数组A的元素为梯子的横档数，数组B元素为计算mod值得幂数，时间复杂度为O(L**2)
:param A: 正整数数组
:param B: 正整数数组
:return: mod值的数组
"""
max_num = len(A)
methods_dict = ladder(max_num)
C = [2 ** h for h in B]
return [methods_dict[i-1] % j for i, j in zip(A, C)]
def solution(A, B):
"""
数组A的元素为梯子的横档数，数组B元素为计算mod值得幂数，时间复杂度为O(L)
:param A: 正整数数组
:param B: 正整数数组
:return: mod值的数组
"""
max_num = len(A)
methods_dict = ladder(max_num)
C = [1 << h for h in B]
return [methods_dict[i-1] & (j - 1) for i, j in zip(A, C)]
- 结果
image
点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。
image
image
网友评论