博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
pow(x,y)函数的实现算法(递归函数)
阅读量:6646 次
发布时间:2019-06-25

本文共 439 字,大约阅读时间需要 1 分钟。

函数pow(x,y)实现运算x^y,即x的y次方,这里x和y都为整数。

算法的基本思想是,减少乘法次数,重复利用结算结果,例如:
x^4,如果逐个相乘的话,需要四次乘法。如果我们这样分解(x^2)*(x^2)就只需要2两次乘法,因为x^2的结果我们可以重复利用。所以我们最好做对称的分解指数y,然后求x^(y/2)的平方。

具体算法如下:
1 如果y为偶数,直接计算mypow(x, y/2)*mypow(x, y/2);
2 如果y为奇数,则y-1为偶数,回到了第一种情况。

int mypow(int x,int y){    if(y==0) return 1;    if(y==1) return x;    int ret=0;    int tmp=mypow(x,y/2);    if(y&1 != 0){        ret=x*tmp*tmp;    }    else{        ret=tmp*tmp;    }    return ret;}

 

转载地址:http://pmuto.baihongyu.com/

你可能感兴趣的文章
C++--标准库 字符串类
查看>>
Java的新项目学成在线笔记-day1(七)
查看>>
160个CRACK_ME系列 第一弹
查看>>
什么是记录型数字压力表?被应用在哪些领域?
查看>>
零基础学习Python的4个方法
查看>>
Clouds
查看>>
好程序员带你认识HTML5中的WebSocket
查看>>
PDA是什么功能有哪些
查看>>
一文了解 SaCa DataViz 企业版和标准版的区别
查看>>
CentOS 5的KVM安装使用说明
查看>>
php warning: php startup: in unknown on line 0
查看>>
【CentOS 7.1】配置防火墙 iptables
查看>>
二十七、单张图片上传预览
查看>>
一例千万级pv高性能高并发网站架构
查看>>
Android平台通用安全问题分析及策略(一)
查看>>
Oracle面向对象的应用实例
查看>>
总结-计划
查看>>
POJ 2506 Tiling dp+大数 水题
查看>>
EasyCHM - 电子书制作软件
查看>>
电脑组装图文教程电子书
查看>>