Lucy上了初中,她很喜歡數(shù)學(xué),經(jīng)常做數(shù)學(xué)奧林匹克的題目,可是今天她遇到了難題,于是就向她在南開(kāi)大學(xué)上學(xué)的哥哥Feagle請(qǐng)教,聰明的哥哥不一會(huì)功夫就編程解決了妹妹的問(wèn)題(^_^,南開(kāi)大學(xué)的學(xué)生就是優(yōu)秀)! 妹妹的題目是這樣的:對(duì)給定的f(n) 當(dāng) n>=50025002 的時(shí)候,f(n)=n-5;當(dāng) n<50025002 的時(shí)候,f(n)=f(f(n+2005))。現(xiàn)在請(qǐng)您試試編程解決Lucy的難題!
輸入
輸入只有一個(gè)整數(shù)n,-2147483647<n<2147483647 。?
? 輸出
輸出只有一個(gè)整數(shù),f(n) 的值。
? 樣例輸入 樣例輸出
50025002 50024997
??
? 時(shí)間限制
??
對(duì)每個(gè)輸入數(shù)據(jù),程序應(yīng)在5秒內(nèi)給出結(jié)果。
我分別用遞歸和非遞歸做了一下，本來(lái)想把沒(méi)個(gè)函數(shù)的運(yùn)行時(shí)間算一下，我用的是clock()，結(jié)果是開(kāi)始時(shí)間和結(jié)束時(shí)間是一樣的，我也就沒(méi)放上了，誰(shuí)幫忙計(jì)算出這兩個(gè)函數(shù)時(shí)間上的差異
?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
說(shuō)一下那個(gè)非遞歸調(diào)用的算法吧。
把x做為+2005的次數(shù)，y作為-5的次數(shù)
如果n>=50025002，那么不需要做+的操作，所以
y-x=1
否則n<50025002，就需要先+2005，再-5，x和y同時(shí)+1
因此，最終y-x=1。
所以先將i設(shè)為1
說(shuō)的有點(diǎn)亂，看一下就明白了。