第十一章：算法入门——模拟与高精度¶
你好！欢迎来到第十一章！从这一章开始，我们将正式进入算法学习。算法是解决问题的步骤和方法，就像菜谱一样，告诉计算机一步一步怎么做。本章我们学习两类基础算法：模拟和高精度。
- 模拟：按照题目描述的过程，一步一步用程序实现，就像“照葫芦画瓢”。
- 高精度：当数字太大，连
long long都存不下时，我们需要用数组或字符串来存储和计算，比如求 100 的阶乘。
让我们一起探索吧！
11.1 模拟算法¶
11.1.1 什么是模拟？¶
模拟就是让计算机模仿现实世界的过程。比如，你要写一个程序模拟电梯的运行：有人按按钮，电梯就移动到那一层。你只需要按照电梯的规则一步一步写代码。
11.1.2 模拟程序范例¶
我们来看一个简单的模拟题：猜拳游戏。两个人玩石头剪刀布，规则是石头赢剪刀、剪刀赢布、布赢石头。输入两人的出拳（0代表石头，1代表剪刀，2代表布），输出谁赢。
#include <iostream>
using namespace std;
int main() {
int a, b;
cout << "请输入A和B的出拳（0石头 1剪刀 2布）：";
cin >> a >> b;
if (a == b) {
cout << "平局" << endl;
} else if ((a == 0 && b == 1) || (a == 1 && b == 2) || (a == 2 && b == 0)) {
cout << "A赢了" << endl;
} else {
cout << "B赢了" << endl;
}
return 0;
}
这就是一个简单的模拟：根据游戏规则判断胜负。
11.1.3 模拟的步骤¶
- 读懂题目：明确题目描述的规则和过程。
- 找出变量：哪些东西会变化，需要用变量表示。
- 模拟过程：用循环和判断一步步实现。
- 输出结果：根据模拟得到的结果输出。
11.1.4 模拟实例讲解¶
实例1：报数游戏（约瑟夫环简化）¶
题目：n个人围成一圈，从第1个人开始报数，数到m的人出列，然后从下一个人继续报数。输入n和m，输出出列顺序。
#include <iostream>
using namespace std;
int main() {
int n, m;
cout << "请输入总人数n和报数m：";
cin >> n >> m;
bool inGame[100] = {false}; // 标记是否还在游戏中，假设最多100人
for (int i = 0; i < n; i++) inGame[i] = true;
int count = 0; // 当前报的数
int outCount = 0; // 已经出列的人数
int i = 0; // 当前人的下标
while (outCount < n) {
if (inGame[i]) {
count++;
if (count == m) {
cout << i + 1 << " "; // 输出编号（从1开始）
inGame[i] = false;
outCount++;
count = 0;
}
}
i = (i + 1) % n; // 下一个，形成环
}
cout << endl;
return 0;
}
运行示例：
请输入总人数n和报数m：5 3
3 1 5 2 4
实例2：电梯模拟¶
题目：有一部电梯，初始在第1层。输入一系列请求，每个请求包含目标楼层和方向（上或下）。电梯每次移动一层，每移动一层花费1秒，停靠开门关门花费5秒。按请求顺序处理（即先来先服务），计算总时间。
#include <iostream>
using namespace std;
int main() {
int n;
cout << "请输入请求个数：";
cin >> n;
int currentFloor = 1;
int totalTime = 0;
for (int i = 0; i < n; i++) {
int target;
cout << "请输入目标楼层：";
cin >> target;
// 移动时间 = 楼层差绝对值
totalTime += abs(target - currentFloor);
currentFloor = target;
// 停靠时间
totalTime += 5;
}
cout << "总时间：" << totalTime << "秒" << endl;
return 0;
}
11.1.5 阶段性编程练习（模拟）¶
- 练习1：模拟一个简单的计算器。输入两个数和运算符（+、-、*、/），输出结果，注意除数为0的情况。
- 练习2：模拟一个自动售货机。商品价格5元，投入硬币（1元、5元、10元），计算总金额，如果足够支付，输出找零，否则提示金额不足。
- 练习3：模拟一个猜数字游戏（电脑随机生成1-100的数，用户猜，提示大小，直到猜中，统计次数）。
- 练习4：模拟一个排队系统。有n个人排队，每分钟处理一个人，新来的人排到队尾。输入初始队列（用数组表示），然后模拟3分钟，每分钟输出当前队首被服务，并加入一个新来的人（编号为n+1、n+2…）。
11.2 高精度算法¶
11.2.1 为什么需要高精度？¶
C++中，int 大约能存到21亿（10位），long long 大约能存到9×10^18（19位）。如果要计算 100!（约100位），或者两个100位的整数相加，普通变量就不够用了。我们需要用数组或字符串来存储每一位数字，然后模拟手工计算的过程。
11.2.2 高精度存储¶
通常用字符串读入，然后倒序存入整型数组（因为手工计算是从低位到高位）。
例如：数字 12345 存在数组里：a[0]=5, a[1]=4, a[2]=3, a[3]=2, a[4]=1。
11.2.3 高精度加法¶
两个大数相加，从低位到高位逐位相加，处理进位。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 高精度加法，返回结果字符串
string add(string s1, string s2) {
// 将字符串反转，便于从低位开始计算
reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());
// 确保s1较长
if (s1.length() < s2.length()) swap(s1, s2);
int carry = 0; // 进位
for (size_t i = 0; i < s1.length(); i++) {
int a = s1[i] - '0';
int b = i < s2.length() ? s2[i] - '0' : 0;
int sum = a + b + carry;
s1[i] = sum % 10 + '0';
carry = sum / 10;
}
if (carry) {
s1 += carry + '0'; // 最高位有进位
}
reverse(s1.begin(), s1.end());
return s1;
}
int main() {
string a, b;
cout << "请输入两个大整数：";
cin >> a >> b;
cout << "和：" << add(a, b) << endl;
return 0;
}
11.2.4 高精度减法¶
减法需要注意借位，并且要保证结果是非负的（先比较大小）。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 比较两个字符串表示的数，若a>=b返回true
bool greaterOrEqual(string a, string b) {
if (a.length() != b.length()) return a.length() > b.length();
return a >= b;
}
// 高精度减法，要求a>=b
string subtract(string a, string b) {
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
string result;
int borrow = 0;
for (size_t i = 0; i < a.length(); i++) {
int digitA = a[i] - '0' - borrow;
int digitB = i < b.length() ? b[i] - '0' : 0;
if (digitA < digitB) {
digitA += 10;
borrow = 1;
} else {
borrow = 0;
}
result += (digitA - digitB) + '0';
}
// 去除前导零
while (result.length() > 1 && result.back() == '0') {
result.pop_back();
}
reverse(result.begin(), result.end());
return result;
}
int main() {
string a, b;
cout << "请输入两个大整数（a >= b）：";
cin >> a >> b;
if (!greaterOrEqual(a, b)) {
cout << "a必须大于等于b" << endl;
} else {
cout << "差：" << subtract(a, b) << endl;
}
return 0;
}
11.2.5 高精度乘法（高精度×低精度）¶
一个大数乘以一个普通整数（如 long long 范围内）。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string multiply(string a, int b) {
reverse(a.begin(), a.end());
int carry = 0;
for (size_t i = 0; i < a.length(); i++) {
int cur = (a[i] - '0') * b + carry;
a[i] = cur % 10 + '0';
carry = cur / 10;
}
while (carry) {
a += carry % 10 + '0';
carry /= 10;
}
reverse(a.begin(), a.end());
return a;
}
int main() {
string a;
int b;
cout << "请输入大整数a和普通整数b：";
cin >> a >> b;
cout << "积：" << multiply(a, b) << endl;
return 0;
}
11.2.6 高精度乘法（高精度×高精度）¶
两个大数相乘，模拟竖式乘法。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string multiply(string a, string b) {
int lenA = a.length(), lenB = b.length();
vector<int> res(lenA + lenB, 0); // 结果最多 lenA+lenB 位
// 将字符串反转存入整型数组
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
for (int i = 0; i < lenA; i++) {
for (int j = 0; j < lenB; j++) {
res[i + j] += (a[i] - '0') * (b[j] - '0');
res[i + j + 1] += res[i + j] / 10; // 进位
res[i + j] %= 10;
}
}
// 去除前导0
while (res.size() > 1 && res.back() == 0) res.pop_back();
// 转成字符串
string result;
for (int i = res.size() - 1; i >= 0; i--) {
result += res[i] + '0';
}
return result;
}
int main() {
string a, b;
cout << "请输入两个大整数：";
cin >> a >> b;
cout << "积：" << multiply(a, b) << endl;
return 0;
}
11.2.7 高精度阶乘¶
计算 n!，n 较大时结果很长，用高精度乘法。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string multiply(string a, int b) {
// 复用之前的高精度乘低精度
reverse(a.begin(), a.end());
int carry = 0;
for (size_t i = 0; i < a.length(); i++) {
int cur = (a[i] - '0') * b + carry;
a[i] = cur % 10 + '0';
carry = cur / 10;
}
while (carry) {
a += carry % 10 + '0';
carry /= 10;
}
reverse(a.begin(), a.end());
return a;
}
string factorial(int n) {
string result = "1";
for (int i = 2; i <= n; i++) {
result = multiply(result, i);
}
return result;
}
int main() {
int n;
cout << "请输入n：";
cin >> n;
cout << n << "! = " << factorial(n) << endl;
return 0;
}
11.2.8 阶段性编程练习（高精度）¶
- 练习1：输入两个大整数，输出它们的和、差（保证非负）。
- 练习2：输入一个大整数和一个普通整数，输出它们的积。
- 练习3：计算斐波那契数列的第100项（用高精度）。
- 练习4：输入两个大整数，输出它们的乘积。
11.3 编程实例讲解¶
实例3：高精度加法应用——大数求和¶
题目：输入若干个大整数（以0结束），求它们的总和。
#include <iostream>
#include <string>
using namespace std;
string add(string a, string b) {
// 复用之前的加法代码
// ...
}
int main() {
string sum = "0", num;
while (true) {
cin >> num;
if (num == "0") break;
sum = add(sum, num);
}
cout << "总和：" << sum << endl;
return 0;
}
实例4：模拟+高精度——大数阶乘之和¶
题目：求 1! + 2! + … + n!，其中 n 较大（例如 n=50）。
#include <iostream>
#include <string>
using namespace std;
string multiply(string a, int b) { /* ... */ }
string add(string a, string b) { /* ... */ }
string factorial(int n) { /* ... */ }
int main() {
int n;
cout << "请输入n：";
cin >> n;
string sum = "0";
for (int i = 1; i <= n; i++) {
sum = add(sum, factorial(i));
}
cout << "1!+2!+...+" << n << "! = " << sum << endl;
return 0;
}
11.4 第11章编程作业¶
作业1：模拟银行排队¶
银行有2个窗口，客户到达时间和服务时间已知，模拟每个客户在哪个窗口办理，以及等待时间。输入客户数n，以及每个客户的到达时间和服务时间（整数），输出每个客户的开始服务时间和结束时间。
作业2：高精度加法器¶
编写一个程序，可以不断输入两个大整数，输出它们的和，直到用户输入”0 0”结束。
作业3：高精度乘法器¶
类似作业2，但做乘法。
作业4：大数比较¶
输入两个大整数，比较它们的大小（大于、小于、等于）。
作业5：回文数判断（高精度版）¶
输入一个很大的整数（可能100位），判断它是否是回文数（正读反读一样）。如果是，输出YES；否则输出NO。
作业6：模拟+高精度——大数进制转换¶
输入一个十进制大数（用字符串），将其转换为二进制（也用字符串输出）。
恭喜你完成了第十一章的学习！模拟是算法中最直接的思想，高精度则让我们突破了数据范围的限制。加油！🚀