2015年蓝桥杯国赛C组机器人繁殖题解析：高精度整数代码实现与解题思路
2个月前 (07-19)
一、题目解读
2015年蓝桥杯国赛C组“机器人繁殖”问题要求求解机器人按月繁殖的累计数量。题目设定初始机器人数量为a，每月新增b台，需计算n个月后总机器人数。由于繁殖数量可能呈指数级增长，普通整数类型无法存储结果，因此需采用高精度整数运算解决。
二、解题思路
核心在于自定义高精度整数类（BigInt），支持加法、减法及乘法操作。解题关键在于利用高精度加法模拟每月繁殖过程：每月总数为上月总数+新增数量，通过循环迭代计算n个月后的累计值。高精度处理避免了数据溢出，确保结果正确性。
三、解题步骤
1. 初始化：读入初始数量a、新增量b及月份n，将a、b转换为高精度整数对象。
2. 循环迭代：通过循环执行n次加法操作，每次将当前总数加上b，更新总数。
3. 输出结果：将最终高精度整数转换为字符串输出，确保格式正确。
四、代码与注释
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 高精度整数类
class BigInt {
private:
vector<int> digits; // 存储数字各位（逆序）
bool isNegative; // 负数标记
public:
BigInt() : isNegative(false) {} // 默认构造函数
BigInt(string s) { // 字符串初始化
if (s.empty()) return;
isNegative = (s[0] == '-'); // 处理负号
for (int i = s.size() - 1; i >= (isNegative? 1 : 0); --i) {
digits.push_back(s[i] - '0'); // 逆序存储数字字符
}
}
// 加法
BigInt operator+(const BigInt& other) const {
BigInt result;
int carry = 0; // 进位
int maxLen = max(digits.size(), other.digits.size());
for (int i = 0; i < maxLen || carry; ++i) {
int sum = carry;
if (i < digits.size()) sum += digits[i];
if (i < other.digits.size()) sum += other.digits[i];
result.digits.push_back(sum % 10);
carry = sum / 10;
}
return result;
}
// 减法
BigInt operator-(const BigInt& other) const {
BigInt result;
int borrow = 0; // 借位
for (int i = 0; i < digits.size(); ++i) {
int diff = digits[i] - borrow;
if (i < other.digits.size()) diff -= other.digits[i];
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
result.digits.push_back(diff);
}
// 去除前导零
while (result.digits.size() > 1 && result.digits.back() == 0) {
result.digits.pop_back();
}
return result;
}
// 乘法
BigInt operator*(const BigInt& other) const {
BigInt result;
result.digits.resize(digits.size() + other.digits.size(), 0);
for (int i = 0; i < digits.size(); ++i) {
int carry = 0;
for (int j = 0; j < other.digits.size() || carry; ++j) {
long long product = result.digits[i + j] +
(long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) +
carry;
result.digits[i + j] = product % 10;
carry = product / 10;
}
}
// 去除前导零
while (result.digits.size() > 1 && result.digits.back() == 0) {
result.digits.pop_back();
}
return result;
}
// 除法
BigInt operator/(const BigInt& other) const {
BigInt quotient, remainder;
for (int i = digits.size() - 1; i >= 0; --i) {
remainder = remainder * BigInt("10") + BigInt(to_string(digits[i]));
int count = 0;
while (remainder >= other) {
remainder = remainder - other;
count++;
}
quotient.digits.insert(quotient.digits.begin(), count);
}
// 去除前导零
while (quotient.digits.size() > 1 && quotient.digits.back() == 0) {
quotient.digits.pop_back();
}
return quotient;
}
// 比较运算符
bool operator>=(const BigInt& other) const {
if (digits.size() != other.digits.size()) {
return digits.size() > other.digits.size();
}
for (int i = digits.size() - 1; i >= 0; --i) {
if (digits[i] != other.digits[i]) {
return digits[i] > other.digits[i];
}
}
return true;
}
// 输出
friend ostream& operator<<(ostream& os, const BigInt& num) {
for (int i = num.digits.size() - 1; i >= 0; --i) {
os << num.digits[i];
}
return os;
}
};
// 计算2的幂
BigInt powerOfTwo(int n) {
BigInt result("1");
for (int i = 0; i < n; ++i) {
result = result * BigInt("2");
}
return result;
}
int main() {
int n;
string s_str;
cin >> n >> s_str;
BigInt s(s_str);
// 计算分子部分: s + 2^(n+1) - n - 2
BigInt two_pow_n1 = powerOfTwo(n + 1);
BigInt numerator = s + two_pow_n1 - BigInt(to_string(n + 2));
// 计算分母部分: 2^(n+1) - 1
BigInt denominator = two_pow_n1 - BigInt("1");
// 计算结果: x = numerator / denominator
BigInt x = numerator / denominator;
cout << x << endl;
return 0;
}五、总结
本解法通过高精度整数类高效处理大数运算，核心在于加法操作的迭代应用。代码设计简洁，通过vector存储数字各位，支持动态扩展，适用于类似需要大数计算的竞赛题目。同时，减法与乘法功能的实现为扩展其他复杂运算提供了基础。
原创内容 转载请注明出处
