算法分析基础上机题目
1.旅行商问题
【问题描述】
假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
【输入形式】
城市数目,以及城市之间的距离
【输出形式】
所有路径之中的最小值
【样例输入】
4
0,10,15,20
10,0,35,25
15,35,0,30
20,25,30,0
【样例输出】
80
【样例说明】
第一行说明有4个城市;第2至5行说明一个城市与其他城市的距离,其中城市到其自身的距离为0,不可达的城市之间的距离为0。
思路
数据较小,直接全排列枚举所有方案
代码
from itertools import permutations
n = int(input())
ls = []
for i in range(n):
ls.append([int(x) for x in input().split(',')])
def tsp(n, ls):
cities = [i for i in range(n)]
res = float('inf')
for path in permutations(cities):
distance = 0
for i in range(n):
distance += ls[path[i - 1]][path[i]]
res = min(res, distance)
return res
print(tsp(n, ls))
2.邮局选址问题
【问题描述】
对一个以XY轴表达的城市里,n个居民点散乱分布,居民点位置可以用坐标(x,y)表示,任意两点(x1,y1)(x2,y2)间距离可以用| x1-x1|+|y1-y2|度量,居民希望在城市中选择建立邮局的最佳位置,使得n个居民点到邮局的距离总和最小
【输入形式】
居民点数目,以及居民点的坐标
【输出形式】
最小的距离总和
【样例输入】
3
3 3
1 6
4 9
【样例输出】
9
思路
贪心的思想,首先这个问题可以将横纵坐标分开考虑,对答案没影响,则问题转换为在一维坐标轴上面选择一个点,使得所有点到它的距离加起来最小。
放到最中间距离最小,因为假设有两个点AB,需要放置C点,如下:
A C B
A B C
显然放中间距离为AB,放两边距离为AB+BC/AC
代码
n = int(input())
a, b = [], []
for i in range(n):
x, y = map(int, input().split())
a.append(x)
b.append(y)
## 排序
a.sort()
b.sort()
res = 0 ## 最优的选择就是放中间
for i in range(n):
res += abs(a[i] - a[n // 2]) + abs(b[i] - b[n // 2])
print(res)
3.最优合并问题
【问题描述】
给定k个排好序的序列s1,s2,…,sk,用2路合并算法将这k个序列合并成一个序列。假设所采用的2路合并算法合并两个长度分别为m和n的序列需要m+n-1次比较。试设计一个算法确定合并这个序列的最优合并顺序,使所需要的总比较次数最少。
【输入形式】
序列数目,以及各个序列中的元素数目。
【输出形式】
最少的总比较次数
【样例输入】
4
5 12 11 2
【样例输出】
52
思路
贪心的思想:使用一个优先队列,每次从队列中取出两个最小的序列进行合并,再将得到的结果插入到优先队列中去。
代码
import heapq
n = int(input())
ls = [int(x) for x in input().split(' ')]
priority_queue = []
for i in ls: heapq.heappush(priority_queue, i)
res = 0
while len(priority_queue) > 1:
a = heapq.heappop(priority_queue)
b = heapq.heappop(priority_queue)
res += a + b - 1
heapq.heappush(priority_queue, a + b)
print(res)
4.堆排序
###【问题描述】
排序问题: 给定一个无序序列,采用”堆排序“方法对序列升序排序。
【输入形式】
无序的整数序列
【输出形式】
升序的整数序列
【样例输入】
12,11,13, 5, 6,7
【样例输出】
5, 6, 7,11,12,13
【样例说明】
以逗号隔开的序列, 程序内需要转化为整数序列
思路
堆的性质
- 堆中某个节点的值总是不大于或不小于其父节点的值;
- 堆总是一棵完全二叉树。
- 最后一个非叶结点是第n/2个结点。这里建堆的时候会用到,复杂度可以降到O(n);
- 如果一个点为u,那么它的左儿子为2u,右儿子为2u+1
- 对于小根堆来讲,每个以u为根节点的树,它的左右儿子的值一定大于父节点。所以对堆进行建立的时候,如果当前点与它的左右儿子并不满足这一性质,就需要进行交换。
- 小根堆:子节点比父节点大
- 大根堆:子节点比父节点小
显然这里是升序,因此需要小根堆
代码
## 堆排序
def heapify(ls, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and ls[i] < ls[l]:
largest = l
if r < n and ls[largest] < ls[r]:
largest = r
if largest != i:
ls[i], ls[largest] = ls[largest], ls[i]
heapify(ls, n, largest)
def heapSort(ls):
n = len(ls)
for i in range(n, -1, -1):
heapify(ls, n, i)
for i in range(n - 1, 0, -1):
ls[i], ls[0] = ls[0], ls[i]
heapify(ls, i, 0)
ls = [int(x) for x in input().split(",")]
heapSort(ls)
print(",".join(str(x) for x in ls))
5.布线问题
苏科大的sb输入输出数据,题目描述的输入输出和答案数据全是乱的。
【问题描述】
印刷电路板将布线区域划分成n*m个方格,精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案。在布线时,电路只能沿直线或直角布线。为了避免线路相交,已经布了线的方格不允许其他线穿过。对给定的电路板,找出最短的布线路径。
【输入形式】
方阵的行数、列数、布线区域方阵(其中不能通过的地方输入1,能通过的地方输入0)、起点坐标、终点坐标
【输出形式】
线路长度以及线路包含的方格坐标
【样例输入】
6 6
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 1 0
0 0 0 1 1 0
1 0 0 0 1 0
1 1 1 0 0 0
1 2
4 3
【样例输出】
4
1,2 > 2,2 > 3,2 > 4,2 > 4,3
【样例说明】
第1行输入方阵的行数、列数
第2-7行输入方阵元素,不能通过的地方输入1,能通过的地方输入0
第8行输入起点坐标
第9行输入终点坐标
所有元素用空格分隔, 且坐标索引从1开始!!
思路
思路很简单,就是BFS求最短路,只不过需要输出路径,那就记录前一个节点,最后回溯回去就可以
代码
import queue
## 输入地图大小
n, m = map(int, input().split())
## 初始化地图
g = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(n):
g[i + 1] = [0]+[int(x) for x in input().split()]
## 输入起点和终点
start = tuple(map(int, input().split()))
end = tuple(map(int, input().split()))
## 初始化距离和状态数组,以及父节点数组
dist = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
st = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
father = [[(0, 0) for _ in range(m + 1)] for _ in range(n + 1)]
## BFS 队列初始化,加入起点
q = queue.Queue()
q.put(start)
st[start[0]][start[1]] = 1
flag = False
while not q.empty() and not flag:
## 弹出队首元素
t = q.get()
## 枚举四个方向
for i in range(4):
x = t[0] + [-1, 1, 0, 0][i]
y = t[1] + [0, 0, -1, 1][i]
## 判断是否越界或者障碍物已经被标记
if x < 1 or x > n or y < 1 or y > m:
continue
if g[x][y] == 0 and st[x][y] == 0:
## 如果可以走,则加入队列,更新距离,标记状态,记录父节点
q.put((x, y))
dist[x][y] = dist[t[0]][t[1]] + 1
st[x][y] = 1
father[x][y] = (t[0], t[1])
## 判断是否到达终点
if (x, y) == end:
flag = True
break
## 输出最短路距离
print(dist[end[0]][end[1]])
## 再次 BFS,打印路径
path = [end]
x = end[0]
y = end[1]
while (x, y) != start:
## 获取当前点的父节点
x, y = father[x][y]
path.append((x, y))
## 反转路径,并输出
path.reverse()
for i in range(len(path)):
if i == len(path) - 1:
print("{},{}".format(path[i][0], path[i][1]))
else:
print("{},{}".format(path[i][0], path[i][1]), end="-->")
其他三个测试数据如下:
由第一个数据看出
## 测试数据1
6 6
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 1 0
0 0 0 1 1 0
1 0 0 0 1 0
1 1 1 0 0 0
1 2
4 3
## 输出
4
1,2-->2,2-->3,2-->4,2-->4,3
## 测试数据2
6 6
1 1 1 1 0 0
0 0 0 0 1 0
0 0 0 1 1 0
1 0 0 0 0 0
1 1 1 0 0 0
3 1
3 6
## 输出
9
3,1-->4,1-->4,2-->5,2-->5,3-->5,4-->5,5-->5,6-->4,6-->3,6
## 测试数据3
4 4
0 1 0 0
0 1 0 1
0 0 0 0
0 0 1 1
1 1
1 4
## 输出
7
1,1-->2,1-->3,1-->3,2-->3,3-->2,3-->1,3-->1,4
6.汽车加油问题
第二个测试数据最后莫名其妙加一些空格
【问题描述】
一辆汽车加满油后可以行驶n千米。旅途中有k个加油站。若要使沿途的加油次数最少,设计一个有效的算法,采用贪心算法,编程计算并输出最少加油次数,以及指出应在那些加油站停靠加油。
【输入形式】
两行标准输入,数字通过空格分隔
【输出形式】
将编程计算出的最少加油次数,以及哪些加油站,输出到文件ouput.txt。如果无法到达目的地,则输出“No Solution”。
【样例输入】
7 7
1 2 3 4 5 1 6 6
【样例输出】
4
3 4 6 7
【样例说明】
第一行标准输入有2个正整数n和k,表示汽车加满油后可行驶n km,且旅途中有k个加油站。
第二行标准输入有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地,汽车已加满油。第k+1个加油站表示目的地。
思路
贪心,如果序列中有一个大于n了,那么说明肯定到不了,否则一定有解,因为最坏的情况就是每站都加
可以开一个变量s,记录当前已经跑了多远了,如果加上下一站还够的话,就继续跑,否则就在本站加油
代码
## 输入s,去除末尾空格
s = input().rstrip()
n, k = map(int, s.split(" "))
ls = [0] + [int(x) for x in input().split(" ")]
## 汽车加油问题
flag = True
for i in ls:
if i > n:
flag = False
break
if flag:
res = 0
s = 0
ans = []
for i in range(k + 1):
if s + ls[i + 1] > n:
ans.append(i)
res += 1
s = 0
s += ls[i + 1]
print(res)
for i in ans:
print(i, end=" ")
else:
print("No Solution")
7.最大团问题
【问题描述】
给定一个无向图G=(V,E),若U为V子集,请对任意的顶点u, v为U的元素,有边(u,v)为E元素,则称U为G的一个完全子图。G的完全子图U是一个团,当且仅当U不包含在G的更大的完全子图中。G的最大团则指包含定点数最多的团。对给定的无向图,找出最大团中顶点的个数。
【输入形式】
G的邻接矩阵
【输出形式】
第一行输出最大团顶点个数,第二行输出最大团中的顶点
【样例输入】
0,1,1,0,0
1,0,1,1,1
1,1,0,1,1
0,1,1,0,1
0,1,1,1,0
【样例输出】
最大团顶点个数: 4
最大团为: [0, 1, 1, 1, 1]
【样例说明】
输入的邻接矩阵表明图中有5个顶点,矩阵元素为1,则行、列对应的顶点有边相连,否则没有边相连。矩阵元素之间通过逗号隔开。举例:假设5个顶点分别为ABCDE,那么A与B、C相连。最终求得,最大团中包含4个节点,为BCDE。
完全图
任意两点都恰有一条边相连的图,n个顶点的图中有 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1) 条边。
完全子图(团)
任意两点都恰好有一条边相连的子图,也叫团。
思路
每次看当前点u如果他和最大团中的点没有边的话就不加,如果都有边的话,那么就加进去。
代码
graph = []
while True:
try:
graph.append(list(map(int, input().split(","))))
except:
break
n = len(graph[0])
## 用于存储最大团的点集
ans = [0 for _ in range(n)]
## 用于存储当前团的点集
st = [0 for _ in range(n)]
res = 1
def dfs(u, num):
global res, ans, n
if u == n:
if num > res:
res = num
ans = st[:]
return
flag = True
for i in range(n):
if st[i] == 1 and graph[u][i] == 0:
flag = False
break
if flag:
st[u] = 1
dfs(u + 1, num + 1)
st[u] = 0
dfs(u + 1, num)
else:
dfs(u + 1, num)
dfs(0, 0)
print("最大团顶点个数: {}".format(res))
print("最大团为: {}".format(ans))
三组测试数据如下
## Test1
0, 1, 1, 0, 0
1, 0, 1, 1, 1
1, 1, 0, 1, 1
0, 1, 1, 0, 1
0, 1, 1, 1, 0
## Result1
最大团顶点个数: 4
最大团为: [0, 1, 1, 1, 1]
## Test2
0, 1, 1, 1
1, 0, 1, 1
1, 1, 0, 1
1, 1, 1, 0
## Result2
最大团顶点个数: 4
最大团为: [1, 1, 1, 1]
## Test3
0, 1, 0, 0, 0, 1
1, 0, 1, 1, 1, 1
0, 1, 0, 1, 1, 0
0, 1, 1, 0, 1, 0
0, 1, 1, 1, 0, 1
1, 1, 0, 0, 1, 0
## Result3
最大团顶点个数: 4
最大团为: [0, 1, 1, 1, 1, 0]
8.最长公共子序列问题
【问题描述】
若给定序列X={x1,x2,…,xm},则另一序列Z={z1,z2,…,zk},是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有:zj=xij。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。如果给定2个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。现给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},要求使用动态规划算法思想,找出X和Y的最长公共子序列。
【输入形式】
输入以空格分割的字符,第一行对应第一条序列,第二行对应第二条序列。
【输出形式】
字符数组形式的最长公共子序列。
【样例输入】
z x y
x y y
【样例输出】
['x', 'y']
【样例说明】
第一行输入为第一条序列,包含z x y三个字符;输出为最长公共子序列,包含两个字符,以数组形式输出。
思路
动态规划:
- 状态表示:
dp[i][j]
表示a的[0i]和b的[0j]的最长公共子序列的长度的最大值 - 状态计算:
- 如果a[i]==a[j],则
dp[i][j]=dp[i-1][j-1]+1
- 否则,
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
- 如果a[i]==a[j],则
代码
a = input().split()
b = input().split()
n, m = len(a), len(b)
## dp[i][j]表示a[0:i]和b[0:j]的最长公共子序列长度
dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]: ## a[i - 1]和b[j - 1]相等,那么dp[i][j]就是dp[i - 1][j - 1] + 1
dp[i][j] = dp[i - 1][j - 1] + 1
else: ## a[i - 1]和b[j - 1]不相等,那么dp[i][j]就是dp[i - 1][j]和dp[i][j - 1]的最大值
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
## 回溯 输出最长公共子序列
res = []
i = n
j = m
while i > 0 and j > 0:
if a[i - 1] == b[j - 1]: ## a[i - 1]和b[j - 1]相等,那么a[i - 1]就是最长公共子序列的一个元素
res.append(a[i - 1])
i -= 1
j -= 1
elif dp[i - 1][j] > dp[i][j - 1]: ## a[i - 1]和b[j - 1]不相等,那么dp[i][j]就是dp[i - 1][j]和dp[i][j - 1]的最大值
i -= 1
else:
j -= 1
res.reverse()
print(res)
9.棋盘覆盖问题
【问题描述】
给定一个2k×2k的棋盘(具体图例见教材),有一个特殊棋格,拥有一个特殊棋格的棋盘称为特殊棋盘。现要用四种L型骨牌(具体图例见教材)覆盖特殊棋盘上除特殊棋格外的全部棋格,不能重叠,找出覆盖方案。
【输入形式】
在屏幕上输入棋盘大小及特殊方格所在行号和列号
【输出形式】
输出使用L型骨牌进行棋盘覆盖结果
【样例输入】
2
1 2
【样例输出】
2 -1 3 3
2 2 1 3
4 1 1 5
4 4 5 5
【样例说明】
输入:第一行输入整数k表示棋盘大小为2的k次幂,若k为2,则棋盘大小为4行4列;第二行输入特殊方格所在的行号和列号,以空格分隔
输出:使用L型骨牌进行棋盘覆盖结果,由3个相同的数表示同一个L型骨牌,不同的骨牌用不同的数字表示。数字的大小表示棋盘覆盖的顺序。特殊方格在棋盘的第1行第2列,用-1表示。各整数间以空格分隔。文章来源:https://www.toymoban.com/news/detail-721534.html
思路
使用数学归纳法可知这个问题一定有解,因此可以将整个棋盘分为四个部分,因为有障碍物的那个部分一定是有解的,我们可以把剩下的三个棋盘每个棋盘在切开的位置都看成有障碍物,因此剩下的三个棋盘就都有解了,在3个看成障碍物的地方可以使用一个L型进行覆盖文章来源地址https://www.toymoban.com/news/detail-721534.html
代码
k = int(input())
obstacle = tuple(map(int, input().split()))
board = [[0 for _ in range(2 ** k)] for _ in range(2 ** k)]
board[obstacle[0]-1][obstacle[1]-1] = -1
## 每个放置的L都需要自己的编号
cnt = 1
def chessboard(board, tr, tc, dr, dc, size):
global cnt
if size == 1:
return
s = size // 2
t = cnt
cnt += 1
## 覆盖左上角子棋盘
if dr < tr + s and dc < tc + s:
chessboard(board, tr, tc, dr, dc, s)
else:
board[tr + s - 1][tc + s - 1] = t
chessboard(board, tr, tc, tr + s - 1, tc + s - 1, s)
## 覆盖右上角子棋盘
if dr < tr + s and dc >= tc + s:
chessboard(board, tr, tc + s, dr, dc, s)
else:
board[tr + s - 1][tc + s] = t
chessboard(board, tr, tc + s, tr + s - 1, tc + s, s)
## 覆盖左下角子棋盘
if dr >= tr + s and dc < tc + s:
chessboard(board, tr + s, tc, dr, dc, s)
else:
board[tr + s][tc + s - 1] = t
chessboard(board, tr + s, tc, tr + s, tc + s - 1, s)
## 覆盖右下角子棋盘
if dr >= tr + s and dc >= tc + s:
chessboard(board, tr + s, tc + s, dr, dc, s)
else:
board[tr + s][tc + s] = t
chessboard(board, tr + s, tc + s, tr + s, tc + s, s)
chessboard(board, 0, 0, obstacle[0]-1, obstacle[1]-1, 2 ** k)
for i in range(2 ** k):
for j in range(2 ** k):
print(board[i][j], end=' ')
print()
到了这里,关于算法分析基础上机题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!