返回顶部

收藏

C++解决大数据的加法、减法、乘法以及阶乘的计算问题

更多

限于数据类型的长度有限,对于大数据的计算就无能为力了,这里主要是采用字符数组解决精度问题。

加法、减法的思路差不多,主要就是采用我们固有的思维来计算,直接一位一位地相加。减法的话,先

判断2个数的大小,让较大的数始终在前面,并且改变相应的数据长度,把结果放在一个临时的缓冲区里面。

计算完毕后,再把数据写入到用户的缓冲区中,并且除去前面多余的0。乘法的计算就有点不同了,最大的

不同之处就是在于我们自己算乘法的时候还要算加法,这里我把加法合到了算乘法的过程中,也免除了溢出的

危险,计算量也小些了,每一位乘之前取结果当前位的值保存起来,然后连带进位一起加起来,就避免了最后

算加法的问题。

算阶乘的时候,主要就是确定该给临时缓冲区分配多大内存。最后大概算了下,一位数分配11个,两位数就分配21个,

三位数就分配3*1。专门写了个函数用于返回分配数量大小。分配3个这么大的缓冲区,一个存取当前每一次的计算结果(逆序表示),

第二个复制该结果(逆序表示),第三个存取待乘的数据(顺序表示)。还是乘法结束后,加法也完毕了,然后进入下一次乘法。

怎么想的就是怎么做的。用gcc编译的时候,注意带上-lm选项,链接math库,下边是一个带简单错误处理的demo以及源代码。

#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;
}

标签:大数据,四则运算,C++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. 数据有意思 发表 2017-07-13 05:36:49 Python调用C模块以及性能分析
  2. 数控小V 发表 2017-01-10 03:17:42 入门必读 机器学习六大开发语言
  3. 博主 发表 2014-07-06 00:00:00 Javascript 开发者玩转 C++
  4. 博主 发表 2014-07-21 14:14:00 《Effecticve Modern C++》预览
  5. 博主 发表 2015-04-29 03:01:59 LinkedIn运行大规模的Kafka集群
  6. 博主 发表 2014-01-31 00:36:00 Spark开发环境的配置
  7. mortoray 发表 2015-03-06 06:56:04 Visions of generics and templates: How parametrics
  8. oldim 发表 2014-08-26 14:33:53 intel c++ 高性能运算工具
  9. Jiaxing 发表 2015-02-22 16:18:38 Julia语言介绍(二)多维数组
  10. coleflowers 发表 2013-07-31 07:00:00 用EditPlus和MinGW搭建C++开发环境
  11. Sun 发表 2013-03-07 02:29:30 获取Root权限的钩子
  12. 跳跳 发表 2012-01-25 12:55:17 如何避免头文件多重包含

发表评论