python作业

1.某个人进入如下一个棋盘中，要求从左上角开始走，
?? ?最后从右下角出来（要求只能前进，不能后退），
?? ?问题：共有多少种走法？
?? ?
?? ?0 0 0 0 0 0 0 0

?? ?0 0 0 0 0 0 0 0

?? ?0 0 0 0 0 0 0 0

?? ?0 0 0 0 0 0 0 0

?? ?0 0 0 0 0 0 0 0

代码如下

def a(m, n):

? ? dp = [[0] * n for _ in range(m)] ?# 创建一个m行n列的二维数组，并初始化为0

? ? for i in range(m):

? ? ? ? for j in range(n):

? ? ? ? ? ? if i == 0 or j == 0:

? ? ? ? ? ? ? ? dp[i][j] = 1 ?# 将第一行和第一列的值设为1，表示只有一种走法

? ? ? ? ? ? else:

? ? ? ? ? ? ? ? dp[i][j] = dp[i-1][j] + dp[i][j-1] ?# 根据状态转移方程计算dp[i][j]的值

? ? return dp[m-1][n-1]

m = 5 ?# 棋盘的行数

n = 8 ?# 棋盘的列数

print(a(m, n)) ?# 输出结果a

2.

作业2：
?? ?输入一行符号，以#结束，判断其中的对称符号是否匹配。对称符号包括：
?? ?{ } 、 [ ] 、 ( )、 < >

?? ?如果对称符号能够实现中间对称，则输出yes
?? ?否则输出no
?

代码如下

def zhan(symbols):

? ? stack = [] ?# 创建一个栈来存储左括号

? ? symbol_dict = {']': '[', '}': '{', ')': '(', '>': '<'} ?# 符号映射关系

? ? for symbol in symbols:

? ? ? ? if symbol in {'{', '[', '(', '<'}:

? ? ? ? ? ? stack.append(symbol) ?# 遇到左括号时将其压入栈中

? ? ? ? elif symbol in {'}', ']', ')', '>'}:

? ? ? ? ? ? if not stack or stack[-1] != symbol_dict[symbol]:

? ? ? ? ? ? ? ? return "no" ?# 如果栈为空或栈顶括号与当前右括号不匹配，则返回"no"

? ? ? ? ? ? stack.pop() ?# 栈顶括号与当前右括号匹配，将栈顶括号弹出

? ? if not stack:

? ? ? ? return "yes" ?# 遍历结束后栈为空，表示所有的对称符号都匹配

? ? else:

? ? ? ? return "no" ?# 栈不为空，表示有未匹配的对称符号

symbols = input("请输入一行符号：")

print(zhan(symbols))

3.给定一个包含n+1个整数的数组nums，其数字在1到n之间（包含1和n），
?? ?可知至少存在一个重复的整数，假设只有一个重复的整数，
?? ?请找出这个重复的数

代码如下

def findDuplicate(nums): ? ? ? ? ?#定义一个查找重复

? ? slow = fast = nums[0]

? ? while True:

? ? ? ? slow = nums[slow] ?# 慢指针每次移动一步

? ? ? ? fast = nums[nums[fast]] ?# 快指针每次移动两步

? ? ? ? if slow == fast:

? ? ? ? ? ? break

? ? fast = nums[0] ?# 将快指针重新指向数组的第一个元素

? ? while fast != slow:

? ? ? ? fast = nums[fast]

? ? ? ? slow = nums[slow]

? ? return slow

nums = [1, 3, 4, 2, 2] ?# 示例输入

print(findDuplicate(nums)) ?# 输出结果