C++基础算法：模拟

文章目录 1.[P1067 [NOIP 2009 普及组\] 多项式输出 - 洛谷]( .luogu /problem/P1067)题目解析算法解析代码实现 2.[P5731 【深基5.习6】蛇形方阵 - 洛谷]( .luogu /problem/P5731)题目解析算法原理代码实现 3.[P1098 [NOIP 2007 提高组\] 字符串的展开 - 洛谷]( .luogu /problem/P1098)算法原理代码实现 模拟，顾名思义，就是题目让你做什么你就做什么，考察的是将思路转化成代码的代码能力

1.[P1067 NOIP 2009 普及组] 多项式输出 - 洛谷

题目解析

这道题是简单的模拟实现题目，主要将算式通过代码来实现出来，将所有的情况分析出来，代码进行实现即可

算法解析

这道题需要细心处理分类:

分类如下：

处理「符号」： 如果系数小于 0 ，直接输出 “-”； ◦ 如果系数大于 0 ，除了⾸项不输出 “+”，其余全部输出 “+”。 处理「系数」： 先取⼀个绝对值，因为正负的问题已经处理过了；当系数不等于 1 ，直接输出这个数；但是当系数为 ，且是最后⼀项的时候，这个 也是需要输出的；其余情况下的 不需要输出。 处理「次数」： 次数大于 1 ，输出 “x^” + 对应的次数；次数等于 1 ，输出 “x”；次数小于 1 ，什么也不输出。

对应到代码:

//处理系数 if(a==0) continue; if(a>0) { if(i!=n) cout<<'+'; } else cout<<'-'; a = abs(a); if(a!=1||(a==1&&i==0)) cout<<a; //处理次数 if(i == 0) continue; else if(i == 1) cout<<'x'; else cout<<"x^"<<i; 代码实现 #include <iostream> using namespace std; #include <cmath> int main() { int n; cin>>n; for(int i = n;i>=0;i--) { int a; cin>>a; //处理系数 if(a==0) continue; if(a>0) { if(i!=n) cout<<'+'; } else cout<<'-'; a = abs(a); if(a!=1||(a==1&&i==0)) cout<<a; //处理次数 if(i == 0) continue; else if(i == 1) cout<<'x'; else cout<<"x^"<<i; } return 0; } 2.P5731 【深基5.习6】蛇形方阵 - 洛谷

题目解析

本题是通过模拟运用数组来模拟实现蛇形方阵的题目，通过输入数据n来模拟实现要求

算法原理

对于方阵类的题目我们可以用两个直角坐标系来实现题目要求：

这样通过数组来模拟方向我们直接可以对其进行填数

int x[] = {0,1,0,-1}; int y[] = {1,0,-1,0}; int pos; //创建数组存放值 const int N = 10; int ret[N][N]; int main() { for(int i = 1; i<=n*n;i++) { ret[a][b] = i; //先判断是否越界 int p = a + x[pos], q = b + y[pos]; if(p>n||q>n||q<1||ret[p][q]!=0) ++pos%=4; //a b更正方向 a += x[pos]; b += y[pos]; } } 代码实现 #include <iostream> using namespace std; //通过数组来模拟行进方向 int x[] = {0,1,0,-1}; int y[] = {1,0,-1,0}; int pos; //创建数组存放值 const int N = 10; int ret[N][N]; int main() { int n; cin>>n; int a = 1, b = 1; for(int i = 1; i<=n*n;i++) { ret[a][b] = i; int p = a + x[pos], q = b + y[pos]; //判断是否越界 if(p>n||q>n||q<1||ret[p][q]!=0) ++pos%=4; a += x[pos]; b += y[pos]; } //打印数组 for(int i = 1; i<=n;i++) { for(int j = 1;j<=n;j++) { printf("%3d",ret[i][j]); } cout<<endl; } return 0; } 3.[P1098 NOIP 2007 提高组] 字符串的展开 - 洛谷

算法原理

题目描述过多，可以先写主要逻辑，中间一些内容可以用函数代替

基本逻辑：

int main() { cin>>p1>>p2>>p3>>s; for(int i = 0;i<s.size();i++) { char ch = s[i]; //判断逻辑 if(ch!='-'||ch==0||ch==s.size()-1) ret+=ch; else { char left = s[i-1]; char right = s[i+1]; //判断是数字还是字母 if((islet(left)&&islet(right)&&left<right)|| (isdig(left)&&isdig(right)&&left<right)) { add(left,right);//题目实现的主要函数 } else { ret+=ch; } } } cout<<ret; }

将中间部分判断是数字还是字母的函数写出来

bool islet(char ch) { return ch>='a'&&ch<='z'; } bool isdig(char ch) { return ch>='0'&&ch<='9'; }

最后再将题目要求的写出来，其中

p1使用大小写字符之间相差32的特性即可完成p2直接使用循环即可完成p3使用reverse函数，要注意包含头文件<algorithm> void add(char left,char right) { string t; for(char i = left+1;i<right;i++) { char ch = i; if(p1==2&&islet(ch)) ch-=32; else if(p1==3) ch='*'; for(int j = 0;j<p2;j++) { t += ch; } } if(p3==2) reverse(t.begin(),t.end()); ret+=t; } 代码实现 #include <iostream> #include <algorithm> using namespace std; string ret,s; int p1,p2,p3; bool islet(char ch) { return ch>='a'&&ch<='z'; } bool isdig(char ch) { return ch>='0'&&ch<='9'; } //程序主逻辑 void add(char left,char right) { string t; for(char i = left+1;i<right;i++) { char ch = i; if(p1==2&&islet(ch)) ch-=32; else if(p1==3) ch='*'; for(int j = 0;j<p2;j++) { t += ch; } } if(p3==2) reverse(t.begin(),t.end()); ret+=t; } int main() { cin>>p1>>p2>>p3>>s; for(int i = 0;i<s.size();i++) { char ch = s[i]; //判断逻辑 if(ch!='-'||ch==0||ch==s.size()-1) ret+=ch; else { char left = s[i-1]; char right = s[i+1]; if((islet(left)&&islet(right)&&left<right)|| (isdig(left)&&isdig(right)&&left<right)) { add(left,right); } else { ret+=ch; } } } cout<<ret; }

总结这类题目要求分类详细，判断时要注意越界情况