考研機試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即個位數
}

斐波那契

輸入一個整數 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);
}

成績排名

對 n 個同學的考試成績從大到小排名，成績相同的算同一名。求排名為 m 的成績。若無排名為m的成績，輸出最后一名的成績。

輸入格式

一共三行

第一行：一個整數 n，表示同學的個數。

第二行：n 個整數，表示 n 個同學的成績。

第三行：一個整數 m，表示排名。

輸出格式

一個整數，表示排名為 m 的成績。

輸入樣例

6
100 100 99 98 97

輸出樣例

#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];}
}

括號匹配

給定三種括號{ }，[ ], ( )，和若干小寫字母的字符串，請問改字符串的括號是否匹配（可以嵌套）?

輸入輸出

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

輸入樣例

{[a(v)d]q}

輸出樣例

yes

#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;
}

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);
}

很遺憾，遞歸不滿足時間復雜度。

非遞歸解決：定義一個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);
}

障礙物版不同路徑

首先，怎么輸入和傳參二維數組？

不能直接向某個變量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::vectorvector<vector<int>> matrix;for (int i = 0; i < rows; ++i) {matrix.push_back(vector<int>(begin(arr[i]), end(arr[i])));}

注意：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;
}

秒了

最小路徑和

太經典了，和回復祝順利一樣經典

根據上兩道題，不難猜出每個位置的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;
}

other 機試題

中南大上機壓軸

506ec55b1cc642a7afb2c28c5d175ce8

水印是我的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*200cout<<"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;
}