用cpp实现高精度幂,不用vector
时间: 2023-02-09 16:31:50 浏览: 77
可以使用字符串来实现高精度幂。
实现思路如下:
1. 将幂次n转换为二进制形式,便于进行快速幂计算。
2. 初始化结果为1。
3. 使用循环,每次将结果乘上底数,如果当前二进制位为1。
4. 将底数平方,并转移到下一次循环。
5. 重复步骤3和4,直到所有二进制位都处理完。
以下是参考代码:
```
std::string pow(std::string base, int exponent) {
std::string result = "1";
while (exponent > 0) {
if (exponent & 1) {
result = multiply(result, base);
}
base = multiply(base, base);
exponent >>= 1;
}
return result;
}
```
请注意,上面的代码需要额外实现高精度乘法函数。
相关问题
高精度小数加法不用vector
以下是一个高精度小数加法的 C++ 实现,使用了字符串来存储小数,并且支持任意精度。假设输入的两个小数 a 和 b 都是非负数,且小数位数不超过 1000。
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string add(string a, string b) {
int lena = a.length(), lenb = b.length();
if (lena < lenb) {
swap(a, b);
swap(lena, lenb);
}
int carry = 0;
string res = "";
int p = lena - 1, q = lenb - 1;
while (q >= 0) {
int sum = a[p] - '0' + b[q] - '0' + carry;
res += to_string(sum % 10);
carry = sum / 10;
p--;
q--;
}
while (p >= 0) {
int sum = a[p] - '0' + carry;
res += to_string(sum % 10);
carry = sum / 10;
p--;
}
if (carry) {
res += to_string(carry);
}
reverse(res.begin(), res.end());
return res;
}
int main() {
string a, b;
cin >> a >> b;
string ans = add(a, b);
int dot = ans.find('.');
if (dot == string::npos) { // 如果没有小数部分
cout << ans << endl;
} else { // 如果有小数部分
int len = ans.length() - 1; // 最后一位的下标
while (len > dot && ans[len] == '0') { // 去除末尾的 0
len--;
}
if (len == dot) { // 如果小数部分为 0
ans.erase(dot); // 删掉小数点
} else { // 如果小数部分不为 0
ans.erase(len + 1); // 删掉多余的 0
}
if (ans[0] == '0') { // 如果整数部分为 0
ans.erase(0, 1); // 删掉前导 0
}
cout << ans << endl;
}
return 0;
}
```
对于输入的两个小数 a 和 b,我们直接使用上一题的高精度小数加法来计算它们的和。计算完毕后,根据小数点的位置,判断是否有小数部分。如果没有小数部分,则直接输出整个字符串;如果有小数部分,则去除末尾的 0,然后判断小数部分是否为 0,如果是则删掉小数点,否则删掉多余的 0。最后,如果整数部分为 0,则删掉前导 0。
需要注意的是,上面的代码假设输入的小数部分没有前导 0,例如 `2.5` 和 `3.0`,而不是 `2.500` 和 `3.000`。如果输入的小数部分有前导 0,那么在计算时需要先把前导 0 去掉。
帮忙用cpp写一个高精度除法的项目,不用vector
### 回答1:
高精度除法的实现方法有很多,下面是一种使用数组实现的示例代码:
```
#include <iostream>
using namespace std;
const int N = 1005;
int a[N], b[N], c[N];
void div(int *a, int *b, int *c, int &lenc) {
int len_a = a[0], len_b = b[0];
for (int i = 1; i <= len_a; i++) c[i] = a[i];
c[0] = len_a - len_b + 1;
for (int i = c[0]; i >= 1; i--) {
c[i] = 0;
while (c[i] * (b[1] * 10 + b[2]) <= (c[i + 1] * 10 + c[i + 2])) {
c[i]++;
}
for (int j = 1; j <= len_b; j++) {
c[i + j - 1] -= c[i] * b[j];
}
for (int j = i + len_b - 1; j >= i; j--) {
if (c[j] < 0) {
c[j] += 10;
c[j - 1]--;
}
}
}
while (c[0] > 1 && !c[c[0]]) c[0]--;
lenc = c[0];
}
int main() {
int len_a, len_b, len_c;
cin >> len_a;
for (int i = 1; i <= len_a; i++) cin >> a[i];
cin >> len_b;
for (int i = 1; i <= len_b; i++) cin >> b[i];
div(a, b, c, len_c);
for (int i = len_c; i >= 1; i--) cout << c[i];
return 0;
}
```
这里用数组模拟高精度除法的过程,需要注意的是,除数和被除数需要从高位到低位存储,且需要判断余数是否为0。
希望这个示例代码能帮到你。
### 回答2:
要用C++编写一个高精度除法的项目,不使用vector,可以使用字符串和数组来处理高精度数的运算。以下是一个简单的实现示例:
首先,我们需要实现一个函数将字符串转换为数组,并且反转数组的顺序:
```cpp
void strToArr(string num, int* arr) {
int len = num.length();
for (int i = 0; i < len; i++) {
arr[i] = num[len-i-1] - '0';
}
}
```
接下来,我们可以实现一个除法函数:
```cpp
string divide(string dividend, string divisor, int precision) {
int a[precision+1] = {0}; // 定义一个数组用于保存结果
int dividendArr[dividend.length()];
int divisorArr[divisor.length()];
strToArr(dividend, dividendArr);
strToArr(divisor, divisorArr);
int dividendLen = dividend.length();
int divisorLen = divisor.length();
int remainder = 0; // 余数
int idx = 0; // 商数数组的下标
for (int i = dividendLen-1; i >= 0; i--) {
int curr = dividendArr[i] + remainder * 10;
a[idx++] = curr / divisorArr[0]; // 取商
remainder = curr % divisorArr[0]; // 更新余数
// 长除法
for (int j = divisorLen-1; j >= 0; j--) {
curr = curr % 10; // 当前的除数
curr = curr * 10 + dividendArr[i-j-1]; // 添加下一位被除数
if (curr / divisorArr[j] >= 1) { // 如果可以整除
curr %= divisorArr[j];
a[idx-1] += 1; // 对应位的商数加1
}
}
}
string result = "";
bool leadingZero = true;
// 将除法结果转为字符串
for (int i = precision-1; i >= 0; i--) {
if (leadingZero && a[i] == 0)
continue;
leadingZero = false;
result += to_string(a[i]);
}
return result;
}
```
这是一个简单的高精度除法函数的实现,可以通过传入被除数、除数和所需的精度来得到除法结果。
注意,这个实现示例仅适用于除数和被除数都是正整数的情况,且结果仅包含整数部分(不包含小数部分)。对于更复杂的情况(例如带有小数的除法),需要额外的处理。
### 回答3:
要实现高精度除法的功能,可以使用C++语言编写一个项目。以下是示例代码:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000; //定义最大位数
int a[MAXN], b[MAXN], c[MAXN];
void divide(int a[], int b[], int c[]) {
int len_a = strlen(a);
int len_b = strlen(b);
memset(c,0,sizeof(c)); //初始化结果数组c
int j=0, tmp;
for (int i = 0; i < len_a; i++) {
tmp = j * 10 + a[i] - '0'; //当前余数乘以10加上下一位被除数
j = tmp % b;
c[i] = tmp / b;
}
}
int main() {
char str_a[MAXN];
char str_b[MAXN];
cin >> str_a >> str_b;
for (int i = 0; i < strlen(str_a); i++)
a[i] = str_a[i] - '0';
for (int i = 0; i < strlen(str_b); i++)
b[i] = str_b[i] - '0';
divide(a, b, c);
//输出结果
bool left_zero = true;
for (int i = MAXN - 1; i >= 0; i--) {
if (left_zero && c[i] == 0)
continue;
else
left_zero = false;
cout << c[i];
}
return 0;
}
```
这是一个简单的高精度除法实现。我们首先将两个被除数和除数的字符串形式转换成整数数组,然后通过除法计算生成商的整数数组。最后,我们遍历商的数组,从最高位开始输出结果。
这个示例项目没有使用`vector`,而是使用了定长的整数数组进行运算。你可以根据自己的需求和对C++语言的熟悉程度进行相应的修改和优化。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)