武理计专 考研复试 历年算法真题题解（个人解析）

题解（个人解析）"/>

武理计专 考研复试 历年算法真题题解（个人解析）

目录

• 2021机试
• • 第一题
  • 第三题
• 2019笔试
• 2018笔试

复试准备期间实现的部分真题内容，由于时间关系，我只写了几道题，下面的题解都是我自己写的代码，不完全正确，可以先看看目录哪些是能用上的

2021机试

第一题

• 题解
  一道回溯法的题目，可以在读入文件的时候先统计任务总量sum，sum是奇数，则无法均分，可以直接返回结果，之后再进行回溯判断，回溯的尽头就是当前选的数字总和大于sum/2，则再往后选也不可能均分。

#include <iostream>
#include<sstream>
#include<string>
#include<fstream>
#include<vector>
using namespace std;vector<int> flag;//用于后续标记bool recursion(vector<int>& nums, int sum, int count) {if (count == sum / 2) return true;if (count > sum / 2) return false;for (int i = 0; i < nums.size(); i++) {if (!flag[i]) {flag[i] = 1;if (recursion(nums, sum, count += nums[i])) {return true;}flag[i] = 0;}}return false;
}int main() {vector<int> nums;//存读出来的数int p;int sum = 0;ifstream read;read.open("input03.txt", ios::in);while (read >> p) {nums.push_back(p);flag.push_back(0);sum += p;}ofstream write;write.open("output.txt", ios::out);//任务量总数为奇数，没有能够均分的方案if (sum % 2 != 0) {write << "NO" << endl;cout << "NO" << endl;return 0;}//递归入口if (recursion(nums, sum, 0)) {write << "YES" << endl;cout << "YES" << endl;}else {write << "NO" << endl;cout << "NO" << endl;}write.close();return 0;
}

第三题

• 题解
  我用的是回溯法，加了一些剪枝的操作来加速，

// project01.cpp : 定义控制台应用程序的入口点。
//#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<vector>using namespace std;//货物的结构体，weight就是重量，count就是货物数量
typedef struct good{int weight;int count;
}good;//回溯法的算法，k是表示当前考虑到到goods的第几个货物
//不取比k下标小的货物，防止重复的获取方案
//参数nums是货物列表，sum是当前取货总重量，t是重量上限，ans是方案计数
void recursion(vector<good>& goods,int sum, int t, int k, int& ans){//当前取的货物总重量在(0，t],就可以记为一种方案if(sum <= t && sum != 0 && k==goods.size()) {ans++;}//若是总重量大于上限，剪枝，或者k超出下标范围，后面无需再查找方案if(k >= goods.size()){return;}//回溯的具体算法for(int i=0;i<=goods[k].count && sum + i*goods[k].weight <= t;i++){sum += i*goods[k].weight;recursion(goods,sum,t,k+1,ans);sum -= i*goods[k].weight;}
}int main()
{//读取文件内容ifstream read;read.open("input.txt",ios::in);int m,c,w,t;read >> m;read >> t;vector<good> goods;for(int i=0;i<m;i++){good one;read >> one.count;goods.push_back(one);}for(int i=0;i<m;i++){read >> goods[i].weight;}int ans = 0;recursion(goods,0,t,0,ans);cout << ans << endl;ofstream write;write.open("output.txt",ios::out);write << ans;write.close();return 0;
}

2019笔试

#include <iostream>
#include<sstream>
#include<string>
#include<fstream>
#include<vector>
#include<queue>
#include<stack>
using namespace std;int flag[100];int main() {stack<char> s;ifstream read;string str = "{([{)])}";char p;string ans;for (int i = 0; i < str.size(); i++) {if (str[i] == '(' || str[i] == '[' || str[i] == '{') {s.push(str[i]);}else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {//当前栈为空，无法匹配当前的右括号，直接跳过if (s.empty()) continue;char q = s.top();s.pop();//匹配则将字符串加入答案，否则就进入下一次循环if (str[i] == ')') {if (q == '(') {ans = '(' + ans + ')';}}else if(str[i] == ']') {if (q == '[') {ans = '[' + ans + ']';}}else if (str[i] == '}') {if (q == '{') {ans = '{' + ans + '}';}}}}cout << ans << endl;
}

2018笔试

• 题解
  就是一个sort

#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;typedef struct student{int age;int grade;string name;
}student;bool cmp(student& a,student& b){return a.grade > b.grade;
}int main()
{vector<student> students;for(int i=0;i<8;i++){student one;cin >> one.name >> one.age >> one.grade;students.push_back(one);}for(int i=0;i<8;i++) cout << students[i].name << students[i].age << " " << students[i].grade << endl;sort(students.begin(),students.end(),cmp);cout << endl << students[1].name << " " << students[1].age << " " << students[1].grade << endl;
}