计算幂,n^m,其中n为底数,m为幂
当m取值比较大时如果采用m个n相乘的办法,计算显得冗长。
可以采用以下方法重新组织算法:
n^m == n^((m/2) * 2)
n^m == (n^(m/2))^2
假设如果可以求得temp = n^(m/2),则n^m = temp * temp
这里采用了递归的做法,将n^m问题转换成为n^(m/2)的问题,将近减少了一半运算量。
特殊情况是m不是偶数的情况,这种状况下:
temp = n^(m/2)
n^m = temp * temp * n (多乘一次就可以解决这个问题)
时间代价从原来的O(m) 变成了 O(log m),再这种情况下递归可以提高运行效率。
代码如下:
class Power {
public static void main(String[] args) {
for(int i=0; i< 11; i++) {
System.out.print(power(3,i) + " ");
}
System.out.println();
}
private static long power(int n, int m) {
assert m >= 0;
if(m == 0) return 1;
if(m == 1) return n;
long temp = power(n,m/2);
return m%2 == 0? temp * temp: temp * temp * n;
}
}
分享到:
相关推荐
一个简单的递归求幂的c++源代码,简单易懂适合初学者引用研究.
递归求简单交错幂级
c语言非递归快速幂demo
使用JS实现表达式求值与幂运算算法:1)求以a为底的n次幂递归与非递归实现;2)快速乘法递归与非递归实现;3)表达式求值计算
2的幂次方表示 描述 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HjnOLAKd-1583034303750)(C:\Users\HUAWEI\AppData\Roaming\Typora\typora-user-images\image-20200301114236455.png)]...
求正整数n的不同划分个数。 2、设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。 3、Hanoi塔问题 设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个圆盘,这些圆盘自下而上,由大到 小地叠在一起。各圆盘从小...
主要介绍了C语言求幂计算的高效解法,分别演示了求幂运算与整数次方的解法,具有不错的参考借鉴价值,需要的朋友可以参考下
C++实现的快速幂算法-Pow(x,n),本算法实现了迭代和递归两个版本。
算法设计与优化中的递归法德5道经典例题(如最大值,母牛繁殖,x的n次幂等),用c编写,很适合初学者借鉴。
本代码是用java实现的快速傅里叶变换的递归实现,要求使用者要按多项式的幂的升序来输入系数
2.1.15幂次方.wmv 2.1.13组合问题.wmv 2.1.14组合与素数.wmv 2.1.12巡视.wmv 2.1.16Jam的计数法.wmv 2.1.2地盘划分.wmv 2.1.1棋子移动.wmv 2.1.3拆分自然数.wmv 2.1.4魔方阵.wmv 2.1.5放苹果.wmv 2.1.6N皇后问题.wmv...
创建一个函数 power来为任意数字做幂运算n ** i #递归 def power(n,i): if i==1: return n return n*power(n,i-1) print(power(2,4)) 练习2 创建一一个函数,用来检查一个任意的字符串是否是回文字符串 ,如果...
递归快速幂的思路非常自然,代码也很简单(直接把递归方程翻译成代码即可) 这次的讲解就到这里了,希望大家对快速幂能有所了解,快速幂还包涵矩阵快速幂,快速幂的代码是需要背的,如果要熟练的话就只能多背!
a,b较小时 2000 #include using namespace std; const int N = 2010, mod = 1e9 + 7; int c[N][N]; int n; int main() { cin >> n;...a,b较大时 利用乘法逆元求 a,b为10^5 #include #include #inclu
当无限脉冲响应(IIR)系统输入和输出信号被α稳定噪声干扰时,传统的最小...然后采用矩阵求逆引理和幂迭代法递归更新自适应滤波器的系数,使其可跟踪时变系统,并提高算法收敛速度 。仿真结果表明,IIR RTLP算法比 TLMP算
提出的实现使用执行矩阵乘法和递归供电的迭代算法。 程序用 C99 编写并使用 GNU MP 库。 在页面上阅读有关该方法的更多信息。 只要您链接到 GNU MP,许可证就有效。安装为了构建程序,只需运行make 。 该程序依赖于...
Python入门程序 函数应用(判断素数、递归求n的阶乘、x的n次方、最大最小值、插入排序法) 1.判断素数 #编写函数,判断一个数是否是素数。 def isprime(n): if n==1: return False for i in range(2, n): if n ...
这篇文章讲述了CIC基本原理,并将CIC转换为非递归结构形式,对于非2的幂次倍抽取率,比如,24、40、180等非2次幂倍抽取,将抽取倍数分解为2P3K4M5T7R等等形式,每级为2/3/4/5/7/11/...等等倍抽取,这样将CIC设计难度...
C 语言实例include void main() { int x,n; double t; cin>>x>>n; t=1;、练习适合初学者
快速模块化递归求幂 是首要的 素因数分解 橡皮擦筛 米勒-拉宾检验 使用Euclid算法 使用递归 弦 数字 加 减去 乘 划分 功率 号码 到二进制字符串 使用除法和模数 使用右移和模数 使用BigDecimal 使用除法和加倍 是2...