首页 > 代码库 > 算法提高P1001

算法提高P1001

  当两个比较大的整数相乘时,可能会出现数据溢出的情形。为避免溢出,可以采用字符串的方法来实现两个大数之间的乘法。具体来说,首先以字符串的形式输入两个整数,每个整数的长度不会超过8位,然后把它们相乘的结果存储在另一个字符串当中(长度不会超过16位),最后把这个字符串打印出来。例如,假设用户输入为:62773417和12345678,则输出结果为:774980393241726.

输入:
  62773417 12345678

输出:
  774980393241726

主要注意的是进位的问题。。。。

 

#include <stdio.h>
#include <string.h>

void Multiply(char *s, char *s1, char *s2){
    int len,len1,i,j,k,count,tmp; //count:进位
    len = strlen(s),len1 = strlen(s1);
    for(i = 0 ; i < 16 ; i ++ )
        s2[i] = 0; //不能用memset 
    s2[16] = \0;
    for(j = len1 - 1 ; j >= 0 ; j -- ){
        count = 0;
        k = len1 - j - 1; //注意每轮开始放置的位置 
        for(i = len - 1 ; i >= 0 ; i -- ){
            tmp = (s1[j] - 0)*(s[i] - 0) + count;
            if(tmp + s2[k] - 0 > 9){
                //count与s2[k]的计算互为影响,解决办法I另设置一个变量,II在做if判断前将count计算入tmp内 
                //仍要注意count的计算在s2[k]之前 
              //count = (tmp + count + s2[k] - ‘0‘)/10;
                //s2[k] = (tmp + count + s2[k] - ‘0‘)%10 + ‘0‘; 
                count = (tmp + s2[k] - 0)/10;
                s2[k] = (tmp + s2[k] - 0)%10 + 0;
            }
            else{
                s2[k] = tmp + s2[k];
                count = 0;
            }
            k ++;    
        }
        if(count > 0) 
            s2[k] = count + 0;
    }
    //下面这种方式只能避免最后一个0,最后输出的时候还是要在非0时开始输出
    //更简单的方式是将k定义全局变量,故在输出时候不用strlen求长度 
    if(!(s2[k] > 0 || s2[k] == \0))
        s2[k] = \0;
    else if(s2[k] > 0){
        s2[k+1] = \0;
    }
    
}

int main(){
    char s[9],s1[9],s2[17];
    int i,j;
    scanf("%s%s",s,s1);
    Multiply(s,s1,s2);
    //反向输出
    for(i = strlen(s2)-1 ; i >= 0 ; i -- )
        if(s2[i] != 0) 
            break;
    if(i == -1) putchar(0); //0要单独考虑 
    for(j = i ; j >= 0 ; j -- )
        putchar(s2[j]);
    puts("");
    return 0;
}

 

算法提高P1001