主题：[讨论]第三次编程比赛题目
eastcowboy
[专家分：25370] 发布于 2005-10-28 19:30:00
声明：本来我自己准备了题目，但euc又给了我一个题目。在比较之后我认为他的题目更适合目前的比赛。（原来题目不怎么严密，所以我适当修改了一下。）
请大家给euc鼓掌，呵呵
题目描述如下：
请编写一个函数（C/C++都可以），其原型为：
double power(double a,int n);
实现在double范围内计算a的n次方，并返回计算结果，函数中可以不考虑溢出问题。
另行编写main函数以及其他任何必要的函数，使程序结构完整，最好能在程序中一定程度上验证自己的函数。
请尽量注意程序的严谨性、效率、代码风格等因素。这些将作为产生冠军的参考条件。
说明：
本题目不是考察大家是否知道pow这个函数~~
请大家不要使用pow函数。（当然了，用于检验的时候还是可以的。）
参考数据：（利用windows自带计算器程序得出）
1.00001 的 10000 次方 = 1.1051703654940106069188996091683
123 的 50 次方 = 3.1279195318495243277303764742785e+104
0 的 0 次方 = 1
0.99999 的 10000 次方 = 0.90483696561434751400304156716182
再次重申比赛的一些原则：
1、请仔细思考，编程然后帖上自己的代码。不要帖别人现成的东西，那样没什么意思。
2、请认真对待题目，帖上自己认为正确的代码，不要帖有明显逻辑错误甚至语法错误的代码。（至少应该要通过编译吧）
3、请注明自己使用的语言、编译器/编译环境。比较有特色的程序请写一个简短的介绍。（当然比较一般的程序也可以写介绍）
4、建议：程序要有注释。
5、请文明参赛，不要在比赛时做出任何恶意行为。
6、本人将对本次比赛规则保留解释权^-^
比赛从28日（星期五）晚上7点30分持续到29日（星期六）晚上11点30分，共28小时，希望大家都能找到自己合适的时间来答题。
好了，我的废话完毕。
大家加油吧！
回复列表 （共46个回复）
31 楼
Jiff [专家分：640] 发布于 2005-10-29 10:52:00
double EvenPower(double a,int n) //若n为偶数，执行次函数
{
return Power(a,n/2)*Power(a,n/2); //折半递归进行
}
32 楼
Catamount3000 [专家分：7640] 发布于 2005-10-29 10:52:00
我再发一个
#include <stdio.h>
double power(double o_o,int h_h) {
int T_T;double x_x;
for (T_T=1,x_x=o_o;T_T++<((h_h<0)?-h_h:h_h);x_x*=o_o);
return (h_h<0)?1.0/x_x:x_x;
}
void main() {
double n_n;int w_w;
scanf("%lf%d",&n_n,&w_w);
printf("%lf",power(n_n,w_w));
getchar();getchar();
}
33 楼
Jiff [专家分：640] 发布于 2005-10-29 10:54:00
上面的函数改为
double EvenPower(double a, int n)
{
double temp=Power(a,n/2);
return temp*temp;
}
后效率提升了近一半多.呵呵
当初我也太马虎了,花了双倍的价值!
34 楼
euc [专家分：4310] 发布于 2005-10-29 11:22:00
我不参加比赛，但还是想发一下, 这个是O(log(N^2))的吧
#define BITWIDTH 15
double binpow (double a, int n)
{
while (--n >= 0) a *= a;
return a;
}
double log_power (double a, int n)
{
int i, mask = 1;
double s = 1.0;
if (n == 0) return 1.0;
if (n < 0) {a = 1.0 / a; n = -n;}
for (i = 0; i < BITWIDTH; ++i, mask <<= 1)
if (n & mask) s *= binpow (a, i);
return s;
}
35 楼
euc [专家分：4310] 发布于 2005-10-29 14:50:00
上面算法不是logN的，[url=http://www.oioj.net/blog/user2/21189/archives/2005/170027.shtml]logN的[/url]就交给其他同学发表吧。
36 楼
杀死进程 [专家分：510] 发布于 2005-10-29 15:22:00
#include "stdio.h"
double power(double a, int n)//n次方函数
{
int i;
double res=1;
if (a==0)
return 1;
else
{
for(i=0;i<n;i++)
res=res*a;//每次循环乘一次a
return res;//返回函数的结果
}
}
void main()
{
double a;
int n;
printf("请您输入a的值：");//输入的值为要求n次方的数
scanf("%lf",&a);
printf("\n请您输入n的值:");//输入的值为多少次方
scanf("%d",&n);
printf("经过计算%lf的%d方是：%lf\n",a,n,power(a,n));
}
//凑个热闹
37 楼
华山论剑 [专家分：5310] 发布于 2005-10-29 17:11:00
euc的代码注入了全新算法思路，不错。
有些朋友提到根据a的奇偶分别用不同的算法，当然，a如果是纯粹偶数可以用移位运算代替乘法提高效率。想法虽不错，可是实际上可能行不通。因为a是double值，范围很广，包含的小数部分就没有奇偶之说了。如果再加上整数/小数判断、奇偶判断，本来就增加了不小的运行开销，况且使代码结构复杂化，是不是有些得不偿失呢？
部分贴中我们不难看到很多直接或者变相抄2楼的地方。如果没有新东西，只是抄别人的，或者别人已经发了的，就别重复了，发了还不如不发的好！
我这个人喜欢说实话，别人不敢说或者不好说的就由我来说吧！砖头、谩骂尽管向我身上招呼。
38 楼
lovefreex [专家分：1190] 发布于 2005-10-29 19:12:00
#include<stdio.h>
double Power(double a, int n);
int main()
{
double a, result;
int n;
printf("please input a :");
scanf("%lf",&a);
printf("please input n:");
scanf("%d",&n);
result = Power(a, n);
printf("%lf",result);
return 0;
}
double Power(double a, int n)
{
double r = 1; //存放奇数次幂的积
double b = a; //存放偶数次幂
int i; //循环次数
if(n == 0)
return 1.0;
else
if(n < 0)
n = -n;
i = n;
while(i > 1)
{
if(i % 2 ==0) /*偶次方*/
{
b = b * b;
i = i / 2;
}
else
{
r = r * b;
i--;
}
}
if(n < 0)
return 1 / (r * b);
else
return r * b;
}
39 楼
iAkiak [专家分：8460] 发布于 2005-10-29 19:40:00
好像已经有人贴过log n的了吧？我晚了...
#include <stdio.h>
#include <math.h>
double Power(double a, int n)
{
// O(log n)
double t, s = 1;
if (n < 0)
t = 1. / a, n = -n;
else
t = a;
for (; n; n >>= 1)
{
if (n & 1)
s *= t;
t *= t;
}
return s;
}
int main()
{
double a;
int n;
while(scanf("%lf%d", &a, &n)==2)
{
printf("%lf^%d=\n%lf\n%lf\n", a, n, Power(a, n), pow(a, n));
}
return 0;
}
/// btw. 有的人愿意看这样的代码...那么也顺便满足一下好了
double Power(double a, int n)
{
// O(log n)
double s = 1;
for (n < 0 && (a = 1. / a, n = -n); n; n >>= 1, a *= a)
n & 1 && (s *= a);
return s;
}
40 楼
iAkiak [专家分：8460] 发布于 2005-10-29 20:28:00
另一个方法：
前面log n的方法其实具体的运算量在log n到2 * log n之间。比如对18，用log n的方法有6次乘法：
18 = 10010 //包括4次进位的a *= a和2次s *= a
而这样分：
18=3*3*2
a2=a*a
a6=a2*a2*a2
a18=a6*a6*a6
或者：
a3 = a*a*a
a6 = a3*a3
a18=a6*a6*a6
就只要5次乘法。
具体方法是对n分解质因数。把问题降为多个求幂的小问题。（这个角度来看有点像jiff分奇偶那个程序）
对每个小问题，分别再使用一个logn的方法。
看上去这个问题对这个题目并没有帮助，反而多了一个因数分解的过程。
不过对高精度乘法来说，分解低精度整数n的过程是划算的。减少的高精度乘法次数还是比较可观的：）
[color=FF0000]等等，第二个方法复杂度更高...各位，我错了:([/color]
我来回复
您所在位置：