算法基础——模拟
目录
1 多项式输出
2.蛇形方阵
3.字符串的展开
模拟，顾名思义，就是题⽬让你做什么你就做什么，考察的是将思路转化成代码的代码能⼒。这类题⼀般较为简单，属于竞赛⾥⾯的签到题（但是，万事⽆绝对，也有可能会出现让人非常难受的模拟题），但是在学习语法阶段接触的题，大多数都属于模拟题。
1 多项式输出
题⽬来源： 洛⾕
题⽬链接：P1067 [NOIP2009 普及组] 多项式输出
难度系数： ★
[解法]
根据题意模拟+分类讨论（分的越详细，越不会出现bug）：
仅需按照顺序，考虑每⼀项的三件事情：符号 + 系数 + 次数。
处理「符号」：
- 负数：直接输出
- 正数：(1) 是第n项，不输出+ （2）其余情况，直接输出+
处理「系数」：
- 先取绝对值：
（1）不是1，直接输出
（2）是1
末项 - 需要输出
不是末项 - 不需要输出
处理「次数」：
- 次数为 1 ，输出 "x"；
次数为0 ，什么也不输出
其他 ，输出 "x^" + 对应的次数；
【参考代码】
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int n;cin >> n;
//循环次数
for(int i = n;i >= 0;i--){
int op;cin >> op;
if(op == 0) continue;//出来系数为0的情况
//1.符号
if(op < 0) cout << "-";
else{
if(i != n) cout << "+";
}
//2.系数
int a = abs(op);
if(a != 1 || (a==1 && i== 0)) cout << a;
//3.次数
if(i == 1)cout << "x";
else if(i == 0) ;
else{
cout << "x^" << i;
}
}
return 0;
}2.蛇形方阵
题⽬来源： 洛⾕
题⽬链接：P5731 【深基5.习6】蛇形⽅阵
难度系数： ★
[解法]
模拟填数的过程。（实现的方式有很多种）
在⼀个矩阵中按照⼀定规律填数的通用解法：
- 定义方向向量
比如本题⼀共四个方向，分别是右、下、左、上，对应： (0, 1)、(1, 0)、(0, -1)、(-1, 0)
遇到其他类型的题只需要更改方向向量即可；
2.根据规则结合方向向量填数
（1） 朝⼀个方向⾛，⼀边走⼀边填数，直到越界；
（2） 越界之后，结合定义的方向向量，求出下⼀轮应该⾛的方向以及应该到达的正确
位置；
（3）重复上述过程，直到把所有的数填完为止；
【参考代码】
#include<iostream>
using namespace std;
const int N = 15;
//定义方向向量 右，下， 左，上
int dy[] = {1,0,-1,0};
int dx[] = {0,1,0,-1};
int arr[N][N];
int main(){
int n;cin >> n;
//模拟填数过程
int cet = 1; //当前位置要填的数
int x = 1,y = 1;//初始位置
int pos = 0;//当前的方向
while(cet <= n*n){
arr[x][y] = cet;
//计算下一个位置
int a = x + dx[pos];
int b = y + dy[pos];
//判断是否越界
if(a < 1 || a > n || b < 1 || b > n || arr[a][b]){
//更新出正确的该走的位置
pos = (pos + 1) % 4;
a = x + dx[pos];
b = y + dy[pos];
}
cet++;
x = a;y = b;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
printf("%3d",arr[i][j]);
}
printf("\n");
}
return 0;
}3.字符串的展开
题⽬来源： 洛谷
题⽬链接： P1098 [NOIP2007 提⾼组] 字符串的展开
难度系数： ★
【解法】
纯代码题 - 考察代码能力 ：>
【参考代码】
#include<iostream>
#include<algorithm>
using namespace std;
int p1,p2,p3,n;
string s,ret;
//判断是否是数字字符
bool isdig(char ch){
return ch >= '0' && ch <= '9';;
}
//判断是否小写字母
bool islet(char ch){
return ch >= 'a' && ch <= 'z';
}
//展开 把(left,right)之间的字符展开
void add(char l,char r){
string t;
//遍历中间的字符
for(char ch = l + 1;ch < r;ch++){
char tmp = ch;
//处理p1
if(p1 == 2 && islet(tmp)) tmp -= 32; //小写变大写
else if(p1 == 3) tmp = '*';//变成星号
//处理p2
for(int i = 1;i <= p2;i++){
t += tmp;
}
}
//处理p3
if(p3 == 2) reverse(t.begin(),t.end());
ret += t;
}
int main(){
cin >> p1 >> p2 >> p3 >> s;
n = s.size();
for(int i = 0;i < n;i++){
char ch = s[i];
if(s[i] != '-' || i == 0 || i == n-1) ret += ch;
else{
char left = s[i-1], right = s[i+1];
//判断是否展开
if((isdig(left) && isdig(right) && left < right)
|| (islet(left) && islet(right) && left < right))
{
//展开
add(left,right);
}
else
{
ret += ch;
}
}
}
cout << ret << endl;
return 0;
}