C语言atoi函数怎么递归实现
时间: 2023-04-08 22:03:33 浏览: 166
C语言的atoi函数可以通过递归实现,具体实现方法如下:
```c
int my_atoi(char *str) {
if (*str == '\0') {
return 0;
}
int num = my_atoi(str + 1);
return (*str - '0') + num * 10;
}
```
这个函数首先判断字符串是否为空,如果为空则返回0。否则,它会递归调用自己,将字符串指针向后移动一位,直到字符串末尾。然后,它将当前字符转换为数字,并将其加到递归调用的结果中,最后返回结果。
相关问题
C语言如何递归实现atoi函数
C语言中可以使用递归来实现atoi函数,具体实现方法如下:
```c
int my_atoi(char *str) {
if (*str == '\0') {
return 0;
}
int num = my_atoi(str + 1);
return (*str - '0') + num * 10;
}
```
这个函数会递归地将字符串转换为整数,直到字符串为空为止。每次递归时,先将字符串指针向后移动一位,然后递归调用函数,最后将当前字符转换为数字并加上之前递归得到的结果乘以10。
实现Karatsuba乘法C语言代码
下面是实现Karatsuba乘法的C语言代码,同样使用了递归的方法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 去除字符串前导0
void removeLeadingZeros(char* str) {
int i = 0;
while (str[i] == '0') {
i++;
}
if (i == strlen(str)) {
str[0] = '0';
str[1] = '\0';
} else {
memmove(str, str + i, strlen(str) - i + 1);
}
}
// Karatsuba乘法
char* karatsuba(const char* num1, const char* num2) {
int len1 = strlen(num1);
int len2 = strlen(num2);
if (len1 == 0 || len2 == 0) {
char* res = (char*)malloc(2 * sizeof(char));
res[0] = '0';
res[1] = '\0';
return res;
}
if (len1 == 1 || len2 == 1) {
int res = atoi(num1) * atoi(num2);
char* str = (char*)malloc(12 * sizeof(char)); // 最多11位数
sprintf(str, "%d", res);
return str;
}
int n = (len1 > len2 ? len1 : len2);
if (n % 2 != 0) {
n++;
}
char* x1 = (char*)malloc((n/2 + 1) * sizeof(char));
char* x0 = (char*)malloc((n/2 + 1) * sizeof(char));
char* y1 = (char*)malloc((n/2 + 1) * sizeof(char));
char* y0 = (char*)malloc((n/2 + 1) * sizeof(char));
strncpy(x1, num1, len1 - n/2);
x1[len1 - n/2] = '\0';
strncpy(x0, num1 + len1 - n/2, n/2);
x0[n/2] = '\0';
strncpy(y1, num2, len2 - n/2);
y1[len2 - n/2] = '\0';
strncpy(y0, num2 + len2 - n/2, n/2);
y0[n/2] = '\0';
char* z2 = karatsuba(x1, y1);
char* z0 = karatsuba(x0, y0);
char* x1x0 = (char*)malloc((n/2 + 1 + 1) * sizeof(char));
sprintf(x1x0, "%d", atoi(x1) + atoi(x0));
char* y1y0 = (char*)malloc((n/2 + 1 + 1) * sizeof(char));
sprintf(y1y0, "%d", atoi(y1) + atoi(y0));
char* z1 = karatsuba(x1x0, y1y0);
z1 = (char*)realloc(z1, (2 * n + 1) * sizeof(char));
int lenz1 = strlen(z1);
int i;
for (i = 0; i < lenz1; i++) {
z1[i] -= '0';
}
for (i = 0; i < n; i++) {
z1[i] += (i < lenz1 ? z1[i] + '0' : '0');
}
z1[n] = '\0';
removeLeadingZeros(z1);
z2 = (char*)realloc(z2, (2 * n + 1) * sizeof(char));
z0 = (char*)realloc(z0, (n + 1) * sizeof(char));
lenz1 = strlen(z1);
int lenz2 = strlen(z2);
for (i = 0; i < n; i++) {
z2[i] = (i < lenz2 ? z2[i] : '0');
z0[i] = (i < strlen(z0) ? z0[i] : '0');
}
z2[n] = '\0';
z0[n] = '\0';
char* res = (char*)malloc((2 * n + 1) * sizeof(char));
int carry = 0;
for (i = n - 1; i >= 0; i--) {
int sum = z2[i] + z1[i] + z0[i] - '0' - '0' - carry;
res[i+1] = sum % 10 + '0';
carry = sum / 10;
}
res[0] = carry + '0';
removeLeadingZeros(res);
free(x1);
free(x0);
free(y1);
free(y0);
free(x1x0);
free(y1y0);
free(z2);
free(z0);
free(z1);
return res;
}
int main() {
char num1[] = "123456789";
char num2[] = "987654321";
char* res = karatsuba(num1, num2);
printf("%s\n", res);
free(res);
return 0;
}
```
需要注意的是,在计算``z1``时,需要递归调用``karatsuba``函数,而最后的结果需要去除前导0。此外,为了防止溢出,数组长度需要额外加1。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)