算法基础 1

目录

一、模拟

1.1 多项式输出

1.2 蛇形矩阵

介绍一种通用解法——解决矩阵填数问题

1.3 字符串展开

二、高精度

2.1 高精度加法

2.2 高精度减法

2.3 高精度乘法

2.4 高精度除法（高精度 / 低精度）

---

一、模拟

1.1 多项式输出

题目链接：P1067 [NOIP 2009 普及组] 多项式输出 - 洛谷 注意模拟+分类讨论即可

#include<iostream>
#include<cmath>
using namespace std;
​
int main()
{int n = 0;cin >> n;for(int i = n;i >= 0;i--){int m = 0;cin >> m;if(m == 0) continue;//1.处理符号if(m > 0 && i != n)cout << '+';else if(m < 0)cout << '-';
​//2.处理数字int a = abs(m);if(a != 1 || (a == 1 && i == 0)) cout << a;//3.处理次数if(i == 0)continue;else if(i == 1)cout << 'x';elsecout << "x^" << i;}
​return 0;
}

1.2 蛇形矩阵

题目链接：P5731 【深基5.习6】蛇形方阵 - 洛谷

介绍一种通用解法——解决矩阵填数问题

1.定义方向向量

int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0}; 

右、下、左、上（顺时针）

注意：此处坐标轴，以下为x正方向，以右为y正方向。因为要和二维数组相适应

2.根据规则结合方向向量填数

• 超一个方向走，一边走一边填数，直到越界

• 越界之后，结合方向向量，重新计算出新的坐标以及方向

#include<iostream>
​
using namespace std;
​
const int N = 15;
//判断坐标（x，y）中是否已经填数
int arr[N][N];
​
//定义方向向量
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
​
​
int main()
{//处理输入int n = 0;cin >> n;
​//模拟填数过程int x = 1,y = 1;int pos = 0;//方向int cnt = 1;//填的数字while(cnt <= n*n){arr[x][y] = cnt;//计算下一个位置int a = x + dx[pos],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];}//更新坐标x = a,y = b;cnt++;}//输出for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){printf("%3d",arr[i][j]);}cout << endl;}
​return 0;
}

1.3 字符串展开

题目链接：P1098 [NOIP 2007 提高组] 字符串的展开 - 洛谷 纯模拟+考察基础代码能力

对于复杂的条件判断，建议封装函数，这样代码较为简洁，方便debug

C++ 标准库中有 （判断是否为数字）和 isalpha （判断是否为字母）这两个函数，它们是 C 标准库函数，在 <cctype> 头文件中定义（对应 C 语言中的 <ctype.h>）

还有类似的函数：

• isalnum：判断是否是字母或数字

• isspace：判断是否是空白字符（如空格、换行、制表符等）

• islower / isupper：判断是否是小写或大写字母

• tolower / toupper：转换为小写或大写

此题我们会用到 isdigit 和 islower

#include<iostream>
#include<algorithm> // 调用reverse函数
#include<cctype> // 调用isdigit和islower函数
using namespace std;
​
string s;
string ret;
int p1,p2,p3,n;
​
void add(char left,char right)
{string t;//遍历其中的字符for(char ch = left + 1;ch < right;ch++){char tmp = ch;//处理p1if(p1 == 2 && islower(tmp)) tmp -= 32; //注意只对字母字符改变大小写else if(p1 == 3) tmp = '*';//处理p2for(int i = 0;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((isdigit(left) && isdigit(right) && right > left) ||(islower(left) && islower(right) && right > left)){add(left,right);}else{ret += ch;}}}cout << ret << endl;return 0;
}

二、高精度

当数据的值特别大，各种类型都存不下的时候，此时就要用高精度算法来计算加减乘除；

• 先用字符串读入这个数，然后用数组逆序存储该数的每一位

• 利用数组，模拟加减乘除运算的过程

高精度算法本质上还是模拟算法，用代码模拟小学列竖式计算加减乘除的过程

2.1 高精度加法

题目链接：P1601 A+B Problem（高精） - 洛谷

算法原理：

• 模拟小学列竖式计算的过程

• 先用字符串读入，拆分每一位，逆序放在数组中

• 利用数组，模拟小学列竖式计算加法的过程（对应位相加，加上进位，处理进位，处理余数）

