«August 2018»
1234
567891011
12131415161718
19202122232425
262728293031


公告

本站技术贴除标明为“原创”的之外,其余均为网上转载,文中我会尽量保留原作者姓名,若有侵权请与我联系,我将第一时间做出修改。谢谢!

             ——既瑜


天气预报(南京)


我的分类(专题)

首页(183)
【趣味文摘】(22)
【五子连珠】(13)
【技术文档】(136)
【电脑技术】(6)
【疑难问题】(1)
【我的心情】(5)


最新日志
花语(中英文对照版)
各种花的花语
NTFS格式的7个精彩问答(pconli
童言无忌,有趣得一蹋
给MM修电脑的三个步骤[转载]
J2EE 面试题综合
JAVA编程规则
[转] P2P之UDP穿透NAT的原理与
[转]词法分析器
文件加密技术
一个让人发狂的PI求解C程序
[转]直线生成算法之DDA
[转]利用内核对象----互斥量实现应用
[转]如何正确的计算文件收发进度
双机调试VC程序
[转]分治法优化大整数乘法 C++实现
浮点数值的内存结构
[转]双链表实现大整数的加法与乘法[VC
拜占廷将军问题[转]
某人的挂QQ的程序源代码,虽然没用了,拿

最新回复
回复:vc中的CString的操作
回复:[转]分治法优化大整数乘法 C++
回复:[转]分治法优化大整数乘法 C++
回复:花语(中英文对照版)
回复:基本排序算法比较与选择[转载]
回复:c++中强制类型转换操作符小结
回复:c++中强制类型转换操作符小结
何必那么执着于是大头猫还是愤怒的小鸟,淡
回复:浮点数值的内存结构
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:32位位图到24位位图的转换
dren, ages 16 and 20
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:花语(中英文对照版)
回复:各种花的花语

留言板
签写新留言

不是0-1背包喔
桂花的花语``
谢谢
提议
提议

统计
blog名称:★既瑜★
日志总数:183
评论数量:636
留言数量:-25
访问次数:1313255
建立时间:2005年3月12日

链接


http://www.nju.edu.cn
http://bbs.nju.edu.cn 
http://www.t7-online.com
http://www.csdn.net
http://www.91f.net
http://www.crsky.com
我的MSN BLOG 

联系我

  OICQ:215768265
  njucs2001@hotmail.com
  erichoo1982@gmail.com

 

W3CHINA Blog首页    管理页面    写新日志    退出


[【技术文档】][转]分治法优化大整数乘法 C++实现
既瑜(224499) 发表于 2005-11-25 21:17:29

上大学算法分析实验课的内容.关于利用分治法大整数乘法.还没有解决大整数的存储方式,应该是要利用一维数组来解决.所以目前只是5位数的运算没有问题.程序不是很健全,但是算法的核心部分应该是已经都在这里了. VC++6.0下测试通过. #include <iostream.h>#include <math.h> long mult(long x,long y,int n);int num(long x); void main() //主函数{ long x,y; cout<<"input x and y:"<<endl; cin>>x>>y; cout<<mult(x,y,num(x))<<endl;} long mult(long x,long y,int n){ long a,b,c,d,s; if (n=1)  return x*y; else {  a=long(x/pow(10,(n/2))); //取x的左半部分  b=long(x%long(pow(10,(n/2)))); //取x的右半部分  c=long(y/pow(10,(n/2))); //取y的左半部分  d=long(y%long(pow(10,(n/2)))); //取y的右半部分  s=mult(a,c,n)*pow(2,n)+(mult((a-b),(d-c),n)+mult(a,c,n)+mult(b,d,n))*pow(2,n/2)+mult(b,d,n); //书上的公式  return (s); }} int num(long x) //判断输入的数字的位数{ int i=0; if(x-9<=0)  return 1; else {  while (x!=0)  {   i++;   x=x/10;  }  return i; }}   Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=505113

阅读全文(25339) | 回复(8) | 编辑 | 精华

回复:[转]分治法优化大整数乘法 C++实现
liu(游客)发表评论于2012-9-26 11:29:55

以下引用孟宪龙(游客)在2012-5-8 10:29:18的评论:  s=mult(a,c,n)*pow(2,n)+(mult((a-b),(d-c),n)+mult(a,c,n)+mult(b,d,n))*pow(2,n/2)+mult(b,d,n); 没有对n进行任何操作,递归永远跳不出来!是   求s的正确写法   急···

个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:[转]分治法优化大整数乘法 C++实现
孟宪龙(游客)发表评论于2012-5-8 10:29:18

 s=mult(a,c,n)*pow(2,n)+(mult((a-b),(d-c),n)+mult(a,c,n)+mult(b,d,n))*pow(2,n/2)+mult(b,d,n); 没有对n进行任何操作,递归永远跳不出来!
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:[转]分治法优化大整数乘法 C++实现
xiaogang(游客)发表评论于2007-10-22 21:11:04

#include <iostream.h>#include <math.h> long mult(long x,long y,int n);int num(long x); void main() //主函数{ long x,y; cout<<"input x and y:"<<endl; cin>>x>>y; cout<<mult(x,y,num(x))<<endl;} long  mult(long int x, long int y, int n)  //{X和Y为2个小于2n的整数,返回结果为X和Y的乘积XY}{ long int s; if( ( (x>=0) && (y>=0) ) || ( (x<0) && (y<0) ) )        s = 1; else  s = -1;     x=abs(x);      y=abs(y);            //{X和Y分别取绝对值}   if(n==1)  {  if((x==1)&&(y==1))    return s;                       else       return x*y*s;    }        else  {                         long int A=(long)(x/pow(10,(n/2)));           //X的左边n/2位;                         long int B=(long)(x%(long)(pow(10,(n/2))));     //X的右边n/2位;                           long int C=(long)(y/pow(10,(n/2)));           //Y的左边n/2位;                         long int D=(long)(y%(long)(pow(10,(n/2))));     //Y的右边n/2位;                            long int m1=mult(A,C,n/2);                         long int m2=mult(A-B,D-C,n/2);                         long int m3=mult(B,D,n/2);                         s=s*(m1*pow(10,(n/2)*2)+(m1+m2+m3)*pow(10,n/2)+m3);                                      }  return s; } int num(long x) //判断输入的数字的位数{    int i=0;    if(x-9<=0)       return 1;    else {       while (x!=0)    {          i++;          x=x/10;    }        return i; }}
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:[转]分治法优化大整数乘法 C++实现
apo(游客)发表评论于2007-9-28 21:30:14

if (n=1)  return x*y;永远为真,这个程序和直接求乘法一样的了,后面的全是废话
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:[转]分治法优化大整数乘法 C++实现
jun(游客)发表评论于2007-6-2 12:27:19

但是这个只能求一般的数啊,连10000000*100000之类的东西都求不了
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:[转]分治法优化大整数乘法 C++实现
zxl(游客)发表评论于2006-11-11 20:50:05

// *********************Algorithm: (a+ib)*(c+id)=(ac-bd)+i(bc+ad)**************************Complex Complex::operator*( const Complex &operand2 ) const{ return Complex( real * operand2.real - imaginary * operand2.imaginary,     imaginary * operand2.real + real * operand2.imaginary );}
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:[转]分治法优化大整数乘法 C++实现
flyfish(游客)发表评论于2006-3-23 15:17:39

如果要求两个复数乘法的话。。。怎么写?   我的QQ414147419
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

回复:[转]分治法优化大整数乘法 C++实现
flyfish(游客)发表评论于2006-3-23 15:16:48

如果要求两个复数乘法的话。。。怎么写?
个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除

» 1 »

发表评论:
昵称:
密码:
主页:
标题:
验证码:  (不区分大小写,请仔细填写,输错需重写评论内容!)

站点首页 | 联系我们 | 博客注册 | 博客登陆

Sponsored By W3CHINA
W3CHINA Blog 0.8 Processed in 0.078 second(s), page refreshed 144091584 times.
《全国人大常委会关于维护互联网安全的决定》  《计算机信息网络国际联网安全保护管理办法》
苏ICP备05006046号