HNUCM-《算法分析与设计》期末考试考前复习题

问题 A: X星人的地盘

题目描述

一天，X星人和Y星人在一张矩形地图上玩抢地盘的游戏。

X星人每抢到一块地，在地图对应的位置标记一个“X”；Y星人每抢到一块地，在地图对应的位置标记一个“Y”；如果某一块地无法确定其归属则标记一个“N”。

最终统计谁拥有的地盘最大，即统计“X”和“Y”的个数。如果“X”的个数多，则说明X星人的地盘更大，输出“X win”；反之，如果Y星人的地盘更大，则输出“Y win”；如果X星人和Y星人拥有的地盘一样大，则输出“The same”。

输入

单组输入。

第1行输入两个正整数m和n，表示地图矩阵的行和列。(m和n均不超过1000)

从第2行到第m+1行，输入一个由'X'、'Y'和'N'三种字符组成的矩阵，每行包含n个字符，一共m行。

输出

如果X星人拥有的地盘大，输出“X win”；如果Y星人拥有的地盘大，输出“Y win”；如果拥有的地盘一样大，输出“The same”。

思路

简单题，就是数数，但是数据应该有点小问题，不适用python和java的一般输入，会导致wa。改用多组输入的方式循环输入即可解决。

代码

x, y = 0, 0
while True:try:string = input()x, y = x + string.count('X'), y + string.count('Y')except:break
print('X win') if x > y else print('Y win') if y > x else print('The same')

问题 B: X星人的高考

题目描述

一年一度的X星高考如期举行。今年X星新高考一卷的数学真的很难，据说把很多考生都考哭了。

今年数学考试的多选题仍然是4道题，每题5分，共20分。在每小题给出的4个选项中，有多项符合题目要求，全对得5分，选对但不全得2.5分，有选错的得0分。每道题均包含A、B、C和D四个选项。

现在给出某X星考生的多选题答案和正确答案，请编写一个程序计算该X星考生最终多选题的得分。

输入

单组输入。

每组输入两行，第1行包含该X星人四道多选题的答案，两两之间用空格隔开；第2行包含四道多选题的正确答案，两两之间用空格隔开（答案不一定按照字典序排列）。

输出

输出该X星考生最终多选题的得分(答案保留一位小数)。

思路

模拟判题即可，注意分情况考虑。

代码

def mark(x: str, y: str):s = list(y)for r in x:if r in s:s.remove(r)else:return 0.0if len(s) == 0:return 5.0return 2.5while True:try:reply, answer, grades = input().split(), input().split(), 0.0for i in range(4):grades += mark(reply[i], answer[i])print("%.1f" % grades)except:break

问题 C: X星人的数列

题目描述

爱冒险的X星人在一艘海底沉船上发现了一串神秘数列，这个数列的前6项如下：

0 1 3 7 15 31

X星人对这串数列产生了浓厚的兴趣，他希望你能够帮他发现这个神秘数列中所蕴含的规律，并且使用递归来编写一个程序输出该数列前N项的和。

当输入一个正整数N时，请输出这个神秘数列前N项的和。

输入

单组输入，每组输入一个正整数N（N<=20）。

输出

输出一个正整数，对应这个神秘数列前N项的和。

思路

不难发现n[i] == 2 ** i - 1，这里偷懒没用递归。

代码

nums, n = [2 ** i - 1 for i in range(21)], int(input())
print(sum(nums[:n]))

问题 D: X星人的递归

题目描述

X星人想使用递归编写一个程序求如下表达式的计算结果： (1<n<=1000)

S(n) = 1 - 4 + 9 - 16 + 25 - 36 +......

输入n，输出表达式S(n)的结果。

请你编写一个递归程序帮助X星人实现该功能。

输入

单组输入，输入一个正整数n，1<n<=1000。

输出

输出表达式S(n)的计算结果。

思路

简单题，直接用递归的话，注意递归深度。

import syssys.setrecursionlimit(1000000)def fun(x: int):if x == 1:return 1else:t = -1 if x % 2 == 0 else 1return fun(x - 1) + t * (x ** 2)n = int(input())
print(fun(n))

问题 E: X星人的礼物

题目描述

六一儿童节到了，X星人宝宝收到了很多很多礼物。他决定把这些礼物装到自己的礼物箱中。为此，他准备了很多个型号相同的礼物箱，每个礼物箱能够装礼物的最大重量都是一样的。但是X星人宝宝不希望在一个礼物箱里面装太多礼物（可能担心礼物会被压坏吧），每个礼物箱最多只允许装2个礼物。

假设X星人宝宝收到了N个礼物，现在给出每一个礼物的重量和一个礼物箱的最大装载量，请你编写一个程序计算X星人宝宝最少要用多少个礼物箱才能够把所有的礼物都装完。

输入

单组输入。

每组两行，第1行输入两个正整数，分别表示礼物的数量N和每个礼物箱的最大装载量C，其中1<=N<=1000，1<=C<=100，两者之间用英文空格隔开。

第2行输入N个不超过100的正整数，分别表示每一个礼物的重量，两两之间用英文空格隔开。

输入保证最重的礼物的重量<=C。

输出

针对所输出的数据，输出将所有的礼物全部都装完所需的礼物箱的最少个数。

思路

对礼物的重量进行排序，从首尾开始选取礼物放入盒中，如果礼物的重量小于等于c，两者都放入盒中，否则只有最重的礼物放入盒中。

代码

n, c = map(int, input().split())
goods, cnt = [int(i) for i in input().split()], 0
i, j, _ = 0, n - 1, goods.sort()
while i < j:if goods[i] + goods[j] <= c:cnt, i, j = cnt + 1, i + 1, j - 1else:cnt, j = cnt + 1, j - 1
print(cnt) if i != j else print(cnt + 1)

