首页 > ACM题库 > 九度OJ > 剑指offer(06)-数值的整数次方[快速幂]
2013
12-10

剑指offer(06)-数值的整数次方[快速幂]

题目来自剑指offer系列 九度 1514 :http://ac.jobdu.com/problem.php?pid=1514

题目描述:
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
输入:
输入可能包含多个测试样例。
对于每个输入文件,第一行输入一个整数T,表示测试案例的数目,接下来的T行每行输入一个浮点数base和一个整数exponent,两个数中间用一个空格隔开。
输出:
对应每个测试案例,
输出一个浮点数代表答案,保留两位小数即可。
样例输入:
5
1.0 10
0.0 -5
1.0 0
1.2 5
2.0 -1
样例输出:
1.00e+00f
INF
1.00e+00f
2.49e+00f
5.00e-01f
提示:
 请特别注意不同的编译器对于科学计数法格式输出中指数位数的差别。建议使用九度Online Judge所使用的编译环境。
此处指定 指数为整数,是在考察快速幂。
//============================================================================
// Name        : 数值的整数次方.cpp
// Author      : coder
// Version     :
// Copyright   : www.acmerblog.com
// Description : 数值的整数次方, 使用快速幂, Ansi-style
//============================================================================
#include <stdio.h>
double x, ans, tmp;
int e, n, i;
int main() {
	while(scanf("%d", &n) != EOF){
		for( i=0; i<n; i++){
			scanf("%lf%d",&x, &e);
			//计算 x^e
			if(x != 0.0){
				if(e < 0){
					e = -e;
					x = 1/x;
				}
				ans = 1.0;
				//快速幂
				while(e){
					if(e & 1)
						ans *= x;
					x *= x;
					e >>=1;
				}
				 printf("%1.2ef\n", ans);
			}else{
				 if(e > 0)
					 printf("0.00e+00f\n");
				else
					printf("INF\n");
			}
		}
	}
	return 0;
}

 


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测