免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 3550 | 回复: 5

[算法] 折半法求x的n次方 [复制链接]

论坛徽章:
0
发表于 2013-10-24 22:10 |显示全部楼层
比如mypow(x, ,第一次循环算出x·x=x2,第二次循环算出x2·x2=x4,第三次循环算出4·x4=x8。这样只需要三次循环,时间复杂度是Θ(lgn)。思考一下如果n不是2的整数次幂应该怎么处理。请分别用递归和循环实现这个算法。
  1. #include<iostream>
  2. using namespace std;

  3. //递归法
  4. double myPow(double x,int n){
  5.     int y=0;
  6.     if(n==1)return x;
  7.     y=n/2;
  8.     if((2*y)==n)
  9.         return myPow(x,n/2)*myPow(x,n/2);
  10.     else
  11.         return x*myPow(x,(n-1)/2)*myPow(x,(n-1)/2);
  12. }

  13. //循环法
  14. double myPow2(double x,int n){
  15.     if(n==1)return x;

  16.     int y=1,b=2,a=0;
  17.     while(n>b){
  18.         b*=2;
  19.         y++;
  20.     }
  21.     if(n!=b){
  22.         y--;
  23.         a=n-b/2;
  24.     }   

  25.     double product=x*x;
  26.     while(--y){
  27.         product*=product;
  28.     }
  29.     while(a--){
  30.         product*=x;
  31.     }
  32.     return product;
  33. }
  34. int main(){
  35.     cout<<myPow2(2,8)<<endl;
  36. }
复制代码

论坛徽章:
0
发表于 2013-10-25 00:15 |显示全部楼层
递归法
  1. double myPow(double x, int n)
  2. {
  3.         if (n <= 0) return 1.0;
  4.         if (n == 1) return x;
  5.         double halfX;
  6.         halfX = myPow(x, n/2);
  7.         return halfX * halfX * (n%2 ? x : 1.0);
  8. }
复制代码

论坛徽章:
0
发表于 2013-10-25 00:56 |显示全部楼层
非递归方法
  1. double myPow2(double x, int n)
  2. {
  3.         if (n <= 0) return 1.0;
  4.         if (n == 1) return x;
  5.         int flag = 0; //用来记录什么时候要多乘以一个x
  6.         double half = 0.0; //用来记录结果
  7.         int tmpN = n;
  8.         while (tmpN > 1)
  9.         {
  10.                 flag = 2 * flag + tmpN % 2;
  11.                 tmpN /= 2;
  12.         }
  13.         half = x;
  14.         while (tmpN < n)
  15.         {
  16.                 half *= half;
  17.                 half *= (flag % 2) ? x : 1.0; //当此时flag不是2的倍数时,表示要多乘一个x
  18.                 tmpN *= 2;
  19.                 tmpN += flag % 2;
  20.                 flag /= 2;
  21.         }
  22.         return half;
  23. }
复制代码

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2013-10-25 08:47 |显示全部楼层
依次查看 n 的二进制形式上的各位
举个例子,假设 n 为 5(二进制为101)
那么 x^5 == (1*x^4) * (0*x^2) * (1*x^1)
  1. #include <iostream>
  2. using namespace std;

  3. double foo( double x, unsigned n )
  4. {
  5.     double r = 1.0;
  6.     for( double m=x; n; m*=m, n>>=1u )
  7.     {
  8.         if( n & 1u )
  9.             r *= m;
  10.     }
  11.     return r;
  12. }

  13. int main()
  14. {
  15.     cout << foo(2.1,13) << endl;

  16.     return 0;
  17. }
复制代码

论坛徽章:
0
发表于 2013-10-26 18:24 |显示全部楼层
本帖最后由 blackfur 于 2013-10-26 18:25 编辑

大哥,想问下怎样写签名?我也想找工作^_^回复 4# bruceteen


   

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2013-10-28 08:39 |显示全部楼层
blackfur 发表于 2013-10-26 18:24
大哥,想问下怎样写签名?我也想找工作^_^回复 4# bruceteen

页面最上端有个“设置”,然后是 个人资料\个人信息\个人签名
不过,我贴了这么久,屁用没有^_^
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP