机试准备第13天

第一题是模拟出入栈游戏。

#include <stdio.h>
#include <stack>
#include <iostream>
using namespace std;
int main()
{string str;while(getline(cin, str)){stack<char> stk;int j = 0;//扫描出栈序列strfor(char i = 'a';i<='z';i++){stk.push(i);//每次按顺序入栈一个while(!stk.empty()&&stk.top()==str[j]){j++;//发生匹配，向后扫描stk.pop();//弹出匹配元素}}if(stk.empty()) printf("yes\n");else printf("no\n");}return 0;
}

第二题是简单计算器，代码逻辑与表达式计算相同。

#include <stdio.h>
#include <string>
#include <stack>
#include <map>
using namespace std;int main() {char strArr[300] = { 0 };map<char, int> priority = {{'\n',0},{'+',1},{'-',1},{'*',2},{'/',2}};while (fgets(strArr,300,stdin) != NULL) {string str = strArr;if (str == "0\n") {break;}string numStr = "";stack<char> opStack;stack<double> numStack;for (int i = 0; ; ++i) {if (str[i] >= '0' && str[i] <= '9') {numStr.push_back(str[i]);}else if (str[i] == ' ') {if (numStr.size() > 0) { // 操作数读取完成double num = stod(numStr);numStr = "";numStack.push(num);}}else { // 运算符if (str[i] == '\n' && numStr.size() > 0) { // 操作数读取完成double num = stod(numStr);numStr = "";numStack.push(num);}while (!opStack.empty() &&priority[str[i]] <= priority[opStack.top()]) {double rhs = numStack.top();numStack.pop();double lhs = numStack.top();numStack.pop();char curOp = opStack.top();opStack.pop();if (curOp == '+') {numStack.push(lhs + rhs);}else if (curOp == '-') {numStack.push(lhs - rhs);}else if (curOp == '*') {numStack.push(lhs * rhs);}else if (curOp == '/') {numStack.push(lhs / rhs);}}// 栈为空 或者 新op的优先级高于栈顶if (str[i] == '\n') {printf("%.2lf\n", numStack.top());break;}else {opStack.push(str[i]);}}}}return 0;}

下面学习递归与分治。若一个问题可以通过分而治之的思想解决，那就会用到递归。在代码段调用函数时，PC会走到被调函数的入口，栈区会压入一个新的栈针，返回时PC会回到主调方，栈区会弹出栈顶。递归的设计要考虑递归出口。

第三题是跳台阶，显然，这是一个复杂到没法全盘考虑的问题，只能考虑逐渐降低复杂度。把一个大问题分解为相似的小问题，看看能不能解决小问题。知道分解为能够直接解决的最小问题。本题中f(n) = f(n-1)+f(n-2)。使用分治法的两个要素：1.大问题要变成相似的小问题 2.找到最小问题的解决方案。

#include <stdio.h>
using namespace std;
int f(int n){if(n == 1) return 1;else if(n == 2) return 2;else return f(n-1)+f(n-2);
}
int main(){int n;scanf("%d", &n);int result = f(n);printf("%d", result);
}

第四题是不连续的字串。

using namespace std;
#include <stdio.h>
int f(int n){if(n == 1) return 2;else if(n == 2) return 3;else return f(n-1)+f(n-2);
}int main()
{int n;scanf("%d", &n);printf("%d", f(n));return 0;
}

第五题是斐波那契数列，最有自信的一集。

#include <stdio.h>
using namespace std;
int F(int n ){if(n == 0) return 0;else if(n == 1) return 1;else return F(n-1) +F(n-2);
}
int main(){int n;scanf("%d", &n);printf("%d", F(n));
}

第六题是骨牌。简单dp，dp[n] = dp[n-1]+dp[n-2]。

#include <stdio.h>
using namespace std;
int main(){int n;scanf("%d", &n);int dp[10010] = {0};dp[1] = 1;dp[2] = 2;if (n == 1) {printf("1");return 0;}else if(n == 2) {printf("2");return 0;}else {for(int i = 3;i<=n;i++){dp[i] = (dp[i-1]+dp[i-2])%999983;}printf("%d", dp[n]%999983);return 0;}
}

第七题是2的幂次方。这个是真看不懂，看了答案代码，首先得到n的二进制形式，找到对应二进制位不为0的位置，输出不为0的位置，然后将不为0的位置再次递归直到到递归边界。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
string Get2sexponet(int n){if(n == 0) return "0";vector<int> exp;for(int i = 15;i >= 0;i--){if((n & (1<<i))!=0){exp.push_back(i);}}// n = 2^(exp[0]) + 2^(exp[1]) + ....求出n的指数形式string res ="";for(int i = 0; i <exp.size();i++){//2(XXX)+if(i != 0){res+="+";}if(exp[i] == 1){res+="2";}else {res += "2(" + Get2sexponet(exp[i]) + ")";}}return res;
}
int main()
{int n;while(scanf("%d", &n)!=EOF){printf("%s\n",Get2sexponet(n).c_str());}return 0;
}

第八题是矩阵幂次，主要是熟悉矩阵的各位置元素如何得到。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 15;
int n,k;
int w[N][N];
void mul(int c[N][N], int a[N][N], int b[N][N]){static int tmp[N][N];memset(tmp, 0, sizeof tmp);for(int i = 0; i <n;i++){for(int j = 0; j<n;j++){for(int k = 0;k<n;k++){tmp[i][j] +=a[i][k]*b[k][j];}}}for(int i=0; i<n;i++){for(int j = 0; j<n;j++){c[i][j] = tmp[i][j];}}
}
int main(){scanf("%d%d", &n, &k);for(int i = 0; i <n;i++){for(int j = 0; j < n;j++){scanf("%d", &w[i][j]);}}int res[N][N] ={0};for(int i = 0; i< n;i++) res[i][i] = 1;for(int i = 0;i<k;i++){mul(res,res,w);}for(int i = 0; i<n;i++){for(int j = 0;j<n;j++){printf("%d ", res[i][j]);}printf("\n");}
}