首页 > 其他 > 详细

两个大整数相乘

时间:2014-04-17 12:17:58      阅读:451      评论:0      收藏:0      [点我收藏+]

自己太笨了,两个大整数相乘也纠结这么久,看了别人的思路才明白过来。

有两个大整数:

an an-1 ... a1 a0和

bm bm-1 ... b1 b0相乘。

则对应结果的第k位就应该是a[i] * a[j] (i + j = k,  0 <= i,j <= k)

不考虑进位的情况下。

所以最后只要从低位往高位进位就解决了。

bubuko.com,布布扣
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#define N 550
using namespace std;
int ans[N];
string s1, s2;

int main()
{
    int i, j, n, ls1, ls2, len;
    while (cin>>s1>>s2)
    {
        ls1 = s1.length() - 1;
        ls2 = s2.length() - 1;
        len = ls1 + ls2;
        memset(ans, 0, sizeof(ans));
        for (i = ls1; i >= 0; i--)
            for (j = ls2; j >= 0; j--)
            {
                ans[len - (i + j)] += (s1[i] - 0) * (s2[j] - 0);//字符串最后一位对应的是个位数
            }
        len++;//结果的位数不超过ls1+ls2-1,从0开始数
         for (i = 0; i < len; i++)
         {
             ans[i + 1] += ans[i] / 10;
             ans[i] = ans[i] % 10;
         }
         while (!ans[len] && len > 0)//结果最少有ls1+ls2-2位数
            len--;
         for (; len >= 0; len--)
            cout<<ans[len];
         cout<<endl;
    }
    return 0;
}
bubuko.com,布布扣

 

两个大整数相乘,布布扣,bubuko.com

两个大整数相乘

原文:http://www.cnblogs.com/jecyhw/p/3669823.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!