考研机试C++题目精选

更多内容会在godownio.github.io更新

算法练习（C++代码）

考研上机或C语言代码笔试准备，暨大机试原题+letcode+牛客+中南大等高校机试

快速幂算法

题目：输入一个整数 n ，求 n^n 的个位数是多少。

快速幂算法：指数为偶数，则底数平方，指数除二；指数为奇数，则指数减一再把结果乘底数，底数平方，指数除二。指数看作二进制，除二可以看作位运算。

#include <iostream>

using namespace std;
int main(){
	int n;
	cin>>n;
	int power=n;
	int base=n;
	int result = 1;
	while(power>0){
		if(power%2==1){
			result *= base;
			power /= 2;
			base *= base;//指数为奇数，先乘底数。除二小数部分舍去。底数平方 
		}
		else{
			power /= 2;
			base *= base;//指数为偶数，除二，底数平方 
		}
	}
	cout<<result<<endl; 
	cout<<result%10;//mod 10即个位数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

斐波那契

输入一个整数 n ，求斐波那契数列的第 n 项。第一项是1， 第二项是1。要求必须递归！

#include <iostream>

using namespace std;

int f(int n){
    if(n==1||n==2){
        return 1;
    }
    else return f(n-2)+f(n-1);
}

int main(){
    int n;
    cin >> n;
    cout<<f(n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

成绩排名

对 n 个同学的考试成绩从大到小排名，成绩相同的算同一名。求排名为 m 的成绩。若无排名为m的成绩，输出最后一名的成绩。

• 输入格式

一共三行

第一行：一个整数 n，表示同学的个数。

第二行：n 个整数，表示 n 个同学的成绩。

第三行：一个整数 m，表示排名。

• 输出格式

一个整数，表示排名为 m 的成绩。

• 输入样例

6
100 100 99 98 97

2

• 输出样例

99

#include <iostream>

using namespace std;
int main(){
	int n,m;
	cout<<"输入同学个数："<<endl;
	cin>>n;
	int score[n];
	cout<<"输入同学的成绩："<<endl;
	for (int i=0;i<n;i++){
		cin>>score[i];
	}
	//cout<<"1";
	for (int i=0;i<n;i++){
		for(int j=n-i-1;j>0;j--){
			if(score[j]>score[j-1]){
				int temp = score[j];
				score[j] = score[j-1];
				score[j-1] = temp;
			}
		}//冒泡排序
	}
	int i=0,j;
	for(j=1;j<n;j++){
		if(score[j]!=score[i]){
			score[++i]=score[j];
		}
	}//双指针去重
	cout<<"输入要查询的排名："<<endl;
	cin>>m;
	if(m>i+1){
		cout<<score[i]<<endl; 
	}
	else{
		cout<<score[m-1];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

括号匹配

给定三种括号{ }，[ ], ( )，和若干小写字母的字符串，请问改字符串的括号是否匹配（可以嵌套）?

• 输入输出

输入格式：字符串s。 输出格式：若匹配，输出yes，否则输出no。

• 输入样例

{[a(v)d]q}
1

• 输出样例

yes
1

#include <iostream>
#include <stack>

using namespace std;
int main(){
	stack <int> s;
	string strs;
	cin>>strs;
	int m = strs.length();
	for (int i=0;i<m;i++){
		if(strs[i]=='('||strs[i]=='{'||strs[i]=='['){
			s.push(strs[i]);
		}
		if(strs[i]==')'){
			if(!s.empty()&&s.top()=='(') s.pop();
			else{
				cout<<"不匹配"; 
				return 0;
			}
		}
		else if(strs[i]=='}'){
			if(!s.empty()&&s.top()=='{') s.pop();
			else{
				cout<<"不匹配"; 
				return 0;
			}
		}
		else if(strs[i]==']'){
			if(!s.empty()&&s.top()=='[') s.pop();
			else{
				cout<<"不匹配"; 
				return 0;
			}
		}//特别注意，栈为空s.top()不返回NULL，而是程序出错
	}
	if (s.empty()) cout<<"匹配成功";
	else cout<<"匹配失败";
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

letcode&牛客dp+链表

不同路径

先看递归解决：很明显从右下角开始思考，有从上和从左过来两种方式，即等于左和上路径条数之和。1*2，1*3…等很明显只有一条路径，即m or n一个为1，则返回1

#include <iostream>

using namespace std;

int path(int m,int n){
	if(m>1&&n>1){
		return path(m-1,n)+path(m,n-1);
	}else return 1;//1*2或者2*1或者1*6的路径选择都为1个 
}

int main(){
	int m,n;
	cin>>m>>n;
	cout<<path(m,n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

很遗憾，递归不满足时间复杂度。

非递归解决：定义一个dp数组，记录每个格子的路径条数，即除一行一列外，每个格子的路径条数都等于上+左

#include <iostream>

using namespace std;

int path(int m,int n){
    int dp[m][n];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
        	if(j>0&&i>0){
        		dp[i][j]=dp[i-1][j]+dp[i][j-1];
    		}
            else{
                dp[i][j]=1;
            }
        }
    }
    return dp[m-1][n-1];
}

int main(){
	int m,n;
	cin>>m>>n;
	cout<<path(m,n);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

障碍物版不同路径

首先，怎么输入和传参二维数组？

不能直接向某个变量cin二维数组，只能先输入行和列，然后再逐个输入，传参就用vector，因为C++传参定长，不能使用int[][] matrix，而是int matrix[][3]这种，不如使用vector方便

其次，障碍物点到达它的路径条数为0，其余按照上个题目进行计算即可

不能直接把数组传给vector，需要先进行类型转换：

int arr[rows][cols] = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};

 // 将数组转换为 std::vector
 vector<vector<int>> matrix;
 for (int i = 0; i < rows; ++i) {
     matrix.push_back(vector<int>(begin(arr[i]), end(arr[i])));
 }
1
2
3
4
5
6
7

注意：devC++的标准无法读取vector库，需要在编译选项->添加参数"–std=c++11"

#include <iostream>
#include <vector>

using namespace std;
int path(vector<vector<int>>& block){
    int m=block.size(),n=block[0].size();
    vector<vector<int>> dp(m,vector<int>(n));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(block[i][j]==0){
                if(j>0&&i>0){
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }else{
                    dp[i][j]=1;//第一行或第一列
                }
            }else{
                dp[i][j]=0;//有障碍物
            }
        }
    }
    return dp[m-1][n-1];
}
int main(){
    int rows,cols;
    cout<<"请输入行数和列数："<<endl;
    cin>>rows>>cols;
    vector<vector<int>> block(rows,vector<int>(cols));
    cout<<"请依次输入矩阵："<<endl;
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>block[i][j];
        }
    }
    cout<<"左上到右下路径条数为："<<path(block);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

秒了

最小路径和

太经典了，和回复祝顺利一样经典

根据上两道题，不难猜出每个位置的dp最小值为min(上，左)+本块值，第一行则只能左+本块值，第一列则只能上+本块值，秒了

#include <iostream>
#include <vector>

using namespace std;
int min(int n,int m){
    if(n>m) return m;
    else return n;
}
int path(vector<vector<int>>& block){
    int m=block.size(),n=block[0].size();
    vector<vector<int>> dp(m,vector<int>(n));
    dp[0][0]=block[0][0];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(i>0&&j==0){
                dp[i][j]=dp[i-1][j]+block[i][j];//第一行
            }
			if(j>0&&i==0){
                dp[i][j]=dp[i][j-1]+block[i][j];//第一列
            }
			if(j>0&&i>0){
                dp[i][j]=min(dp[i][j-1],dp[i-1][j])+block[i][j];
            }
        }
    }
    return dp[m-1][n-1];
}
int main(){
    int rows,cols;
    cout<<"请输入行数和列数："<<endl;
    cin>>rows>>cols;
    vector<vector<int>> block(rows,vector<int>(cols));
    cout<<"请依次输入矩阵："<<endl;
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            cin>>block[i][j];
        }
    }
    cout<<"左上到右下最短路径和为："<<path(block);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

