前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >大数相乘算法

大数相乘算法

作者头像
雪影
发布2018-08-02 14:34:29
4880
发布2018-08-02 14:34:29
举报
文章被收录于专栏:流媒体人生

啥也说,直接给代码

代码语言:javascript
复制
//////////////////////////////////////////////////////////////// 
//作者:涂远东 
//时间:2010 01 23 
//高精度的乘法,乘数的位数没有限制,小数点后面的位数也没有限制 
//输入参数:乘数 str1,str2 
//输出参数:str = str1*str2 
//返回值类型:string& 
//////////////////////////////////////////////////////////////// 
string& large_mult(string str1,string str2,string& str/*输出参数*/)  
{  
    str = "0";  
 int pos1 = str1.find('.');  
 int pos2 = str2.find('.');  
 //小数点在字符串的位置 
 int offset = str1.length() + str2.length()  
        - ((pos1 >0)? (pos1+1):0 )  
        - ((pos2 >0) ? (pos2+1):0 );  
 //去除字符串str1和str2中的小数点 
 if(pos1 != -1)  
        str1.erase(pos1,1);  
 if(pos2 != -1)  
        str2.erase(pos2,1);  
    unsigned char single = 0;   //个位数 
    unsigned char tens = 0; //十位数 
    unsigned char ret = 0;  //乘积 
 //计算规则,假设str1和str2字符串长度分别为len1和len2 
 //乘积str的字符串长度len应该不大于len1+len2 
 //乘数str1[len1-i]和str2[len2-j]相乘只会乘积中str中str[len-i-j]和str[len-i-j-1]的值 
 int i = 0;  
 for(string::iterator iter = str1.end()-1; iter >= str1.begin(); iter--,i++)  
    {  
 int index = 0;  
 int offset = 0;  
 int j=0;  
 for(string::iterator iter2=str2.end()-1; iter2 >= str2.begin(); iter2--,j++)  
        {  
            offset = i+j +1;  
 //字符‘0’的ASCII编码值为48 
            ret = (*iter2 -'0') * (*iter -'0'); //乘积 
            single = ret % 10;      //乘积的个位数 
            tens = ret / 10;        //乘积的十位数 
 //位数不够左边补0 
            index = str.length() - offset;  
 while(index < 1)  
            {  
                str.insert(str.begin(), '0');  
                index = str.length() - offset;  
            }  
            assert(str.length() > offset);  
            index = str.length() - offset;  
            add(str,index,single);      //个位数相加 
            add(str,index-1,tens);      //十位数相加 
        }  
    }  
 if(str[0] == '0')  
    {  
        str.erase(str.begin());  
    }  
 if(offset < str.length())  
    {  
        string::iterator itr = str.end()-offset;  
        str.insert(itr,'.');  
    }  
 return str;  
}  
//////////////////////////////////////////////////////////////// 
//在大数str的index位处加于num 即 str+= num 
//////////////////////////////////////////////////////////////// 
inline bool add(string& str, int index, int num)  
{     
    assert(index >=0);  
 int  p = str[index] + num - '0';      
    str[index] = p%10 + '0';  
 if(p >9)  
        add(str,index-1,1);  
 return true;  
}  

测试代码

代码语言:javascript
复制
#include "stdafx.h" 
#include <iostream> 
#include <string> 
#include <cassert> 
using namespace std;  
string& large_mult(string str1,string str2,string& str/*输出参数*/);  
bool add(string& str, int index, int num);  
int main(int argc, char* argv[])  
{  
    printf("Please input two large number!/n");  
    string str1;  
    string str2;  
    std::cout<<"Please input the first large number:/nstr1=";  
    std::cin>> str1;  
    std::cout<<"Please input the second large number::/nstr2=";  
    std::cin>>str2;  
    string str; //str = str1 * str2 
    large_mult(str1,str2,str);  
    std::cout<<"str=str1*str2/nstr=";  
    std::cout<<str<<std::endl;  
 return 0;  
}  
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2010年01月23日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档