elva

大数求和

Declaration

  该文为本人原创,如需转载,请注名原作者和本站地址,但未经本人同意,严禁用于商业途径。

Text

  由于系统硬件的限制,我们无法直接进行大数的求和,但是采取一些存储方面的技术来解决这个问题。下面通过引入字符数组,并运用小学就学习过的进位求和算法来进行大数的求和运算。这里只实现了大整数的求和,如果需要运用到小数求和里头,需要改动才行。

Code

/*
 * FILE: lns.c
 * Funciton: Count the sum of two large numbers
 */


/*
 * Author: Wu Zhangjin, <zhangjinw@gmail.com>
 * (c) 2006-11-25 dslab.lzu.edu.cn Lanzhou University
 * License GPL Version 2
 */


#include <stdio.h>        /* standard input/output functions */
#include <string.h>         /* strlen function */
#define MAX_DIGITS 10000    /* define your max digit here */

/**
 * sumof_ln - count the sum of two large numbers
 * @ln_arr: the address of the array which store the two string of larger numbers
 *
 * Description:
 * For the restrictions of the hardware, we can not count the sum of two
 * large numbers directly, but we can use some skills to work it out.
 * This function use a char array to store the large numbers, and then
 * add every char digit with the carry, until the leftmost digit. Notes that
 * if the digit of two numbers is not equal,The left aligned digit should be
 * treated espectically--you should add a carry if it exist on every left digit.
 * And also if the last carry exist,the leftmost digit should be '1'
 *
 * Returns:
 * the address point of the string of sum
 *
 * Notes:
 * you can define the maximum digit of the number by the macro MAX_DIGITS
 */


char* sumof_ln(char ln_arr[2][MAX_DIGITS])
{
    int digit_arr[2], carry, sindex, lindex, i, tmp, align_lindex;
    
    carry = 0;
    digit_arr[0] = strlen(ln_arr[0]);
    digit_arr[1] = strlen(ln_arr[1]);
    sindex = (digit_arr[0] < digit_arr[1])?0:1;
    lindex = 1 - sindex;
    align_lindex = digit_arr[lindex] - digit_arr[sindex];

    for (i = digit_arr[sindex] - 1; i >= 0; i --) {
        tmp = ln_arr[lindex][align_lindex + i] + ln_arr[sindex][i] + carry;
        ln_arr[lindex][align_lindex + i] = tmp - 48 - 10 * (carry = (tmp >= 106?1:0));
    }

    if (digit_arr[0] != digit_arr[1])
    for (i = align_lindex - 1; i >= 0 && carry; i --)    {
        tmp = ln_arr[lindex][i] + carry;
        ln_arr[lindex][i] = tmp - 10 * (carry = (tmp >= 58?1:0));

    }

    if (carry) {
        for (i = digit_arr[lindex] - 1; i >= 0; i --)
            ln_arr[lindex][i+1] = ln_arr[lindex][i];
        ln_arr[lindex][digit_arr[lindex] + 1] = '\0';
        ln_arr[lindex][0] = '1';
    }    

    return ln_arr[lindex];
}

/**
 * main - main function to call function sumof_ln
 * Description:
 * compile and link this c program and input two larger numbers, you can get the sum of them
 *
 * Notes:
 * you cannot input a number whose digit is larger than MAX_DIGITS, but you can change by modifying the macro.
 */


int main(int argc, char *argv[])
{
    char ln_arr[2][MAX_DIGITS];

    printf("Please input two large numbers: \n");
    scanf("%s %s", ln_arr[0], ln_arr[1]);

    printf("The sum is:\n%s\n", sumof_ln( ln_arr ));    
}


Demo

shell> make lns
cc     lns.c   -o lns
shell> ./lns
Please input two large numbers:
9
1
The sum is:
10
shell> ./lns
Please input two large numbers:
999999999999999999999999999999999999999999999999999999999999999999999999999999999
1
The sum is:
1000000000000000000000000000000000000000000000000000000000000000000000000000000000
shell> ./lns
Please input two large numbers:
5644687481748485751785757181534145412178758718715875187687867168716841687186716876841688676
45848587878456465146861787116876871687168418178718718768465167867817617687116761867187187971971971954521278
The sum is:
45848587878456470791549268865362623472925599712864130947223886583692805374983930584028875158688848796209954
shell> ./lns
Please input two large numbers:
144
2546
The sum is:
2690

posted on 2007-08-15 17:54 叶子 阅读(1237) 评论(0)  编辑 收藏 引用 所属分类: C\C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理