问题 A: 简单递归求和
题目描述
使用递归编写一个程序求如下表达式前n项的计算结果： (n<=100)
1 - 3 + 5 - 7 + 9 - 11 +......
输入n，输出表达式的计算结果。
输入
多组输入，每组输入一个n，n<=100。
输出
输出表达式的计算结果。
样例输入 Copy
1 2
样例输出 Copy
1 -2
def sum_odd_numbers(n):
if n == 1:
return 1
else:
return ((-1)**(n+1))*(2 * n - 1) + sum_odd_numbers(n - 1)
while True:
n = int(input())
print(sum_odd_numbers(n))问题 B: 文件存储
题目描述
如果有n个文件{F1,F2,F3,…,Fn}需要存放在大小为M的U盘中，文件i的大小为Si，1<=i<=n。请设计一个算法来提供一个存储方案，使得U盘中存储的文件数量最多。
输入
多组输入，对于每组测试数据，每1行的第1个数字表示U盘的容量M（以MB为单位，不超过256*1000MB），第2个数字表示待存储的文件个数n。
第2行表示待存储的n个文件的大小（以MB为单位）。
输出
输出最多可以存放的文件个数。
样例输入 Copy
10000 5 2000 1000 5000 3000 4000
样例输出 Copy
4
while True:
m,n = map(int,input().split())
lst=list(map(int,input().split()))
lst.sort()
num = 0
if sum(lst)<m:
print(len(lst))
else:
for i in range(len(lst)):
num += lst[i]
if num == m:
print(i+1)
break
else:
if num>m:
print(i)
break问题 C: 图的m着色问题
题目描述
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色，请输出着色方案。
输入
输入第一行包含n，m，k分别代表n个结点，m条边，k种颜色，接下来m行每行有2个数u，v表示u和v之间有一条无向边,可能出现自环边，所以请忽略自环边。
输出
输出所有不同的着色方案，且按照字典序从小到大输出方案。
样例输入 Copy
3 3 3 1 2 1 3 2 3
样例输出 Copy
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
# 定义函数用于检查着色是否合法
def is_valid_coloring(graph, colors, node, color):
for neighbor in graph[node]: # 遍历节点的所有邻居
if colors[neighbor] == color: # 如果邻居节点已经着色并且颜色与当前节点相同
return False # 该着色方案不合法
return True # 所有邻居节点都没有与当前节点相同的颜色，着色方案合法
# 定义深度优先搜索函数对图进行着色
def color_graph(graph, colors, node, m, k, all_colorings):
if node == len(graph): # 如果所有节点都已经着色完成
all_colorings.append(colors[:]) # 将合法的着色方案加入结果列表
return
for color in range(1, k+1): # 遍历所有颜色
if is_valid_coloring(graph, colors, node, color): # 检查是否可以使用该颜色着色
colors[node] = color # 着色
color_graph(graph, colors, node + 1, m, k, all_colorings) # 递归继续着色下一个节点
colors[node] = 0 # 回溯，将该节点重新置为未着色状态
while 1:
n, m, k = map(int, input().split())
graph = [[] for _ in range(n)] # 初始化图的邻接表
for _ in range(m):
u, v = map(int, input().split())
graph[u-1].append(v-1) # 无向图，双向加边
graph[v-1].append(u-1)
colors = [0] * n # 初始化颜色列表
all_colorings = [] # 用于存放所有合法的着色方案
# 调用深度优先搜索函数进行着色
color_graph(graph, colors, 0, m, k, all_colorings)
# 输出所有合法的着色方案
for coloring in all_colorings:
print(*coloring)问题 D: N皇后问题
题目描述
使用回溯法求解N后问题。
输入
皇后的个数。
输出
每一种方案及总方案数。
样例输入 Copy
4
样例输出 Copy
0 1 0 0 0 0 0 2 3 0 0 0 0 0 4 0 ---------------- 0 0 1 0 2 0 0 0 0 0 0 3 0 4 0 0 ---------------- 总方案数为：2
我的代码，oj上运行是错的，不知道为什么
def is_valid(board, row, col):
# 检查同一列和对角线是否有皇后
for i in range(row):
if board[i] == col or abs(i - row) == abs(board[i] - col):
return False
return True
def solve_n_queens(board, row, solutions, n):
if row == n:
solutions.append(board[:]) # 找到一个解
else:
for col in range(n):
if is_valid(board, row, col):
board[row] = col # 放置皇后
solve_n_queens(board, row + 1, solutions, n) # 继续处理下一行
def print_solutions(solutions):
total = len(solutions)
for solution in solutions:
for row, col in enumerate(solution): # 枚举每一行和列
row_str = ["0"] * len(solution) # 每一行都是N个0
row_str[col] = str(row + 1) # 将皇后所在列的对应位置改为行号
print(" ".join(row_str))
print("----------------")
print("总方案数为：", total)
# 其他代码保持不变
n = int(input())
board = [-1] * n # 初始化棋盘，-1表示该行还没有放置皇后
solutions = [] # 存放所有解
solve_n_queens(board, 0, solutions, n)
print_solutions(solutions)
def dfs(row, n):
global count
if row == n:
for i in range(n):
for j in range(len(res[i])):
print(res[i][j], end=" ")
print()
print("----------------")
count += 1
for j in range(n):
if col[j] and dg[j + row] and udg[j + n - row]:
col[j], dg[j + row], udg[j + n - row] = False, False, False
res[row][j] = row + 1
dfs(row + 1, n)
col[j], dg[j + row], udg[j + n - row] = True, True, True
res[row][j] = 0
n = int(input())
col = [True] * n
dg, udg = [True] * (2 * n), [True] * (2 * n)
res = [[0] * n for _ in range(n)]
count = 0
dfs(0, n)
print("总方案数为：" + str(count))问题 E: 马的遍历问题
题目描述
在5*4的棋盘中，马只能走斜“日”字。马从位置(x, y)处出发，把棋盘的每一格都走一次，且只走一次，请找出所有路径。
输入
x,y，表示马的初始位置。
输出
将每一格都走一次的路径总数，如果不存在该路径则输出“No solution!”。
样例输入 Copy
1 1 2 2
样例输出 Copy
32 No solution!
#是否走过，棋盘
a = []
#保存路径条数
s = 0
#剪枝函数
def check(x, y):
#不在棋盘里或者走过的剪掉
if 1 <= x <= 5 and 1 <= y <= 4 and a[x][y] == 0:
return True
else:
return False
def solve(x, y, step):
global s
if step == 20:
s += 1
return
#方向引导数组
fx = [1, 2, 2, 1, -1, -2, -2, -1]
fy = [2, 1, -1, -2, -2, -1, 1, 2]
for i in range(8):
dx = x + fx[i]
dy = y + fy[i]
if check(dx, dy):
a[x][y] = step
solve(dx, dy, step + 1)
a[x][y] = 0
while True:
try:
a = [[0] * 10 for _ in range(10)]
x, y = map(int, input().split())
for i in range(1, 6):
for j in range(1, 6):
a[i][j] = 0
s = 0
#从第一步开始
solve(x, y, 1)
if s == 0:
print("No solution!")
else:
print(s)
except EOFError:
break问题 F: 素数环
题目描述
现有1,2,3...,n，要求用这些数组成一个环，使得相邻的两个整数之和均为素数，要求你求出这些可能的环。
输入
输入正整数n。
输出
输出时从整数1开始逆时针输出，同一个环只输出一次,且满足条件的环应按照字典序从小到大输出。
注：每一个环都从1开始。
注：每一个环都从1开始。
样例输入 Copy
6
样例输出 Copy
1 4 3 2 5 6 1 6 5 2 3 4
number = [0] * 200
n = 0
def solve(t):
if t >= n:
if sushu(1 + number[n - 1]) == 1:
for i in range(n):
print(number[i], end=' ')
print()
else:
for i in range(2, n + 1):
number[t] = i
if check(t):
solve(t + 1)
def check(t):
for i in range(t):
if sushu(number[t - 1] + number[t]) == 0 or number[t] == number[i]:
return 0
return 1
def sushu(x):
if x == 1:
return 0
for i in range(2, int(x**0.5) + 1):
if x % i == 0:
return 0
return 1
number[0] = 1
try:
while True:
n = int(input())
solve(1)
except EOFError:
pass
