一个算法问题,result *=a : result *= result 的改进。

Brianlicorice 发布于 2013/02/20 18:38
阅读 253
收藏 1
1 result = 1; 
2 for(int i = 1; i <=n; i++) 
3 result *= a;

如果改进算法为

result = a; 
for(int i = 1; i <=k; i++) 
result = result * result;

请问如何推导出n与k之间需要满足的关系?

注:该方法为计算a^n的结果。

加载中
0
leo108
leo108
第二个算法明显不对啊
0
杨同学
杨同学
只有当n是2的幂的时候才可以这样算吧
B
Brianlicorice
对呢,但是k和n的关系是什么呢?
0
zhuang
zhuang
额,太简单了,见<编程原本>
B
Brianlicorice
手头没书,既然简单,劳烦给讲一下
0
杨同学
杨同学
//x是底数,y是指数
long power(int x, int y) {
    long half;

    if (y == 0) return 1;
    half = power(x, y / 2);
    return half * half * (y%2 == 0 ? 1 : x);
}

0
lwdxinghuo
lwdxinghuo
/* n必须是2的整数次幂, k =  log2 (n)*/
#include <stdio.h>
#include <math.h>
		
int main(int argc, char* argv[])
{
	int i = 0, n = 8, ret = 1, a = 3, k;

	for (i = 1; i <= n; i++)
		ret *= a;
	printf("ret = %d\n", ret);
 
	ret = a;
	k = (int)((float)log(n)/(float)log(2));
	
	for (i = 1; i <= k; i++)
		ret *= ret;
	printf("ret = %d\n", ret);
	
	return 0;	
}
0
B
Brianlicorice

引用来自“lwdxinghuo”的答案

/* n必须是2的整数次幂, k =  log2 (n)*/
#include <stdio.h>
#include <math.h>
		
int main(int argc, char* argv[])
{
	int i = 0, n = 8, ret = 1, a = 3, k;

	for (i = 1; i <= n; i++)
		ret *= a;
	printf("ret = %d\n", ret);
 
	ret = a;
	k = (int)((float)log(n)/(float)log(2));
	
	for (i = 1; i <= k; i++)
		ret *= ret;
	printf("ret = %d\n", ret);
	
	return 0;	
}
谢谢!
0
我土鳖

如果你不怕溢出,可以这么干:(a是底数,n是次数,result是结果)

int a, n, i, result = 1;
for( i = 1; i < 32; i++ ) {
	if( n & 1 ) {
		result *= a;
	}
	a *= a;
	n >>= 1;
}

返回顶部
顶部