Generic placeholder image
闲敲代码、落灯花
What's past is prologue

联系邮箱:email@hezehua.net


联系QQ:1907330840

座右铭

保持热情,持续学习,每日精进

大数乘法(一)

大数乘法(一)

本文与作者在csdn上的博文【大数乘法(一)】保持同步


       首先,通过一个例子来展示我们所运用的运算规律:

12*45=540;

12=1*10^1+2*10^0;------------------------把12每一位分解开

45=4*10^1+5*10^0;------------------------把45每一位分解开

12*45=(1*10^1+2*10^0)*(4*10^1+5*10^0)--------多项式相乘

             =1*4*10^(1+1)+1*5*10^(1+0)--------------可知n位数乘m位数需进行n*m次乘法

                                    +2*4*10^(0+1)+2*5*10^(0+0)-----和(n-1)*(m-1)次加法

             =4*10^2          +13*10^1        +10*10^0-------每一项其指数都是原来相乘的项的指数和 

             =540----------------而且积的位数为n+m(最高位有进位)或n+m-1(最高位无进位);

观察上面算式得出算法:

输入两个大数,并且将它们逆序保存在数组a与b中:

  大数a[n]={a[0],a[1],...,a[n]},大数b[m]={b[0],b[1],b[2],...,b[m]};

  声明保存结果的数组c[n+m];并且将元素初始化全为0;

其中,每一位的指数即是其下标,而分解相乘后的每一项值与指数分别为a[i]*b[j]和i+j;

a[i]*b[j]保存在c中以i+j为下标的的位置,仍然以上例来做演示,到这一步时c中元素为

10 13 4 0

,


只需将其按照十进制进位规则进位即可,

0 4 5 0

此时,将c去掉第一个大于0的数字前的0并倒序输出即为最终结果。

下面贴上c/c++代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include <cstdlib>
using namespace std;

void assignment(int* s,int n){
    for(int i=0;i<n;i++){
        s[i]=0;
    }
} 
void Multiplication(char *arr1,char* arr2,int* Result){
    int n,m;n=strlen(arr1);m=strlen(arr2);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            Result[i+j]=Result[i+j]+(arr1[i]-'0')*(arr2[j]-'0');
        }
    }
}
void reorganize(int *Result,int n){
    int t;
    for(int i=0;i<n;i++){
        if(Result[i]>9){
            t=Result[i]%10;
            Result[i+1]=Result[i+1]+Result[i]/10;
            Result[i]=t; 
        }
    }
}
int main(){
    string s1,s2;
    int n,m;char h;
    cin>>s1>>s2;
    n=s1.length();m=s2.length();
    char *arr1=new char[n];char *arr2=new char[m];
    int  *Result=new int[n+m]; 
    assignment(Result,n+m);
    int i=0,j=0;
    stringstream ss1(s1);while(ss1>>h)arr1[i++]=h;arr1[i]='\0';
    stringstream ss2(s2);while(ss2>>h)arr2[j++]=h;arr2[j]='\0';
    arr1=strrev(arr1);arr2=strrev(arr2);
    Multiplication(arr1,arr2,Result);
    reorganize(Result,n+m);
    int k,z=0;k=n+m;
    while(k--){
        if(Result[0]!=0||Result[k+1]==0&&Result[k]!=0){
            z=1;
        }
        if(z==1)printf("%d",Result[k]);
    }   
} 



猜你喜欢
动态规划入门之国王的金矿
阅读 507

最近学习算法,对动态规划不太了解,使用的时候照搬转移方程式,知其然不知其所以然,今天看到一篇动态规划的教程,解释得非常通俗,原文在这里[动态规划入门教程] (http://blog.csdn.net/woshioosm/article/details/7438834),下面我用自己的记忆和理解...

用大数乘法计算阶乘
阅读 425

在比较小的范围内阶乘可以递归实现,而求更大的数的阶乘一般用到long long长整形数,不过,即使这样,在耗时和再大些的阶乘上力有不逮,所以,在输入比较大的情况下,用大数乘法计算阶乘是最好的选择。 计算过程分2步: 1、输入字符串s,将它的值保存到整型n中; 2、从1~i~n-1循环将i转化...

生成子集——二进制法
阅读 436

用二进制位的0和1表示集合中是否存在该元素要生成0~n的子集,先生成0~n的二进制序列,这些序列的0、1位正好可以对应一个子集中全集在该位置上的元素是否存在,将其作为子集中存在的元素的标记,输出对应元素。#include #include

乘法运算过程模拟法首先获取输入的乘数(a)与被乘数(b)字符串,按一般乘法运算过程,先是a的最后一位数字与b的最后一位数字相乘,接着a中用于相乘的数下标递减,直到a中所有数字与b最后一位都相乘过,保存结果后再递减b中的用于相乘的数字的下标,循环下去,直到b中每一位数都与a所有数相乘完。 在这个过程...

大数加减
阅读 347

太残忍,半个月不做题,就对题目毫无感觉了,明明思路正确清晰,但敲的代码满满的bug,连输入字符串前要开辟空间都能无视。。。还在输入后就清空了却在后面一个劲的对它操作。。。略怀悲伤地把代码改好了。#include #include #incl...

算法--生成1~n的排列
阅读 489

在暴力求解法中,我们常常要用上枚举一些简单内容以便方便获得解,若要输出整数n的前n个整数的全排列,则按字典序输出为: (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)。 从中我们似乎发现了一些规律:先输出以1开头的排列,再输出以2开头的排列,然后是3;...

算法--大数开方
阅读 426

之前已找到比较好的大数乘法算法,现在我们来解决大数开方问题,如有大数n,求其开方x,则x与n必满足x*x=n;也就是说我们能遍历x找到n的开方,但是问题在于我们是不可能对大数遍历的。如果我们可以确定它的大致范围,仅仅测试几个不容易直接判断的数据就找到目标数据就好了。      1-一个n位数的开...

算法--库函数实现全排列
阅读 358

c++的STL中提供了一个库函数next_permutation,代码如下: #include #include #include #include #include #include using namespace std; int main(){ int n,p[10]; ...