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
說的有點亂，看一下就明白了。