星海's Blog

老头初学编程
折半算法
C程序设计语言(第二版)课后习题答案 1-3 章

求2的N次方(要求,最简算法复杂度为lgn)

星海 posted @ 2010年12月06日 02:38 in C代码 , 7120 阅读

 

/*
 * =========================================================================
 *
 *       Filename:  mypow.c
 *
 *    Description:  编写一个函数double mypow(double x, int n);
 *    求x的n次方,参数n是正整数。算法复杂度考虑lgn。  !!递归版
 *
 *        Created:  2010年12月05日 17时20分36秒
 *       Compiler:  gcc
 * ==========================================================================
 */
#include <stdio.h>

double mypow(double x, int n)
{
	if (n == 0)
		return 1;
	if (n == 1)
		return x;
	if (n % 2 != 0)
		return x * mypow(x, n - 1);
	else
		return mypow(x*x, n / 2);
}

int main(void)
{
	printf("%f\n", mypow(2, 11));
	return 0;
}
#include	<math.h>
#include	<stdio.h>
#include    <stdio.h>
#include    <math.h>

double mypow(double x, int n)
{
	double result = 1.0;
	if (n == 0)
		return 1;
	while (n) {
		if (n & 1)
			result *= x;
		x *= x;
		n >>= 1;
	}
	return result;
}

int main(void)
{
	for (int i = 0; i < 16; i++)
		printf("%-2d: mypow: %-10.0f \t pow:%-10.0f\n", i,
		       mypow(2, i), pow(2, i));
	return 0;
}

 

Avatar_small
jackpxq 说:
2010年12月07日 07:12

不知道逻辑左移的时间复杂度是多少

Avatar_small
fairywell 说:
2010年12月07日 18:42

左移时间复杂度显然是O(1),其实要关心的是左移的时间周期

Avatar_small
Boski 说:
2010年12月08日 13:48

double也能左移吗?

这个归并的方法可以用在A^(1e9) % B的问题里,A和B都是int

Avatar_small
星海 说:
2010年12月13日 07:39

晕,你们说的我还看不懂哦,哈哈

Avatar_small
civaget 说:
2023年12月12日 03:33

An effective inner linking strategy can amplify the impact of your 구글 seo efforts, both for users and search engines.

Avatar_small
civaget 说:
2023年12月18日 22:41

I recently tried a local 출장샵, and it was fantastic! The therapist was skilled, and the experience was truly rejuvenating.

Avatar_small
civaget 说:
2023年12月21日 22:47

오피매거진's therapy insights are invaluable for urbanites. It's a must-read for those seeking city relaxation.

Avatar_small
civaget 说:
2023年12月24日 21:35

Say yes to sports without strings attached - say yes to 무료스포츠중계.

Avatar_small
civaget 说:
2023年12月25日 22:25

I recommend 울산휴게텔 to anyone in need of relaxation.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter