Lucy上了初中,她很喜欢数学,经常做数学奥林匹克的题目,可是今天她遇到了难题,于是就向她在南开大学上学的哥哥Feagle请教,聪明的哥哥不一会功夫就编程解决了妹妹的问题(^_^,南开大学的学生就是优秀)! 妹妹的题目是这样的:对给定的f(n) 当 n>=50025002 的时候,f(n)=n-5;当 n<50025002 的时候,f(n)=f(f(n+2005))。现在请您试试编程解决Lucy的难题!
输入
输入只有一个整数n,-2147483647<n<2147483647 。
输出
输出只有一个整数,f(n) 的值。
样例输入 样例输出
50025002 50024997
时间限制
对每个输入数据,程序应在5秒内给出结果。
我分别用递归和非递归做了一下，本来想把没个函数的运行时间算一下，我用的是clock()，结果是开始时间和结束时间是一样的，我也就没放上了，谁帮忙计算出这两个函数时间上的差异
1
#include
<
iostream
>
2
#include
<
time.h
>
3
long
count_1(
long
n);
4
long
count_2(
long
n);
5
int
main(
int
argc,
char
*
argv[])
6
{
7
long
n,result_1
=
0
,result_2
=
0
;
8
while
(
1
)
9
{
10
printf(
"
\nPlease Input A Number:
"
);
11
scanf(
"
%ld
"
,
&
n);
12
result_1
=
count_1(n);
13
result_2
=
count_2(n);
14
printf(
"
\ncount_1:%ld\ncount_2:%ld\n
"
,result_1,result_2);
15
}
16
}
17
18
long
count_1(
long
n)
19
{
20
long
i
=
1
;
21
while
(i)
22
{
23
if
(n
>=
50025002
)
24
{
25
n
-=
5
;
26
i
--
;
27
}
28
else
29
{
30
n
+=
2005
;
31
i
++
;
32
}
33
}
34
return
n;
35
}
36
37
long
count_2(
long
n)
38
{
39
long
m,tmp;
40
if
(n
>=
50025002
)
41
m
=
n
-
5
;
42
else
43
{
44
tmp
=
count_2(n
+
2005
);
45
m
=
count_2(tmp);
46
}
47
return
m;
48
}
49
说一下那个非递归调用的算法吧。
把x做为+2005的次数，y作为-5的次数
如果n>=50025002，那么不需要做+的操作，所以
y-x=1
否则n<50025002，就需要先+2005，再-5，x和y同时+1
因此，最终y-x=1。
所以先将i设为1
说的有点乱，看一下就明白了。