限於數據類型的長度有限,對於大數據的計算就無能為力了,這裡主要是采用字符數組解決精度問題。
加法、減法的思路差不多,主要就是采用我們固有的思維來計算,直接一位一位地相加。減法的話,先
判斷2個數的大小,讓較大的數始終在前面,並且改變相應的數據長度,把結果放在一個臨時的緩沖區裡面。
計算完畢後,再把數據寫入到用戶的緩沖區中,並且除去前面多余的0。乘法的計算就有點不同了,最大的
不同之處就是在於我們自己算乘法的時候還要算加法,這裡我把加法合到了算乘法的過程中,也免除了溢出的
危險,計算量也小些了,每一位乘之前取結果當前位的值保存起來,然後連帶進位一起加起來,就避免了最後
算加法的問題。
算階乘的時候,主要就是確定該給臨時緩沖區分配多大內存。最後大概算了下,一位數分配1*1個,兩位數就分配2*1個,
三位數就分配3*1。專門寫了個函數用於返回分配數量大小。分配3個這麼大的緩沖區,一個存取當前每一次的計算結果(逆序表示),
第二個復制該結果(逆序表示),第三個存取待乘的數據(順序表示)。還是乘法結束後,加法也完畢了,然後進入下一次乘法。
怎麼想的就是怎麼做的。用gcc編譯的時候,注意帶上-lm選項,鏈接math庫,下邊是一個帶簡單錯誤處理的demo以及源代碼。
[cpp]
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>
int ystrlen( const char* str )
{
int len;
assert( str != NULL );
len = 0;
while( (*str--) !='\0' )
{
len++;
}
return len;
}
int get_allocate_num(const int* num1, const int* num2)
{
return (*num1 >= *num2) ? *num1+1 : *num2+1;
}
void big_add(const char *num1, const char *num2, char *res)
{
//res存儲計算後的結果
int len1 = strlen(num1);
int len2 = strlen(num2);
int i, j, k, num;
char flag = 0;//進位標志
char *temp_res, temp;//臨時存取結果
num = get_allocate_num(&len1, &len2);
temp_res = (char *)malloc(num);
i = len1 - 1;
j = len2 - 1;
for (k = num - 1; k >= 0; k--) {
if (i >= 0 && j >= 0) {//加號兩邊都有數
temp = num1[i--] + num2[j--] + flag;
if (temp > 0x69) {//有進位
temp_res[k] = temp - 0x3a;
flag = 0x01;
} else {
temp_res[k] = temp - 0x30;
flag = 0x0;
}
} else if (i >= 0 && j < 0) {//加號右邊結束
temp = num1[i--] + flag;
if (temp > 0x39) {//有進位
temp_res[k] = 0x30;
flag = 0x01;
} else {
temp_res[k] = temp;
flag = 0x0;
}
} else if (i < 0 && j >= 0) {//加號左邊結束
temp = num2[j--] + flag;
if (temp > 0x39) {//有進位
temp_res[k] = 0x30;
flag = 0x01;
} else {
temp_res[k] = temp;
flag = 0x0;
}
} else {//加號左邊 右邊剛結束
temp = flag;
if (temp) {//有無進位計算此次就結束
temp_res[0] = 0x31;
strncpy(res, temp_res, num);
res[num] = '\0';
} else {//此時既無進位
strncpy(res, &temp_res[1], num-1);
res[num-1] = '\0';
}
}
}
free(temp_res);
}
int big_cmp(const char *num1, const int *len1, const char *num2, const int *len2)
{
int i;
if (*len1 > *len2) {//減數大
return 1;
} else if (*len1 < *len2) {//被減數大
return -1;
} else {
for (i = 0; i < *len1; i++) {
if (num1[i] > num2[i]) {
return 1;
} else if (num1[i] < num2[i]) {
return -1;
}
}
return 0;//2個數相等
}
}
void earse_zero(char *res, const int *num)
{//擦除多余的0
int len;
int i = 0;
char *temp;
if (res[0] == '-') {
i = 1;
while (res[i] == 0x30) {
i++;
}
if (i != 1) {
len = *num - i + 1;
temp = (char *)malloc(len);
strncpy(temp, &res[i], len);
strncpy(&res[1], temp, len);
free(temp);
}
} else {
while (res[i] == 0x30) {
i++;
}
if (i != 0) {
len = *num - i;
temp = (char *)malloc(len);
strncpy(temp, &res[i], len);
strncpy(res, temp, len);
free(temp);
}
}
}
void big_sub(const char *num1, const char *num2, char *res)
{
//res存儲計算後的結果
int len1 = strlen(num1);
int len2 = strlen(num2);
int i, j, k, num;
char flag = 0, flag_negetive = 0;//進位標志
char *temp_res, temp;//臨時存取結果
i = len1 - 1;
j = len2 - 1;
k = big_cmp(num1, &len1, num2, &len2);
if (k == 0) {
//相等
res[0] = 0x30;
res[1] = '\0';
} else {
//不等
num = get_allocate_num(&len1, &len2);
temp_res = (char *)malloc(num);
if (k == -1) {//始終讓num1指向較大數,同時也改變數據的長度
k = (int)num1;
num1 = num2;
num2 = (const char *)k;
k = i;
i = j;
j = k;
flag_negetive = 1;
}
for (k = num - 1; k > 0; k--) {
if (j >= 0) {
if (k == 1 && i == 0 && j == 0) {//位數相同
temp_res[1] = num1[0] - num2[0] - flag + 0x30;
if (flag_negetive == 1) {//結果為負數
strncpy(&res[1], &temp_res[1], num-1);
res[0] = '-';
res[num] = '\0';
} else {
strncpy(res, &temp_res[1], num-1);
res[num-1] = '\0';
}
} else {
temp = num1[i--] - num2[j--] - flag;
if (temp < 0x0) {//有借位
temp_res[k] = temp + 0x3a;
flag = 0x01;
} else {
temp_res[k] = temp + 0x30;
flag = 0x0;
}
}
} else {
temp = num1[i--] - flag;
if (k == 1) {//最後一位
if (temp > 0x30) {
temp_res[1] = temp;
if (flag_negetive == 1) {//結果為負數
temp_res[0] = '-';//添加負號
strncpy(res, temp_res, num);
res[num] = '\0';
} else {
strncpy(res, &temp_res[1], num-1);
res[num-1] = '\0';
}
} else {//有借位
if (flag_negetive == 1) {//結果是負數
temp_res[1] = '-';
strncpy(res, &temp_res[1], num-1);
res[num-1] = '\0';
} else {
strncpy(res, &temp_res[2], num-2);
res[num-2] = '\0';
}
}
} else {
if (temp >= 0x30) {
temp_res[k] = temp;
flag = 0x0;
} else {//有借位
temp_res[k] = temp + 0xa;
flag = 0x01;
}
}
}
}
free(temp_res);
earse_zero(res, &num);
}
}
void big_mul(const char *num1, const char *num2, char *res)
{
int len1 = strlen(num1);//num1為乘數
int len2 = strlen(num2);
int i, j, k;
char *temp_res, temp, temp_mul, last_res;
char flag = 0x0;
if (num1[0] == 0x30 || num2[0] == 0x30) {
res[0] = 0x30;
res[1] = '\0';
} else {
k = len1 + len2;
temp_res = (char *)malloc(k);
memset(temp_res, 0, k);
for (i = len2 - 1; i >= 0; i--) {
k = len1 + i;
for (j = len1 - 1; j >= 0; j--) {
//盡可能減少循環 每次的結果都是加了上次的結果 避免再把結果加起來
if (i == len2 - 1 || temp_res[k] == 0x0) {
//第一次乘的時候或者當前位置是0
last_res = 0x0;
} else {
//取得上一次當前位置的值
last_res = temp_res[k] - 0x30;
}
temp_mul = (num2[i] - 0x30) * (num1[j] - 0x30) + flag + last_res;//保存每一位的乘積
temp = temp_mul / 10;
if (temp > 0) {
//有余數
flag = temp;
} else {
flag = 0x0;
}
temp_res[k--] = (temp_mul % 10) + 0x30;
}
if (temp > 0 || temp_res[0] == 0x0) {
//每一次循環結束檢查最高位以及那些結果不為k位數的
temp_res[k] = flag + 0x30;
}
flag = 0x0;//重置
}
k = len1 + len2;
strncpy(res, temp_res, k);
res[k] = '\0';
k++;//包含'\0'的長度
earse_zero(res, &k);
free(temp_res);
}
}
//*num待計算階乘的數的大小,*len該數的長度
int get_fac_allocate_num(const char *num, const int *len)
{
int i, allocate_num = 0;
int data = atoi(num);
for (i = 1; i < *len; i++) {
allocate_num += i*9*pow(10, i-1);
}
allocate_num += *len*(data-pow(10, i-1)+1);//加上剩下的
return allocate_num;
}
//階乘
void big_fac(const char *num, char *res)
{
int len = strlen(num), data;
int len1, len2;
int i, j, k, m, l;
char *temp_res, temp, temp_mul, last_res;
char flag = 0x0;
data = atoi(num);
if (data > 2) {
m = get_fac_allocate_num(num, &len);
temp_res = (char *)malloc(m*3);//前m個字節保存計算結果,後2塊保存數據
memset(temp_res, 0, m*3);
strncpy(temp_res+m-len, num, len);
for (l = data - 1; l >= 2; l--) {
//乘法執行*num-2次
memcpy(temp_res+m, temp_res, m);//之前用strncpy居然沒拷貝進去,發現strncpy碰到0就不拷貝了,那要參數n干啥
sprintf(&temp_res[2*m], "%d", l);
len1 = ystrlen(&temp_res[2*m-1]);//數據是倒著存儲的,得倒著算長度
len2 = strlen(&temp_res[2*m]);
for (i = len2 - 1; i >= 0; i--) {
//k = len1 + i;
k = m - len2 + i;//定位到最後面那個數
for (j = 1; j <= len1; j++) {
//盡可能減少循環 每次的結果都是加了上次的結果 避免再把結果加起來
if (i == len2 - 1 || temp_res[k] == 0x0) {
//第一次乘的時候或者當前位置是0
last_res = 0x0;
} else {
//取得上一次當前位置的值
last_res = temp_res[k] - 0x30;
}
temp_mul = (temp_res[2*m+i] - 0x30) * (temp_res[2*m-j] - 0x30) + flag + last_res;//保存每一位的乘積
temp = temp_mul / 10;
if (temp > 0) {
//有余數
flag = temp;
} else {
flag = 0x0;
}
temp_res[k--] = (temp_mul % 10) + 0x30;
}
if (temp > 0) {
//每一次循環結束檢查最高位以及那些結果不為k位數的
temp_res[k] = flag + 0x30;
}
flag = 0x0;//重置
}
}
if (temp > 0) {
//有進位
strncpy(res, &temp_res[k], m - k);
res[m - k] = '\0';
} else {
strncpy(res, &temp_res[k+1], m - k - 1);
res[m-k-1] = '\0';
}
free(temp_res);
} else {
sprintf(res, "%d", data);
if (res[0] == 0x30) {
res[0] = 0x31;
}
}
}
void show_choice()
{
printf("**************大數計算問題****************\n");
printf("*請選擇操作類型 *\n");
printf("*1.加法 2.減法*\n");
printf("*3.乘法 4.階乘*\n");
printf("******************5.退出******************\n");
printf("******************************************\n");
}
void show_input(const char *choice)
{
char a[500], b[500], c[1000000];
switch (*choice) {
case 1:
printf("請輸入加數(輸入不是數字,後果自負): ");
scanf("%s", a);
printf("請輸入被加數(輸入不是數字,後果自負): ");
scanf("%s", b);
if (a[0] >= 0x30 && a[0] <= 0x39 || a[0] == '-' && b[0] >= 0x30 && b[0] <= 0x39 || b[0] == '-') {
if (a[0] == '-' && b[0] == '-') {
big_add(&b[1], &a[1], c);
printf("結果為: -%s\n", c);
} else if (a[0] == '-' && b[0] != '-') {
big_sub(b, &a[1], c);
printf("結果為: %s\n", c);
} else if (a[0] != '-' && b[0] == '-') {
big_sub(a, &b[1], c);
printf("結果為: %s\n", c);
} else {
big_add(a, b, c);
printf("結果為: %s\n", c);
}
} else {
printf("請輸入整數\n");
}
break;
case 2:
printf("請輸入減數(輸入不是數字,後果自負): ");
scanf("%s", a);
printf("請輸入被減數(輸入不是數字,後果自負): ");
scanf("%s", b);
if (a[0] >= 0x30 && a[0] <= 0x39 || a[0] == '-' && b[0] >= 0x30 && b[0] <= 0x39 || b[0] == '-') {
if (a[0] == '-' && b[0] == '-') {
big_sub(&b[1], &a[1], c);
printf("結果為: %s\n", c);
} else if (a[0] == '-' && b[0] != '-') {
big_add(&a[1], b, c);
printf("結果為: -%s\n", c);
} else if (a[0] != '-' && b[0] == '-') {
big_add(a, &b[1], c);
printf("結果為: %s\n", c);
} else {
big_sub(a, b, c);
printf("結果為: %s\n", c);
}
} else {
printf("請輸入整數\n");
}
break;
case 3:
printf("請輸入乘數(輸入不是數字,後果自負): ");
scanf("%s", a);
printf("請輸入被乘數(輸入不是數字,後果自負): ");
scanf("%s", b);
if (a[0] >= 0x30 && a[0] <= 0x39 || a[0] == '-' && b[0] >= 0x30 && b[0] <= 0x39 || b[0] == '-') {
if (a[0] == '-' && b[0] == '-') {
big_mul(&a[1], &b[1], c);
printf("結果為: %s\n", c);
} else if (a[0] == '-' && b[0] != '-') {
big_mul(&a[1], b, c);
printf("結果為: -%s\n", c);
} else if (a[0] != '-' && b[0] == '-') {
big_mul(a, &b[1], c);
printf("結果為: -%s\n", c);
} else {
big_mul(a, b, c);
printf("結果為: %s\n", c);
}
} else {
printf("請輸入整數\n");
}
break;
case 4:
printf("請輸入待計算階乘的數(緩沖有限,最好不要超過7位數):");
scanf("%s", a);
if (strlen(a) <= 7) {
if (a[0] < 0x30 || a[0] > 0x39) {
printf("請輸入自然數\n");
} else {
big_fac(a, c);
printf("%s! = %s\n", a, c);
}
} else {
printf("數據太大,無法計算\n");
}
break;
}
}
int main(int argc, char *argv[])
{
char choice[100];
while (1) {
show_choice();
scanf("%s", choice);
if (choice[0] >= '1' && choice[0] <= '4' && choice[1] == '\0') {
choice[0] -= 0x30;
show_input(choice);
} else if (choice[0] == '5' && choice[1] == '\0') {
printf("謝謝使用!\n");
break;
} else {
printf("無效的輸入(請看大屏幕)\n");
}
}
return 0;
}
下邊是程序運行截圖。