#include<iostream>
using namespace std;
​
const int N = 1e6 + 10;
int a[N],b[N],c[N];
int la,lb,lc; // 记录数字位数
​
//高精度加法的模板 ---  c = a + b;
void add(int a[],int b[],int c[])
{for(int i = 0;i < lc;i++){c[i] += a[i] + b[i]; // 对应位相加，再加上进位c[i+1] = c[i] / 10; // 处理进位c[i] %= 10; // 处理余数}if(c[lc]) lc++; // 处理边界情况，如果最后一位进位，则...
}
​
​
int main()
{string x,y;cin >> x >> y;//1.拆分每一位，逆序放在数组中la = x.size(); lb = y.size(); lc = max(la,lb);for(int i = 0;i < la;i++) a[la - 1 - i] = x[i] - '0';// 这里还是字符，得转换为数字进行加法for(int i = 0;i < lb;i++) b[lb - 1 - i] = y[i] - '0';//2.模拟加法过程add(a,b,c);//输出结果for(int i = lc - 1;i >= 0;i--) cout << c[i];cout << endl;return 0;
}

2.2 高精度减法

题目链接：P2142 高精度减法 - 洛谷

算法原理：

• 先比较大小，然后用较大得数减去较小的数 —— 先比较长度，再按字典序比较

• 先用字符串读入，然后拆分每一位，逆序放进数组中

• 利用数组，模拟列竖式减法的过程

  • 先是对应位相减，然后处理借位

  • 如果减的结果小于0，往前借一位，然后这一位加上10

#include<iostream>
using namespace std;
​
const int N = 1e6 + 10;
​
int a[N],b[N],c[N]; // a - 被减数 b - 减数
int la,lb,lc;
​
//比大小
bool cmp(string& x,string& y)
{//先比较长度if(x.size() != y.size()) return x.size() < y.size();//再按照字典序的方式比较return x < y;
}
​
//高精度减法的模板 —— c = a - b
void sub(int a[],int b[],int c[])
{for(int i = 0;i < lc;i++){c[i] += a[i] - b[i]; // 对应位相减，然后处理借位，此处必须是+=，不能是=if(c[i] < 0){c[i] += 10;c[i+1] -= 1;//借位}}//处理前导0while(lc > 1 && c[lc-1] == 0) lc--;
}
​
int main()
{string x,y;cin >> x >> y;
​//比大小if(cmp(x,y)){swap(x,y);cout << '-';}//1.拆分每一位，逆序放在数组中la = x.size(); lb = y.size(); lc = max(la,lb);for(int i = 0;i < la;i++) a[la - 1 - i] = x[i] - '0';for(int i = 0;i < lb;i++) b[lb - 1 - i] = y[i] - '0';
​//2.模拟减法过程sub(a,b,c);//输出结果for(int i = lc - 1;i >= 0;i--) cout << c[i];cout << endl;return 0;
}

2.3 高精度乘法

题目链接：P1303 A*B Problem - 洛谷

算法原理 —— 模拟列竖式过程

• 先用字符串读入，然后拆分每一位，逆序放在数组中

• 利用数组，模拟列竖式乘法过程

  （采取无进位相乘，然后相加，最后处理进位）

          1  2  3 *4  5  6—————————6  12 185 10 154 8 12——————————————4 13 28 27 181  3  2  1    <—— 处理进位——————————————5  6  0  8  8

#include<iostream>
​
using namespace std;
​
const int N = 1e6 + 10;
int a[N],b[N],c[N];
int la,lb,lc;
​
//高精度乘法模板 —— c = a * b
void mul(int a[],int b[],int c[])
{//无进位相乘，再相加for(int i = 0;i < lc;i++){for(int j = 0;j < lb;j++){c[i + j] += a[i] * b[j];}}//处理进位for(int i = 0;i < lc;i++){c[i+1] += c[i] / 10;c[i] %= 10;}//处理前导0while(lc > 1 && c[lc-1] == 0) lc--;
}
​
​
int main()
{string x,y; cin >> x >> y;la = x.size();lb = y.size();lc = la + lb;//1.拆分每一位，逆序放在数组中for(int i = 0;i < la;i++) a[la - 1 - i] = x[i] - '0';for(int i = 0;i < lb;i++) b[lb - 1 - i] = y[i] - '0';//2.模拟无进位乘法过程mul(a,b,c);for(int i = lc - 1;i >= 0;i--) cout << c[i];cout << endl;return 0;
}

2.4 高精度除法（高精度 / 低精度）

题目链接：P1480 A/B Problem - 洛谷

算法原理：

• 存数不赘述

• 模拟小学列竖式计算两数相除过程

  • 定义一个指针 i 从高位遍历被除数，一个变量 t 标记当前被除的数，记除数是 b ；

  • 更新一个当前被除的数 t = t * 10 + a[i];

  • t / b 表示这一位的商，t % b 表示这一位的余数

  • 用 t 记录这一次的余数，遍历到下一位的时候重复上面的过程

• 注意前导 0

#include<iostream>
using namespace std;
​
typedef long long LL;
​
const int N = 1e6 + 10;
int a[N],b,c[N];
int la,lc;
​
//高精度除法的模板 ——  c = a / b; 高精度 / 低精度
void sub(int a[],int b,int c[])
{LL t = 0;//标记每次除完之后的余数for(int i = la - 1;i >= 0;i--){//计算当前的被除数t = t * 10 + a[i];c[i] = t / b;t %= b;}//处理前导0while(lc > 1 && c[lc-1] == 0) lc--;
}
​
int main()
{string x; cin >> x;cin >> b;la = x.size();lc = la;for(int i = 0;i < la;i++) a[la - 1 - i] = x[i] - '0';sub(a,b,c);//模拟除法的过程for(int i = lc - 1;i >= 0;i--) cout << c[i];cout << endl;return 0;
}