问题 F: X星人的基因

题目描述

X星人的基因由A、B、C、D、E五种不同的结构组合而成。

如果两个性别不同的X星人的基因序列相似度大于50%，按照X星的法律他们是禁止结婚的，等于50%据说还是可以的。

那么基因的相似度怎么计算呢？分别从两个人身上取长度均为N的基因片段，如果它们的最长公共子序列为M，则相似度=M/N。是不是很简单呢？

现在给你两段X星人的基因序列片段，请你判断他们是不是可以结婚？

输入

每一组测试数据包含3行，

第1行数字N表示待比较基因序列片段的长度，N<=10^3。

第2行和第3行为两个长度为N的基因序列片段。

输入0表示结束。

输出

两个X星人是否可以结婚，如果可以输出”Yes“，如果不可以输出”No“。

思路

最长子序列题目，模板题，按模板来即可。

代码

while True:try:n = int(input())DNA_x, DNA_y = "".join(input().split()), "".join(input().split())dp = [[0] * (n + 1) for _ in range(n + 1)]for i in range(1, n + 1):for j in range(1, n + 1):dp[i][j] = dp[(i - 1)][j - 1] + 1 if DNA_x[i - 1] == DNA_y[j - 1] else max(dp[i - 1][j], dp[i][j - 1])# print(dp)print('No') if dp[n][n] / n > 0.5 else print('Yes')except:break

问题 G: X星人的迷宫

题目描述

X星人进入了一个树形迷宫，该迷宫由一个N层的满二叉树组成。迷宫的每一个节点都有一个计分权重，只有找到那条从根节点开始到叶子结点的计分权重和最大的路径，X星人才能够顺利走出迷宫。

现在给出该树形迷宫每一个节点的权重值，你能否编写一个程序计算出权重和最大的路径所对应的总权重。

输入

单组输入。

第1行输入一个正整数N，表示二叉树的节点层数。（N<=20）

第2行输入2^N-1个正整数，分别表示迷宫中每一个节点的权重，两两之间用英文空格隔开。第1个数字表示根节点的权重，接下来两个数字表示根节点左、右孩子的权重，再接下来四个数字表示第3层的四个节点的权重，......，以此类推。每个节点的权重均不超过1000。

输出

输出从根节点出发到叶子节点权重和最大的路径所对应的权重。

思路

从题目不难看出，这是一道路径规划（动态规划）的题目，理论最大数据有2 ** 20 - 1 个，所以可能需要一些节省空间的方法进行解题，所以使用了坐标二维转一维的简单方法节省些许空间。值得注意的是Python使用此思路还是会爆。

代码

C++

#include<bits/stdc++.h>
using namespace std;
int nums[1048890];
int s[] = {0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287};
int main() {int n;cin >> n;for(int i = 0; i < (int) pow(2.0, n) - 1; i++)cin>>nums[i];for(int i = n - 2; i >= 0; i--){for(int j = 0; j < (int) pow(2.0, i); j++){nums[s[i] + j] = nums[s[i] + j] + max(nums[s[i + 1] + 2 * j], nums[s[i + 1] + 2 * j + 1]);}}cout << nums[0] << endl;return 0;
}

Python

n, nums = int(input()), list(map(int, input().split()))  # 1048575
s = [0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287]
for i in range(n - 2, -1, -1):for j in range(2 ** i):x, y = s[i], s[i + 1]nums[x + j] = nums[x + j] + max(nums[y + 2 * j], nums[y + 2 * j + 1])
print(nums[0])

问题 H: X星人的救援

题目描述

X星发生了地震，X星总部决定派出驻扎在总部Super X救援队前去营救被困的X星人。

现在给你一张X星地图，在地图中标注了若干点之间的距离（单位为千米），这些点中包括X星总部和地震点。

已知Super X救援队的移动时速M（千米/分钟），请问救援队能否在K分钟之内（包括K分钟）从总部赶到地震点？

输入

多组输入，第1行输入一个正整数T表示输入数据的组数。 对于每一组输入数据：

第1行输入3个正整数N、M和K，分别表示地图上点的数量、救援队的移动时速和设定时间，三个数字之间用空格隔开，N<=100。

接下来N行是一个N*N的矩阵，每一行两个数字之间用空格隔开，第i行第j列表示顶点i到顶点j之间的距离。如果两个顶点之间不能直接达到，则对应的值为-1。

其中，编号为1的点表示X星总部，编号为N的点表示地震点。

输出

针对每一组输入数据，如果救援队能在指定的K分钟之内从总部赶到地震点，输出“Yes”，否则输出“No”。

思路

从题目可以知道这是一道求点0到点n-1的最短路径的题目，结合给出的距离矩阵使用迪杰斯特拉算法思想即可完成解题。

代码

def get_v():res, tmp = -1, float('inf')for i in range(n):if i not in v and maze[0][i] < tmp and maze[0][i] != -1:res, tmp = i, maze[0][i]return rest = int(input())
while t > 0:t = t - 1n, m, k = map(int, input().split())maze, v, s = [list(map(int, input().split())) for _ in range(n)], [0], nwhile s >= 0 and n - 1 not in v:tmp_v, s = get_v(), s - 1v.append(tmp_v)for j in range(n):x, y, z = maze[tmp_v][j], maze[0][tmp_v], maze[0][j]if j not in v and x != -1 and (z == -1 or x + y < z):maze[0][j] = maze[0][tmp_v] + maze[tmp_v][j]print('No') if maze[0][n - 1] == -1 or maze[0][n - 1] / m > k else print('Yes')