主题:[讨论]第三次编程比赛题目
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个回复)
11 楼
Jiff [专家分:640] 发布于 2005-10-28 21:21:00
晕~~~~
由于版面宽度限制,
注释都被分割了,
应该不影响大家的观看.
呵呵~~~
12 楼
onasp [专家分:5600] 发布于 2005-10-28 21:32:00
谈一点我的想法.
double power(double a, int n);
这个函数的返回值虽然是double的,但是我们没有必要返回的就是结果啊.
我们可以让它为任意一个数,比如成功的时候返回1.0,失败返回0.将它转化为bool了.
这样我们在编写一个print函数,再调用print函数进行结果输出.
我想可以借鉴1000!的计算方法.
这样就可以得到满足题目要求的精度了.尽管楼主说不考虑精度.
我写了一些,写不下去了.
因为double表示的范围太广了.在把double转化为一个数组的时候,很是麻烦.要考虑的情况太多了.我也不知道有没有把double类型直接转化为字符串的函数.
后来想到,将double a的整数部分和小数部分分开.转化后在合并.
再仿照1000!错位相加,加进位.
这样就可以了.
程序没写出来,大家帮我看看,可行么?
13 楼
steddy [专家分:30] 发布于 2005-10-28 22:02:00
VC7.0编的,应该可以.
#include <stdio.h>
#include <math.h>
#include <iostream>
using namespace std;
double power(double a,int n);
int main()
{
double a;
int n;
cout<<"请输入底数a:"<<endl;
cin >> a;
cout<<"请输入次方数n:"<<endl;
cin >> n;
double k = power(a,n);
cout << k<<endl;
while(1)
{}
}
double power(double a,int n)
{
if( n == 0) //何数的0次方都为1
return 1;
double num;
num = a;
for(int i = 1;i < n;i ++)
{
num = num*a;
}
return num;
}
14 楼
Jiff [专家分:640] 发布于 2005-10-28 22:09:00
我的最新版本已放入
我们的兴趣小组的留
言里头了,麻烦楼主
去看一下,这次我可
要拿第一哦.
呵呵~~~~
15 楼
euc [专家分:4310] 发布于 2005-10-28 22:18:00
love几又和jiejie的算法和我想的差不多.我自己也还没做完,因为有可能更优化.
16 楼
林杰杰 [专家分:8970] 发布于 2005-10-28 22:33:00
to euc:
晕死,这题不是你出的吗?
17 楼
eastcowboy [专家分:25370] 发布于 2005-10-28 23:27:00
先写点分析吧,免得到比赛完了才来评,程序太多看着也很累的~~
第2楼 LO几又VE
这位大哥不愧是老手,代码简洁而又考虑周全。(本来我给的测试数据中就故意把负数次方给去掉了……)
double m = a;
这样可以少算一次循环,即:2的5次方只需4次乘法。但这种程度的优化对于计算1000次方来说效果就不怎么明显了。
第3楼 catamount3000
递归是个不错的主义,虽然增加了函数调用的开销但却使代码简洁明了。
缺点:参数n为负的时候会出错。
第5楼 huahuagongzi
这应该算比较平常的解法了,不过函数中的if-else没必要。n为0时b自然就是1.0了。
缺点:参数n为负的时候会出错。
第7楼 LO几又VE
开始考虑效率了……不过可惜的是没有成品。
第9楼 林杰杰
效率很高!不过似乎是因为思路不是太清晰,代码显得有点杂乱,调试得很辛苦吧?
希望能给出优雅一点的表达方式。
第10楼 Jiff
这样的代码量……Jiff老兄可真是认真啊。不过这样的完成并不是十全十美。
首先是效率(这个估计是目前为止效率最低的了,如果是计算1.000001的10000000次方的话),不过稍稍改一点就可以让这个程序快起来。(这要靠Jiff自己去发现了^^)
然后是函数IsNum,其实调用系统函数isdigit就可以,何必自己写呢。
最后是输入方面,如果直接输入Ctrl+Z将导致死循环。
第13楼 steddy
比较一般的解法,参数n为负的时候会出错。
18 楼
林杰杰 [专家分:8970] 发布于 2005-10-28 23:39:00
To eastcowboy:
对于那个程序,我觉得还可以啊。至于更优雅的方式嘛……嘿嘿,我暂时想不到。
程序的思路是这样的:外层while循环就是对应于LO几又VE的分解过程,也就是把15分解成8、4、2、1的过程。而里面的while对每一个分解出来的数求对应的幂值。也就是8 = 2 * 2 * 2,4 = 2 * 2,2 = 2这个过程。由于把一个数分成了许多个2的幂次,所以相乘次数少了许多。因为外层的循环次数确定不了,所以我猜想整个程序的效率可能是log2(m)的平方。
19 楼
euc [专家分:4310] 发布于 2005-10-28 23:52:00
如果谁能想出来比O(logN)更快的算法(N是指数),那绝对是冠军咯,
20 楼
chenxun1983 [专家分:0] 发布于 2005-10-28 23:56:00
#include <stdio.h>
#include <iostream.h>
double power(double a,int n)
{
if (n==0)
return 1.0;
return a*power(a,n-1);
}
int main()
{
double num;
int n;
printf("ÇëÊäÈëÊý¾ÝºÍ´Î·½:\n");
scanf("%lf%d",&num,&n);
if (num==0 && n==0)
{
cout<<"error!"<<endl;
getchar();
getchar();
return 0;
}
printf("½á¹û=%lf\n",power(num,n));
getchar();
getchar();
return 0;
}
我来回复