用C++代码实现(要求高精度一万位以上,能用DEV-C++编译,不添加高精度库,):猴子摘了一堆桃,第一天吃了一半,还嫌不过瘾,又吃了一个;第二天又吃了剩下的一半又一个;以后每天如此,至第n天,猴子一看,只剩下一个了。问最初有多少个桃? 输入 n 输出 最初的桃的个数
时间: 2024-03-24 16:36:52 浏览: 49
好的,以下是用C++实现的代码,不使用任何高精度库,使用字符串模拟高精度计算。
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string add(string a, string b) {
string res = "";
int carry = 0;
for (int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0; i--, j--) {
int x = i >= 0 ? a[i] - '0' : 0;
int y = j >= 0 ? b[j] - '0' : 0;
int sum = x + y + carry;
res += to_string(sum % 10);
carry = sum / 10;
}
if (carry) {
res += to_string(carry);
}
reverse(res.begin(), res.end());
return res;
}
string sub(string a, string b) {
string res = "";
int borrow = 0;
for (int i = a.size() - 1, j = b.size() - 1; i >= 0 || j >= 0; i--, j--) {
int x = i >= 0 ? a[i] - '0' : 0;
int y = j >= 0 ? b[j] - '0' : 0;
int diff = x - y - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
res += to_string(diff);
}
reverse(res.begin(), res.end());
return res;
}
string mul(string a, int b) {
string res = "";
int carry = 0;
for (int i = a.size() - 1; i >= 0; i--) {
int x = a[i] - '0';
int prod = x * b + carry;
res += to_string(prod % 10);
carry = prod / 10;
}
if (carry) {
res += to_string(carry);
}
reverse(res.begin(), res.end());
return res;
}
string div(string a, int b) {
string res = "";
int remainder = 0;
for (int i = 0; i < a.size(); i++) {
int x = a[i] - '0';
remainder = remainder * 10 + x;
res += to_string(remainder / b);
remainder %= b;
}
while (res.size() > 1 && res[0] == '0') {
res.erase(res.begin());
}
return res;
}
int cmp(string a, string b) {
if (a.size() != b.size()) {
return a.size() < b.size() ? -1 : 1;
} else {
for (int i = 0; i < a.size(); i++) {
if (a[i] != b[i]) {
return a[i] < b[i] ? -1 : 1;
}
}
}
return 0;
}
string binary_search(string left, string right, int n) {
while (cmp(add(left, "1"), right) < 0) {
string mid = div(add(left, right), 2);
string tmp = mid, one = "1";
bool ok = true;
for (int i = 0; i < n; i++) {
if (tmp.back() == '1') {
ok = false;
break;
}
tmp = div(sub(mul(tmp, 2), one), 2);
}
if (ok) {
right = mid;
} else {
left = mid;
}
}
return right;
}
int main() {
int n;
cout << "请输入天数n:";
cin >> n;
// 初始数量的上界
string upper_bound = "1";
for (int i = 0; i < n; i++) {
upper_bound = add(mul(upper_bound, 2), "1");
}
// 二分查找
string left = "0", right = upper_bound;
string res = binary_search(left, right, n);
cout << "最初的桃的个数为:" << res << endl;
return 0;
}
```
输入天数 `n` 后,程序会使用二分查找算法求出最初的桃的个数,并输出结果。
注意,这里使用了字符串模拟高精度计算,可以实现高精度计算,但效率较低,不建议在实际应用中使用。
阅读全文