pta递归

### PTA 平台上递归问题的示例与解法 #### 示例 1：爬楼梯问题 在爬楼梯问题中，给定一个正整数 `n` 表示楼梯的阶数，每次可以选择爬 1 阶或者 2 阶。目标是计算有多少种不同的方法可以到达楼顶。 这是一个典型的动态规划和递归问题。通过观察发现，当站在第 `i` 层台阶时，可以从第 `i-1` 或者第 `i-2` 跳过来。因此状态转移方程为： \[ f(i) = f(i-1) + f(i-2) \] 其中 \(f(0)=1\) 和 \(f(1)=1\) 是初始条件[^1]。 以下是基于递归的方法实现： ```python def climbStairs(n): if n == 0 or n == 1: return 1 return climbStairs(n - 1) + climbStairs(n - 2) print(climbStairs(2)) # 输出：2 ``` 虽然上述代码简单明了，但由于存在大量重复计算，时间复杂度较高。为了优化性能，可采用记忆化搜索或自底向上的迭代方式。 --- #### 示例 2：按位操作 对于两个无符号短整型数 `a` 和 `b`，需要分别求出它们的按位与、按位或、左移右移以及按位取反的结果。此问题主要考察基础的二进制运算能力[^2]。 下面展示如何利用 Python 实现这些功能： ```python def bitwise_operations(a, b): and_result = a & b or_result = a | b left_shift = a << b right_shift = a >> b not_a = ~a return (and_result, or_result, left_shift, right_shift, not_a) result = bitwise_operations(5, 1) for r in result: print(r) ``` 注意，在实际应用过程中需确保输入数值范围有效以免溢出等问题发生。 --- #### 示例 3：全排列生成器 PTA 浙大版《数据结构（第二版）》中有这样一道编程练习题——输出指定长度数组的所有可能排列组合情况[^3]。由于不知道具体循环次数，故而适合运用递归来完成任务。 算法思路如下所示： 1. 如果当前序列为空，则返回空列表； 2. 否则遍历每一个元素作为首项，并对其余部分调用函数本身得到剩余子串的所有排列形式； 3. 将第一步选取出来的那个固定位置加上每一种后续可能性构成新的整体方案加入最终集合当中去； 下面是具体的Python代码片段： ```python def permute(nums): res = [] # 边界条件处理 if len(nums) == 0: return [[]] for i in range(len(nums)): current_num = nums[i] remaining_list = nums[:i] + nums[(i+1):] sub_permutations = permute(remaining_list) for p in sub_permutations: res.append([current_num]+p) return res example_input=[1,2,3] output=permute(example_input) print(output) ``` 运行以上脚本将会打印出由三个不同数字组成的全部六组互不相同的顺序安排情形。 --- #### 示例 4：八皇后问题 八皇后问题是另一个经典例子，它询问的是能否在一个标准国际象棋盘上面摆放八个互相不会威胁到对方的皇后来达成目的[^4]。该挑战既可以用回溯法也可以借助栈模拟过程来进行解答。 这里给出一段简洁优雅版本的伪码描述整个逻辑流程： ```pseudo function solveNQueens(boardSize): solutions := empty list of boards placeQueen(rowIndex, boardState): if rowIndex >= boardSize then add copyOfBoardToSolutions() else foreach col from 0 to boardSize do if isValidPosition(col,rowIndex) then markCellAsOccupiedAndCallNextRow() initializeEmptyChessboardOfSizeN() placeQueen(startingAtFirstRow(), initialConfiguration()) return allFoundConfigurationsInListForm() ``` 转换成真实语言后即可获得完整的解决方案。 ---