2015年蓝桥杯国赛C组机器人繁殖题解析：高精度整数代码实现与解题思路

rhsgfswg

一、题目解读

2015年蓝桥杯国赛C组“机器人繁殖”问题要求求解机器人按月繁殖的累计数量。题目设定初始机器人数量为a，每月新增b台，需计算n个月后总机器人数。由于繁殖数量可能呈指数级增长，普通整数类型无法存储结果，因此需采用高精度整数运算解决。

二、解题思路

核心在于自定义高精度整数类（BigInt），支持加法、减法及乘法操作。解题关键在于利用高精度加法模拟每月繁殖过程：每月总数为上月总数+新增数量，通过循环迭代计算n个月后的累计值。高精度处理避免了数据溢出，确保结果正确性。

三、解题步骤

1. 初始化：读入初始数量a、新增量b及月份n，将a、b转换为高精度整数对象。

2. 循环迭代：通过循环执行n次加法操作，每次将当前总数加上b，更新总数。

3. 输出结果：将最终高精度整数转换为字符串输出，确保格式正确。

四、代码与注释

1. #include <iostream>
   
2. #include <string>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. // 高精度整数类
   
7. class BigInt {
   
8. private:
   
9. vector<int> digits; // 存储数字各位（逆序）
   
10. bool isNegative; // 负数标记
    
11. 
    
12. public:
    
13. BigInt() : isNegative(false) {} // 默认构造函数
    
14. BigInt(string s) { // 字符串初始化
    
15. if (s.empty()) return;
    
16. isNegative = (s[0] == '-'); // 处理负号
    
17. for (int i = s.size() - 1; i >= (isNegative? 1 : 0); --i) {
    
18. digits.push_back(s[i] - '0'); // 逆序存储数字字符
    
19. }
    
20. }
    
21. 
    
22. // 加法
    
23. BigInt operator+(const BigInt& other) const {
    
24. BigInt result;
    
25. int carry = 0; // 进位
    
26. int maxLen = max(digits.size(), other.digits.size());
    
27. 
    
28. for (int i = 0; i < maxLen || carry; ++i) {
    
29. int sum = carry;
    
30. if (i < digits.size()) sum += digits[i];
    
31. if (i < other.digits.size()) sum += other.digits[i];
    
32. result.digits.push_back(sum % 10);
    
33. carry = sum / 10;
    
34. }
    
35. 
    
36. return result;
    
37. }
    
38. 
    
39. // 减法
    
40. BigInt operator-(const BigInt& other) const {
    
41. BigInt result;
    
42. int borrow = 0; // 借位
    
43. 
    
44. for (int i = 0; i < digits.size(); ++i) {
    
45. int diff = digits[i] - borrow;
    
46. if (i < other.digits.size()) diff -= other.digits[i];
    
47. if (diff < 0) {
    
48. diff += 10;
    
49. borrow = 1;
    
50. } else {
    
51. borrow = 0;
    
52. }
    
53. result.digits.push_back(diff);
    
54. }
    
55. 
    
56. // 去除前导零
    
57. while (result.digits.size() > 1 && result.digits.back() == 0) {
    
58. result.digits.pop_back();
    
59. }
    
60. 
    
61. return result;
    
62. }
    
63. 
    
64. // 乘法
    
65. BigInt operator*(const BigInt& other) const {
    
66. BigInt result;
    
67. result.digits.resize(digits.size() + other.digits.size(), 0);
    
68. 
    
69. for (int i = 0; i < digits.size(); ++i) {
    
70. int carry = 0;
    
71. for (int j = 0; j < other.digits.size() || carry; ++j) {
    
72. long long product = result.digits[i + j] +
    
73. (long long)digits[i] * (j < other.digits.size() ? other.digits[j] : 0) +
    
74. carry;
    
75. result.digits[i + j] = product % 10;
    
76. carry = product / 10;
    
77. }
    
78. }
    
79. 
    
80. // 去除前导零
    
81. while (result.digits.size() > 1 && result.digits.back() == 0) {
    
82. result.digits.pop_back();
    
83. }
    
84. 
    
85. return result;
    
86. }
    
87. 
    
88. // 除法
    
89. BigInt operator/(const BigInt& other) const {
    
90. BigInt quotient, remainder;
    
91. 
    
92. for (int i = digits.size() - 1; i >= 0; --i) {
    
93. remainder = remainder * BigInt("10") + BigInt(to_string(digits[i]));
    
94. int count = 0;
    
95. while (remainder >= other) {
    
96. remainder = remainder - other;
    
97. count++;
    
98. }
    
99. quotient.digits.insert(quotient.digits.begin(), count);
    
100. }
     
101. 
     
102. // 去除前导零
     
103. while (quotient.digits.size() > 1 && quotient.digits.back() == 0) {
     
104. quotient.digits.pop_back();
     
105. }
     
106. 
     
107. return quotient;
     
108. }
     
109. 
     
110. // 比较运算符
     
111. bool operator>=(const BigInt& other) const {
     
112. if (digits.size() != other.digits.size()) {
     
113. return digits.size() > other.digits.size();
     
114. }
     
115. for (int i = digits.size() - 1; i >= 0; --i) {
     
116. if (digits[i] != other.digits[i]) {
     
117. return digits[i] > other.digits[i];
     
118. }
     
119. }
     
120. return true;
     
121. }
     
122. 
     
123. // 输出
     
124. friend ostream& operator<<(ostream& os, const BigInt& num) {
     
125. for (int i = num.digits.size() - 1; i >= 0; --i) {
     
126. os << num.digits[i];
     
127. }
     
128. return os;
     
129. }
     
130. };
     
131. 
     
132. // 计算2的幂
     
133. BigInt powerOfTwo(int n) {
     
134. BigInt result("1");
     
135. for (int i = 0; i < n; ++i) {
     
136. result = result * BigInt("2");
     
137. }
     
138. return result;
     
139. }
     
140. 
     
141. int main() {
     
142. int n;
     
143. string s_str;
     
144. cin >> n >> s_str;
     
145. BigInt s(s_str);
     
146. 
     
147. // 计算分子部分: s + 2^(n+1) - n - 2
     
148. BigInt two_pow_n1 = powerOfTwo(n + 1);
     
149. BigInt numerator = s + two_pow_n1 - BigInt(to_string(n + 2));
     
150. 
     
151. // 计算分母部分: 2^(n+1) - 1
     
152. BigInt denominator = two_pow_n1 - BigInt("1");
     
153. 
     
154. // 计算结果: x = numerator / denominator
     
155. BigInt x = numerator / denominator;
     
156. 
     
157. cout << x << endl;
     
158. 
     
159. return 0;
     
160. }

复制代码

五、总结

本解法通过高精度整数类高效处理大数运算，核心在于加法操作的迭代应用。代码设计简洁，通过vector存储数字各位，支持动态扩展，适用于类似需要大数计算的竞赛题目。同时，减法与乘**能的实现为扩展其他复杂运算提供了基础。

来源：蓝桥杯题解