other 机试题

中南大上机压轴

水印是我的CSDN号

• 测试数据：

3 500
0.6 100
0.8 200
0.7 100
输出 390

​ 首先要对输入的折扣进行排序，优先使用比率低的z进行支付。
​ 然后用lowcost记录目前多少钱是打过折的。T-lowcost就是剩余没打折的。
​ 每次循环用上一个人的折扣额度。若所有人折扣额度相加低于总价，则最后剩的部分就不打折

#include <iostream>
using namespace std;

int paychase(int N,int T,double *z,int* H){
	int lowcost = 0;
	for(int i=0;i<N;i++){
		if(T<=lowcost+z[i]*H[i]){
			T = lowcost + (T-lowcost)*H[i];
			return T;
		}//菜品总价小于折扣
		else{
			lowcost = lowcost + z[i]*H[i];//lowcost为当前折扣限度，比如第二轮中就是0.6*100+0.8*200
			cout<<"lowcost:"<<lowcost<<endl;
			T = T - H[i] + z[i]*H[i];//折扣
			cout<<"T:"<<T<<endl;
		}
	}
	return T;
}

int main(){
	int N,T;
	cout<<"请输入人数和菜品总价："<<endl;
	cin>>N>>T;
	double z[N];
	int H[N];
	cout<<"请输入每个的折扣率和折扣上限："<<endl;
	for(int i=0;i<N;i++){
		//cout<<i<<endl;
		cin>>z[i]>>H[i];
	}
	for (int i=0;i<N;i++){
		for (int j=i;j<N;j++){
			if(z[j]>z[i]){
				double tempz;int tempH;
				tempz=z[j];z[j]=z[i];z[i]=tempz;
				tempH=H[j];H[j]=H[i];H[i]=tempH;
			}
		}//折扣排序
	}
	int cost = paychase(N,T,z,H);
	cout<<"本次用餐总花费："<<cost<<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

日期

输入日期yyyymm dd，输出是本年第几天。

本题主要知识点：年份满足以下条件之一为闰年，2月有29天：

• 年份能被4整除，不能被100整除
• 年份能被400整除

代码不写了

C语言考点

指针数组，数组指针

区分int (*p)[3]和 int *p[3]

• 指针数组：int *p[3]，实际上是个数组，只是里面元素都存放的指针，指针指向int型变量地址。
• 数组指针：int (*p)[3]，优先级()>[]>*，实际上是定义的一个指针，指向一个包含三个整数的数组。

int **p

int **p是一个指针的指针。

赋值判断

int *a=&b(√)

int a=&b(×)

int *a; a=&b(√)

记住只有指针才能存地址，整型那些都不能存地址。以及int *a后，*a才是取值，a是指向的地址。

后文会更密码学和C易错点记录