一道C语言题目,不知道怎么做
3. Consider the following code segment:
int foo ( int x , int n)
{
int val;
val =1;
if (n>0)
{
if (n%2 == 1) val = val *x;
val = val * foo(x*x , n/2);
}
return val;
}
What function of x and n is compute by this code segment?
(a) x^n
(b) x*n
(c) n^x
(d) None of the above
问题点数：10、回复次数：43Top
1 楼mu_yang（穆扬）回复于 2006-10-23 12:35:37 得分 0
比较变态的题目Top
2 楼Kusk（Kusk）回复于 2006-10-23 12:36:12 得分 0
a.
是用递归的思想，求x的n次方，原理如下：
如果n == 0，则返回1；否则：
如果n是偶数，设n=2k，则x^n = x^(2k)=(x*x)^k
如果n是奇数，设n=2k+1，则x^n= x^(2k) * xTop
3 楼pcboyxhy（-273.15℃）回复于 2006-10-23 12:42:03 得分 0
x^nTop
4 楼xxyyboy（壮志凌云)(★★★★★）回复于 2006-10-23 12:53:43 得分 0
int foo ( int x , int n)
{
int val =1;
if (n>0) //n为整数
{
if (n%2 == 1)//看n是不是2的倍数，是下1步，不是下2步。
{val = val *x;}//是2的倍数 乘，乘完接着下1步。
val = val * foo(x*x , n/2);// 自己调用自己，递归
}
return val;
}
n做为递归终止的条件，n=n/2,什么时候满足 n>0条件 什么时候退出，不考虑n的类型，n/2 趋向于0,但永远！＝0，这里投机取巧，应为int/int 计算机只取整数部分，个人觉得所以这个程序。。。 very bad.
Top
5 楼xxyyboy（壮志凌云)(★★★★★）回复于 2006-10-23 12:55:10 得分 0
程序看懂了，结果我就不说了。Top
6 楼Kusk（Kusk）回复于 2006-10-23 13:15:30 得分 0
楼上的逻辑混乱连取模运算都看错，又把数学中的除法运算和计算机中的整除运算混为一谈。Top
7 楼blue_zyb（）回复于 2006-10-23 13:36:43 得分 0
个人觉得所以这个程序。。。 very bad.
-------------------------------------
这个算法比一般的计算幂次要快。。。Top
8 楼mu_yang（穆扬）回复于 2006-10-23 13:54:09 得分 0
这个算法比一般的计算幂次要快。。。
------------------------------------
根据何在?Top
9 楼Kusk（Kusk）回复于 2006-10-23 13:56:45 得分 0
回复人：mu_yang(穆扬) ( 二级(初级)) 信誉：96 2006-10-23 13:54:00 得分:0
?
这个算法比一般的计算幂次要快。。。
------------------------------------
根据何在?
------------------------------------
因为它的复杂度是对数级的。Top
10 楼mu_yang（穆扬）回复于 2006-10-23 14:02:05 得分 0
因为它的复杂度是对数级的。
-------------------------------
1.但程序的复杂性是指数级的
2.两个形参都是int ,返回值也是int
计算量不大,追求速度我认为得不偿失
3.如果你的道理成立
if (n%3 == 1) val = val *x;
if (n%3 == 2) val = val *x *x;
val = val * foo(x*x*x , n/3);
应该更快
Top
11 楼Kusk（Kusk）回复于 2006-10-23 14:10:10 得分 0
1.但程序的复杂性是指数级的
-----------------------
不知道什么是“程序的复杂性”。
2.两个形参都是int ,返回值也是int
计算量不大,追求速度我认为得不偿失
－－－－－－－－－－－－－－－－－－－－
那是另一个问题。算法的价值在于思想，不能用肤浅的应用来衡量其价值。
3.如果你的道理成立
if (n%3 == 1) val = val *x;
if (n%3 == 2) val = val *x *x;
val = val * foo(x*x*x , n/3);
应该更快
－－－－－－－－－－－－－
你仔细验证一下乘法的计算次数就知道你所臆想的“应该更快”是不正确的。Top
12 楼mu_yang（穆扬）回复于 2006-10-23 14:36:27 得分 0
1.不知道什么是“程序的复杂性”。
---------------------------------
我是指代码的晦涩难懂
2.那是另一个问题。算法的价值在于思想，不能用肤浅的应用来衡量其价值。
---------------------------------
代码的价值:我是把可读性放在速度前面的
再说这代码我也没看出有什么思想性
3.你仔细验证一下乘法的计算次数就知道你所臆想的“应该更快”是不正确的
---------------------------------------------------------------
谢谢你
我会仔细验证一下
Top
13 楼mu_yang（穆扬）回复于 2006-10-23 21:07:21 得分 0
我验证了一下
主帖:
递归调用次数~log2(n)(表示以2为底的对数)
实参为偶时 4次乘除(含求余 除2)
实参为奇时 5次乘除(含求余 除2)
平均 4.5log2(n)次乘除
我的例子:
递归调用次数~log3(n)
实参为3m+1时 7次乘除(含求余 除以3)
实参为3m+2时 8次乘除(含求余 除以3)
实参为3m时 6次乘除(含求余 除以3)
平均 7log3(n)次乘除
4.5log2(n)/7log3(n)~4.5*ln3/7*ln2~1.0189
结论:后者比前者快约1.89%
我所臆想的“应该更快”是不正确的吗?Top
14 楼Kusk（Kusk）回复于 2006-10-23 21:26:47 得分 0
不知道你的7次乘除8次乘除怎么来的。下面是我的推导，二分法是较优的：
设二分法求解时n次幂要做g(n)个乘法，就有
g(n)等于
1）g(n/2) + 1，当n为偶数， (根据f(x,n)=f(x * x, n/2)，右边多算一个乘）
2）或g(n / 2) + 2，当n为奇数。（根据f(x,n)=f(x*x, n / 2) * x)，右边多两个乘）
3）0，当n = 0
三分的时候设n次幂要做h(n)个乘法，同样有
h(n)等于
1）h(n / 3) + 2, when n % 3 == 0
2）h(n / 3) + 3, when n % 3 == 1
3) h(n / 3) + 4, when n % 3 == 2
4)0，当n = 0
不考虑n=0，则g(n)平均每次做1.5个乘法，h(n)每次3个，而g(n)，f(n)分别进行
lg(2, n)及lg(3, n)次迭代，所以乘法数之比为：
2分：3分＝(1.5lg(2, n) / 3lg(3, n)) = 0.5 * (lg3/lg2) ~ 0.79
二分法还是略优于于分法。当然如果考虑除法的话就改一下log的系数，结果
增为0.990. 只不过一般二分法的除二运算可以换为比除法快数百倍的位移运算，
所以一般计算二分法效率不考虑除法而只考虑乘法次数。Top
15 楼myjava_024（）回复于 2006-10-23 21:28:06 得分 0
答案是a
在好多时候递归调用是真迷惑人啊
小心!Top
16 楼mu_yang（穆扬）回复于 2006-10-23 22:14:40 得分 0
不知道你的7次乘除8次乘除怎么来的。
-------------------------------------------
if (n>0)
{
if (n%2 == 1) val = val *x;
val = val * foo(x*x , n/2);
}
对奇数实参:
n%2
val *x
val * foo
x*x
n/2
共5次乘除
对偶数实参:
n%2
val * foo
x*x
n/2
共4次乘除
三分同理
Top
17 楼jietian（）回复于 2006-10-23 22:22:20 得分 0
bt的程序
中国的题都喜欢这样
要么就是指针的指针的指针的指针是什么啊
这些烦死人了！Top
18 楼xiaoke26（带三个表）回复于 2006-10-23 22:48:31 得分 0
这个是原来英文的回答：
The answer is (a)
Non recursive version of the program
int what ( int x , int n)
{
int val;
int product;
product =1;
val =x;
while(n>0)
{
if (n%2 == 1)
product = product*val;
n = n/2;
val = val* val;
}
}
/* Code raise a number (x) to a large power (n) using binary doubling strategy */
Algorithm description
(while n>0)
{
if next most significant binary digit of n( power) is one
then multiply accumulated product by current val ,
reduce n(power) sequence by a factor of two using integer division .
get next val by multiply current value of itself
}Top
19 楼vegetable_king（）回复于 2006-10-23 23:00:57 得分 0
看不懂 啊 我晕
怎么会选a 啊 郁闷
if (n>0)
{
if (n%2 == 1) val = val *x;
val = val * foo(x*x , n/2);
}
这里如果n为偶数的话 n/2不也是偶数吗？？
val=1 则 val=1*1啊 不就都是等于１了吗 ？？
如果是奇数还说得过去Top
20 楼wormOK（笨笨）回复于 2006-10-23 23:09:19 得分 0
出乎意料的方法，学着用了，呵呵。。Top
21 楼jklangel（）回复于 2006-10-23 23:20:24 得分 0
我觉得如何是考试的话，直接挑两个简单的数代进去算，
再与选择核对，看哪个一样，就选哪个
当然，如果是抱以学习的态度，是要弄懂原因的Top
22 楼Kusk（Kusk）回复于 2006-10-23 23:41:28 得分 0
mu_yang(穆扬) ( 二级(初级)) 信誉：96 2006-10-23 22:14:00 得分:0
----------------------------------------------------------
了解。Top
23 楼icansaymyabc（学习与进步）回复于 2006-10-24 09:54:29 得分 0
这是一个典型的用空间换时间的求 x^n 的算法改进。
相比于传统的 x^n=f(x,n){int val=1; for(int i=2;i<=n;i++)val *=x;return val;}来说，
传统算法的空间复杂度是 O(1), 时间复杂度是 O(n);
而这种改进算法的 空间复杂度和时间复杂度都是 O(log n)。
时间上达到了最优化，但是空间的要求却增加不大。
例如：计算 2^18446744073709551616,
传统 O(n) 算法需要做18446744073709551616次乘法，就算在当今最快的计算机上也要用年为单位统计程序执行时间；没有附加的空间需求。
而改进的 O(log n) 算法仅需要 64 次递归，要作128次减法+192次乘法；空间消耗要求增加 64*m（m是每次递归调用需要的栈开销大概是64-128byte）byte。就算在内存不大的低档计算机内也是毫秒级的完成时间。Top
24 楼michaelysj（其实我很傻...）回复于 2006-10-24 09:58:13 得分 0
markTop
25 楼icansaymyabc（学习与进步）回复于 2006-10-24 10:04:59 得分 0
按照 foo 的算法，一个人花有限的时间就能手工计算出 x^99999999999999999999 这样巨大的数。但是要按传统算法一个一个地手工硬乘的话，一个人花100辈子也求不出这个数来吧!?
所以楼上说这个算法很无聊的同志该努力学习了。Top
26 楼luoqintao（tooluck）回复于 2006-10-24 10:13:34 得分 0
x^nTop
27 楼qxbnit（蓝灵）回复于 2006-10-24 10:24:31 得分 0
楼上两位“讨论激烈”的boys~~
虽然我比较愚笨，数学不怎么好，，
但我还是比较支持，“mu_yang(穆扬”
理由很简单啊：字面理解-->三次分肯定比两次分减少乘法的数目多-->以此效率也高
就象两次分比x^n = x*x*x~n强一样
Top
28 楼youzelin（）回复于 2006-10-24 12:36:58 得分 0
icansaymyabc(学习与进步) ( ) 信誉：100 Blog 2006-10-24 09:54:00 得分: 0
这是一个典型的用空间换时间的求 x^n 的算法改进。
相比于传统的 x^n=f(x,n){int val=1; for(int i=2;i<=n;i++)val *=x;return val;}来说，
传统算法的空间复杂度是 O(1), 时间复杂度是 O(n);
而这种改进算法的 空间复杂度和时间复杂度都是 O(log n)。
时间上达到了最优化，但是空间的要求却增加不大。
例如：计算 2^18446744073709551616,
传统 O(n) 算法需要做18446744073709551616次乘法，就算在当今最快的计算机上也要用年为单位统计程序执行时间；没有附加的空间需求。
而改进的 O(log n) 算法仅需要 64 次递归，要作128次减法+192次乘法；空间消耗要求增加 64*m（m是每次递归调用需要的栈开销大概是64-128byte）byte。就算在内存不大的低档计算机内也是毫秒级的完成时间。
===================================================================================
谢谢，路过，学习！
Top
29 楼lurenfu（具有中国特色的社会主义初级阶段，一百年不变）回复于 2006-10-24 12:39:47 得分 0
楼上的，你的确比较愚笨
同意Kush和icansaymyabc(学习与进步)
这是一个计算幂的快速算法Top
30 楼lurenfu（具有中国特色的社会主义初级阶段，一百年不变）回复于 2006-10-24 12:40:18 得分 0
不好意思，有人插队了
错了，我指的是我楼上的楼上Top
31 楼mu_yang（穆扬）回复于 2006-10-24 12:46:16 得分 0
例如：计算 2^18446744073709551616,
------------------------------------------
题目的背景不是这样的
从
int foo ( int x , int n)
就能看出来
如果是计算2^18446744073709551616
这种极端的特例
那+-*/这些最基本的运算都必须重新考虑Top
32 楼vegetable_king（）回复于 2006-10-24 12:46:59 得分 0
好象有一点点 通了
哎 我C学的太差了
我还要看看Top
33 楼qxbnit（蓝灵）回复于 2006-10-24 13:00:18 得分 0
to lurenfu(别理我，烦着呢！) :
我好象说的也是计算幂吧……？？！！
Top
34 楼Kusk（Kusk）回复于 2006-10-24 13:16:12 得分 0
回复人：qxbnit(蓝灵) ( 一级(初级)) 信誉：100 2006-10-24 10:24:00 得分:0
?
楼上两位“讨论激烈”的boys~~
虽然我比较愚笨，数学不怎么好，，
但我还是比较支持，“mu_yang(穆扬”
理由很简单啊：字面理解-->三次分肯定比两次分减少乘法的数目多-->以此效率也高
就象两次分比x^n = x*x*x~n强一样
--------------------------------------------------------------------
三次分肯定比两次分减少乘法的数目多-->以此效率也高
这步的推导是错误的。你只看到了三分法收敛得比二分法快，但没有看到你在做三分的时候
每从x ^ n到(x * x * x) ^ (n/3)降一次就多算两个乘法(x * x * x)，而二分时每从x ^ n到(x * x) ^ (n / 2)的时候
则只多需算一个乘法(x * x)。且不说除二运算可以转化为移位运算本身就比除以3的方法快了上百倍，
就问题本身而言除2是最高层次分治。这也是为什么通常的分治都是采用二分的原因。认为除3比除2
好的朋友可以思考一下为什么归并排序、快速排序不是将数组三分、四分、N分而是二分？为什么有二分
查找却从来没有什么人提倡过什么三分查找、四分查找、N分查找？这些理论上并非不可行，但实质上
不会带来效率的提高，因为在分得多的同时，每一份分得的最单位需要做的计算量也相应提高了，就
像如果有三分归并排序的话到最后要比较出三个数的大小，还是要比二分归并花的时间多；就像我们
这个例子，若是分成三份的话，每一份要做的平均乘法数量就要增加一样。把二分改为多分反而降低
了分治的程度，因为分到最后不能再分时要处理的元素个数增加了，实际上这增加了线性计算的程度，
降低了分治的程度。极端一点，如果分得越多越好，那我干脆分成n份，就变成直接求x * x * ... * x，
也就是n个x相乘了！分倒是一次分完了，但之后呢？你只能通过线性的方法线性的复杂度去求n个x
的积！所以分得多反而只能使算法贴进线性复杂度而不是对数复杂度。二分是分得最少的，所以几乎
一切线性有关的分解都采用二分。
分治已经是算法降解的实质，分多分少只量上的差别，但不能从本质上降低求解的复杂度。其实这种问题根本不需要定量去计算，基本思维观念正确的人一眼就可以看出这一点。Top
35 楼qxbnit（蓝灵）回复于 2006-10-24 14:30:29 得分 0
被你说服了，，不过好象在n小的时候，这个算法与传统的相比并不占优势！
不过二分的确比三分有效率，单从乘法的角度考虑
我疏忽了三分余数部分的乘法
count2 1 if n = 0
count2 3 if n = 1
count2 5 if n = 2
count2 7 if n = 4
count2 8 if n = 0
count2 10 if n = 1
count2 12 if n = 2
count2 14 if n = 4
----------foo2(2,4) = 16----------
count3 2 if n = 0
count3 5 if n = 1
count3 8 if n = 4
count3 10 if n = 0
count3 13 if n = 1
count3 16 if n = 4
----------foo3(2,4) = 16----------
count2 2 if n = 0
count2 4 if n = 1
count2 6 if n = 2
count2 8 if n = 5
count2 10 if n = 10
count2 12 if n = 20
count2 14 if n = 40
count2 16 if n = 0
count2 18 if n = 1
count2 20 if n = 2
count2 22 if n = 5
count2 24 if n = 10
count2 26 if n = 20
count2 28 if n = 40
----------foo2(2,40) = 0----------
count3 4 if n = 0
count3 7 if n = 1
count3 10 if n = 4
count3 13 if n = 13
count3 16 if n = 40
count3 20 if n = 0
count3 23 if n = 1
count3 26 if n = 4
count3 29 if n = 13
count3 32 if n = 40
----------foo3(2,40) = 0----------
count2 3 if n = 0
count2 5 if n = 1
count2 7 if n = 3
count2 9 if n = 6
count2 11 if n = 12
count2 13 if n = 25
count2 15 if n = 50
count2 17 if n = 100
count2 19 if n = 200
count2 21 if n = 400
count2 24 if n = 0
count2 26 if n = 1
count2 28 if n = 3
count2 30 if n = 6
count2 32 if n = 12
count2 34 if n = 25
count2 36 if n = 50
count2 38 if n = 100
count2 40 if n = 200
count2 42 if n = 400
----------foo2(2,400) = 0----------
count3 8 if n = 0
count3 11 if n = 1
count3 14 if n = 4
count3 17 if n = 14
count3 20 if n = 44
count3 23 if n = 133
count3 26 if n = 400
count3 34 if n = 0
count3 37 if n = 1
count3 40 if n = 4
count3 43 if n = 14
count3 46 if n = 44
count3 49 if n = 133
count3 52 if n = 400
----------foo3(2,400) = 0----------
count2 6 if n = 0
count2 8 if n = 1
count2 10 if n = 3
count2 12 if n = 7
count2 14 if n = 15
count2 16 if n = 31
count2 18 if n = 62
count2 20 if n = 125
count2 22 if n = 250
count2 24 if n = 500
count2 26 if n = 1000
count2 28 if n = 2000
count2 30 if n = 4000
count2 36 if n = 0
count2 38 if n = 1
count2 40 if n = 3
count2 42 if n = 7
count2 44 if n = 15
count2 46 if n = 31
count2 48 if n = 62
count2 50 if n = 125
count2 52 if n = 250
count2 54 if n = 500
count2 56 if n = 1000
count2 58 if n = 2000
count2 60 if n = 4000
----------foo2(2,4000) = 0----------
count3 8 if n = 0
count3 11 if n = 1
count3 14 if n = 5
count3 17 if n = 16
count3 20 if n = 49
count3 23 if n = 148
count3 26 if n = 444
count3 29 if n = 1333
count3 32 if n = 4000
count3 40 if n = 0
count3 43 if n = 1
count3 46 if n = 5
count3 49 if n = 16
count3 52 if n = 49
count3 55 if n = 148
count3 58 if n = 444
count3 61 if n = 1333
count3 64 if n = 4000
----------foo3(2,4000) = 0----------
Terminated with return code 0
Press any key to continue ...
Top
36 楼qxbnit（蓝灵）回复于 2006-10-24 15:06:43 得分 0
#include <stdio.h>
int count2 = 0;
int count3 = 0;
double foo2 (double x , int n)
{
double val;
val =1.0;
if (n>0)
{
if (n%2 == 1){
val = val *x;
count2++;
}
val = val * foo2(x*x , n/2);
count2+=1;//x*x:只计算一次就够了
}
printf("count2 %d if n = %d \n" , count2+1 , n);
return val;
}
double foo3(double x , int n){
double val;
val =1.0;
if (n>0)
{
if (n%3 == 1){
val = val *x;
count3++;
}
if (n%3 == 2){
val = val *x *x;
count3+=2;
}
val = val * foo3(x*x*x , n/3);
count3+=1;//x*x*x:只计算一次就够了
}
printf("count3 %d if n = %d \n" , count3+1 , n);
return val;
}
int main(){
count2 = 0;
count3 = 0;
foo2(1.1,4);
printf("----------foo2(1.1,4) = %f----------\n",foo2(1.1,4));
foo3(1.1,4);
printf("----------foo3(1.1,4) = %f----------\n",foo3(1.1,4));
count2 = 0;
count3 = 0;
foo2(1.1,8);
printf("----------foo2(1.1,8) = %f----------\n",foo2(1.1,8));
foo3(1.1,8);
printf("----------foo3(1.1,8) = %f----------\n",foo3(1.1,8));
count2 = 0;
count3 = 0;
foo2(1.1,6);
printf("----------foo2(1.1,6) = %f----------\n",foo2(1.1,6));
foo3(1.1,6);
printf("----------foo3(1.1,6) = %f----------\n",foo3(1.1,6));
count2 = 0;
count3 = 0;
foo2(1.1,12);
printf("----------foo2(1.1,12) = %f----------\n",foo2(1.1,12));
foo3(1.1,12);
printf("----------foo3(1.1,12) = %f----------\n",foo3(1.1,12));
count2 = 0;
count3 = 0;
foo2(1.1,7);
printf("----------foo2(1.1,7) = %f----------\n",foo2(1.1,7));
foo3(1.1,7);
printf("----------foo3(1.1,7) = %f----------\n",foo3(1.1,7));
count2 = 0;
count3 = 0;
foo2(1.1,14);
printf("----------foo2(1.1,14) = %f----------\n",foo2(1.1,14));
foo3(1.1,14);
printf("----------foo3(1.1,14) = %f----------\n",foo3(1.1,14));
}
结果：
count2 2 if n = 0
count2 3 if n = 1
count2 4 if n = 2
count2 5 if n = 4
count2 6 if n = 0
count2 7 if n = 1
count2 8 if n = 2
count2 9 if n = 4
----------foo2(1.1,4) = 1.464100----------
count3 3 if n = 0
count3 4 if n = 1
count3 5 if n = 4
count3 7 if n = 0
count3 8 if n = 1
count3 9 if n = 4
----------foo3(1.1,4) = 1.464100----------
count2 2 if n = 0
count2 3 if n = 1
count2 4 if n = 2
count2 5 if n = 4
count2 6 if n = 8
count2 7 if n = 0
count2 8 if n = 1
count2 9 if n = 2
count2 10 if n = 4
count2 11 if n = 8
----------foo2(1.1,8) = 2.143589----------
count3 5 if n = 0
count3 6 if n = 2
count3 7 if n = 8
count3 11 if n = 0
count3 12 if n = 2
count3 13 if n = 8
----------foo3(1.1,8) = 2.143589----------
count2 3 if n = 0
count2 4 if n = 1
count2 5 if n = 3
count2 6 if n = 6
count2 8 if n = 0
count2 9 if n = 1
count2 10 if n = 3
count2 11 if n = 6
----------foo2(1.1,6) = 1.771561----------
count3 3 if n = 0
count3 4 if n = 2
count3 5 if n = 6
count3 7 if n = 0
count3 8 if n = 2
count3 9 if n = 6
----------foo3(1.1,6) = 1.771561----------
count2 3 if n = 0
count2 4 if n = 1
count2 5 if n = 3
count2 6 if n = 6
count2 7 if n = 12
count2 9 if n = 0
count2 10 if n = 1
count2 11 if n = 3
count2 12 if n = 6
count2 13 if n = 12
----------foo2(1.1,12) = 3.138428----------
count3 3 if n = 0
count3 4 if n = 1
count3 5 if n = 4
count3 6 if n = 12
count3 8 if n = 0
count3 9 if n = 1
count3 10 if n = 4
count3 11 if n = 12
----------foo3(1.1,12) = 3.138428----------
count2 4 if n = 0
count2 5 if n = 1
count2 6 if n = 3
count2 7 if n = 7
count2 10 if n = 0
count2 11 if n = 1
count2 12 if n = 3
count2 13 if n = 7
----------foo2(1.1,7) = 1.948717----------
count3 4 if n = 0
count3 5 if n = 2
count3 6 if n = 7
count3 9 if n = 0
count3 10 if n = 2
count3 11 if n = 7
----------foo3(1.1,7) = 1.948717----------
count2 4 if n = 0
count2 5 if n = 1
count2 6 if n = 3
count2 7 if n = 7
count2 8 if n = 14
count2 11 if n = 0
count2 12 if n = 1
count2 13 if n = 3
count2 14 if n = 7
count2 15 if n = 14
----------foo2(1.1,14) = 3.797498----------
count3 5 if n = 0
count3 6 if n = 1
count3 7 if n = 4
count3 8 if n = 14
count3 12 if n = 0
count3 13 if n = 1
count3 14 if n = 4
count3 15 if n = 14
----------foo3(1.1,14) = 3.797498----------
Terminated with return code 0
Press any key to continue ...
===============
如果这样考虑，三分法 并不比 两分 吃亏 （单从乘法考虑）
不过，我统计的方法可能不对
若干年后再看这个问题，可能我自己会觉得比较傻~
Top
37 楼enderjiang（）回复于 2006-10-25 13:58:06 得分 0
markTop
38 楼davecom（IT新人）回复于 2006-10-25 19:53:52 得分 0
AAAAAAAAAAAAAAAAAAAAAAA 函数的递归调用，没问题！！！！！！！Top
39 楼zhongdu（中毒）回复于 2006-10-25 20:53:28 得分 0
markTop
40 楼windnum1（非宁静无以致远）回复于 2006-10-28 10:53:48 得分 0
夷， 天上会不会掉分呢？Top
41 楼gjb999（老鼠老鼠还是一只老鼠！）回复于 2006-10-28 20:30:19 得分 0
夷， 天上掉分会砸到你吗?Top
42 楼dfsong（dandan）回复于 2006-10-29 09:58:23 得分 0
x^n, so easyTop
43 楼lsd1025（）回复于 2006-10-29 14:46:07 得分 0
(a)
看了后完全赞同Kusk说法，他的讲解个人认为很正确Top
