CS 61A 2021 Fall Disc 04 Q2: Count K

Fall Disc 04 Q2: Count K"/>

CS 61A 2021 Fall Disc 04 Q2: Count K

CS 61A 2021 Fall Disc 04 Q2: Count K

• 题目
  Consider a special version of the count_stair_ways problem, where instead of taking 1 or 2 steps, we are able to take up to and including k steps at a time. Write a function count_k that figures out the number of paths for this scenario. Assume n and k are positive.
• 分析
  是经典台阶问题的进阶问题，需要考虑新的递归范式
  本人考虑的是如下递归规则：

跨越步数最大到了K + 跨越步数最大到k-1

其中 跨越步数最大到K 的部分考虑如下递归规则：

第一步跨越了第K步+第一步用其他步数但后面的最大步数到了K步

• 代码
  因为用了Q1编写的函数，先附上Q1的代码。Q1就是Q2中只能用1步和2步走对应的特殊情况。

def count_stair_ways(n):"""Returns the number of ways to climb up a flight ofn stairs, moving either 1 step or 2 steps at a time.>>> count_stair_ways(4)5"""
#     "*** YOUR CODE HERE ***"if n==1:return 1if n==2:return 2if n<=0:return 0else:return count_stair_ways(n-1)+count_stair_ways(n-2)

然后下面是本人写的Q2的代码，反正是过了题目给的四个简单测试，对不对也不清楚，大家可以一起探讨下

def count_k(n, k):""" Counts the number of paths up a flight of n stairswhen taking up to and including k steps at a time.>>> count_k(3, 3) # 3, 2 + 1, 1 + 2, 1 + 1 + 14>>> count_k(4, 4)8>>> count_k(10, 3)274>>> count_k(300, 1) # Only one step at a time1""""*** YOUR CODE HERE ***"def count_must_k(n,k):if n<k:return 0if n==k:return 1else:return_values = 0return_values += count_k(n - k, k)  # 1for i in range(k - 1):return_values += count_must_k(n - i - 1, k)# return_values+=count_k(k,k-1)*count_must_k(n-k,k)# return_values += count_k(n, k - 1)return return_values# return count_k(n,k)passif n==0:return 0if n==1:return 1if k==1:return 1if k==2:return count_stair_ways(n)if k>n:return count_k(n,n)if k==n:return 1+count_k(n,k-1)# 4 3if k<=0:return 0else:return_values=0return_values+=count_k(n-k,k) #1for i in range(k-1):return_values+=count_must_k(n-i-1,k)# return_values+=count_k(k,k-1)*count_must_k(n-k,k)return_values+=count_k(n,k-1)return return_values

可能能看到这的都是在国内念大学的萌新，这里推荐一个北大大佬写的CS学习建议，如果让我用一句话总结，那就是：CS只能自学（狗头狗头狗头

>