1. N皇后 II
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 9
皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
以下程序实现了这一功能，请你填补空白处内容：
```python
class Solution(object): def __init__(self): self.count = 0 def totalNQueens(self, n): self.dfs(0, n, 0, 0, 0) return self.count def dfs(self, row, n, column, diag, antiDiag): if row == n: self.count += 1 return for index in range(n): isColSafe = (1 << index) & column == 0 isDigSafe = (1 << (n - 1 + row - index)) & diag == 0 isAntiDiagSafe = (1 << (row + index)) & antiDiag == 0 if isAntiDiagSafe and isColSafe and isDigSafe: _________________________; if __name__ == '__main__': s = Solution() print (s.totalNQueens(4)) ```
出处：
https://edu.csdn.net/practice/25949963
代码：
class Solution(object): def __init__(self): self.count = 0 def totalNQueens(self, n): self.dfs(0, n, 0, 0, 0) return self.count def dfs(self, row, n, column, diag, antiDiag): if row == n: self.count += 1 return for index in range(n): isColSafe = (1 << index) & column == 0 isDigSafe = (1 << (n - 1 + row - index)) & diag == 0 isAntiDiagSafe = (1 << (row + index)) & antiDiag == 0 if isAntiDiagSafe and isColSafe and isDigSafe: self.dfs(row + 1, n, (1 << index) | column, (1 << (n - 1 + row - index)) | diag, (1 << (row + index)) | antiDiag) if __name__ == '__main__': s = Solution() print(s.totalNQueens(4)) s = Solution() print(s.totalNQueens(1))
输出：
2
1
2. 迷宫问题(递归)
问题描述：一只老鼠在一个n×n迷宫的入口处，它想要吃迷宫出口处放着奶酪，问这只老鼠能否吃到奶酪？如果可以吃到，请给出一条从入口到奶酪的路径。
思考：解决问题之前，我们首先要做的就是仔细研究问题，找出问题的已知条件和要得到的是什么。和解数学问题、物理问题一样要先弄懂问题。那么，老鼠走迷宫问题的已知条件有什么呢？
数学模型重新定义问题：
问题：问老鼠能否吃到奶酪就是问能否找到一条从迷宫入口到出口的路径。如果不能找到，那么老鼠就吃不到奶酪；如果能够找到，那么就给出这条路径。
观察10×10的迷宫。这个迷宫其实是由10×10=100个格子组成的，其中绿色格子代表墙，白色格子代表路，如图（1）所示。
“绿色格子代表墙，白色格子代表路”是用语言形式描述的，需要转换成数学的形式。用1和0分别定义绿色格子和白色格子，可以得到如图（2）的迷宫。
将上面10×10的迷宫定义为如下的二维数组，即
m[10][10]=[
[1,1,1,0,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,1,1],
[1,0,1,1,1,1,1,0,0,1],
[1,0,1,0,0,0,0,1,0,1],
[1,0,1,0,1,1,0,0,0,1],
[1,0,0,1,1,0,1,0,1,1],
[1,1,1,1,0,0,0,0,1,1],
[1,0,0,0,0,1,1,1,0,0],
[1,0,1,1,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]
有了对迷宫的数学定义，就可以很简单的定义迷宫的入口和出口了。迷宫的入口是m[0][3]，出口是m[7][9]。老鼠走迷宫问题就是要找一条从入口到出口的路径，如果存在就返回这条路径；如果不存在，就返回不存在这种路径。也就是说，要在二维数组m中找一条从m[0][3]到m[7][9]全部为0的路径。 请使用递归解决迷宫路径查找问题。
以下程序实现了这一功能，请你填补空白处内容：
```python
def maze(m, n, route, pos, export):
"""走迷宫 m - 迷宫数组，列表 n - 迷宫阶数 route - 可能的路线，列表 pos - 当前位置，元组 export - 出口位置，元组 """ route.append(pos) if pos == export: print(route) if pos[0] > 0 and m[pos[0]-1][pos[1]] == 0 and (pos[0]-1,pos[1]) not in route: maze(m, n, route[:], (pos[0]-1,pos[1]), export) if pos[0] < n-1 and m[pos[0]+1][pos[1]] == 0 and (pos[0]+1,pos[1]) not in route: maze(m, n, route[:], (pos[0]+1,pos[1]), export) if pos[1] > 0 and m[pos[0]][pos[1]-1] == 0 and (pos[0],pos[1]-1) not in route: maze(m, n, route[:], (pos[0],pos[1]-1), export) ________________________________; m = [ [1,1,1,0,1,1,1,1,1,1], [1,0,0,0,0,0,0,0,1,1], [1,0,1,1,1,1,1,0,0,1], [1,0,1,0,0,0,0,1,0,1], [1,0,1,0,1,1,0,0,0,1], [1,0,0,1,1,0,1,0,1,1], [1,1,1,1,0,0,0,0,1,1], [1,0,0,0,0,1,1,1,0,0], [1,0,1,1,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1,1]] maze(m, len(m), list(), (0,3), (7,9)) ```
出处：
https://edu.csdn.net/practice/25949964
代码：
def maze(m, n, route, pos, export): """走迷宫 m - 迷宫数组，列表 n - 迷宫阶数 route - 可能的路线，列表 pos - 当前位置，元组 export - 出口位置，元组 """ route.append(pos) if pos == export: print(route) if pos[0] > 0 and m[pos[0]-1][pos[1]] == 0 and (pos[0]-1,pos[1]) not in route: maze(m, n, route[:], (pos[0]-1,pos[1]), export) if pos[0] < n-1 and m[pos[0]+1][pos[1]] == 0 and (pos[0]+1,pos[1]) not in route: maze(m, n, route[:], (pos[0]+1,pos[1]), export) if pos[1] > 0 and m[pos[0]][pos[1]-1] == 0 and (pos[0],pos[1]-1) not in route: maze(m, n, route[:], (pos[0],pos[1]-1), export) if pos[1] < n-1 and m[pos[0]][pos[1]+1] == 0 and (pos[0],pos[1]+1) not in route: maze(m, n, route[:], (pos[0],pos[1]+1), export) if __name__ == '__main__': m =[[1,1,1,0,1,1,1,1,1,1], [1,0,0,0,0,0,0,0,1,1], [1,0,1,1,1,1,1,0,0,1], [1,0,1,0,0,0,0,1,0,1], [1,0,1,0,1,1,0,0,0,1], [1,0,0,1,1,0,1,0,1,1], [1,1,1,1,0,0,0,0,1,1], [1,0,0,0,0,1,1,1,0,0], [1,0,1,1,0,0,0,0,0,1], [1,1,1,1,1,1,1,1,1,1]] maze(m, len(m), list(), (0,3), (7,9))
输出：
[(0, 3), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (2, 7), (2, 8), (3, 8), (4, 8), (4, 7), (5, 7), (6, 7), (6, 6), (6, 5), (6, 4), (7, 4), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8), (7, 8), (7, 9)]
3. 体操比赛成绩统计
体操比赛成绩统计。多名运动员，多个评委打分，去掉一个最高分和去掉一个最低分，对其余分数求平均分作为一个运动员成绩。
编程通过键盘输入每位运动员编号和每个评委的成绩，求出运动员的最终成绩，并将运动员编号和最终成绩保存在一个字典中，形如{编号1:最终成绩1,学号2:最终成绩2.....，并将结果输出。
出处：
https://edu.csdn.net/practice/25949965
代码：
t = int(input('请输入评委人数（不得少于3人）：')) s = int(input('请输入学生人数（不得少于1人）：')) stus = [] for i in range(s): stu = {'score':[]} stu.update({'sn':str(input('----\n请输入学生学号：'))}) for j in range(t): stu['score'].append(input('请输入评委'+str(j+1)+'的评分：')) stu['score'].sort() stu.update({'min':stu['score'].pop(0)}) stu.update({'max':stu['score'].pop()}) stu.update({'avg':eval('+'.join(stu['score']))/len(stu['score'])}) stus.append(stu) r = {n['sn']:n['avg'] for n in stus} print(r)
输出：
略
