#26453: 5.4s. 小見解


alexchiu121212@gmail.com (Alex Chiu)

School : No School
ID : 159421
IP address : []
Last Login :
2021-07-26 10:43:52
b127. 會議中心(Room) -- 96學年度台北市資訊學科能力競賽 | From: [111.71.215.33] | Post Date : 2021-08-07 16:23

#include<iostream>

using namespace std;

 

int f(int N)

{

if(N==1)

return 1;

if(N==2)

return 2;

if(N>=3)

return f(N-1)+f(N-2);       /*發現後面答案都是f(N-1)和f(N-2)的結果相加*/

}

 

int main(void)

{

int N;

 

while(cin>>N)

cout<<f(N)<<endl;

 

return 0;

}

 

 
#26947: Re:5.4s. 小見解


yp10871039 ( )

School : 臺北市私立延平高級中學
ID : 104506
IP address : [203.72.178.1]
Last Login :
2024-06-03 13:37:14
b127. 會議中心(Room) -- 96學年度台北市資訊學科能力競賽 | From: [36.228.115.57] | Post Date : 2021-09-04 15:08

#include

using namespace std;

 

int f(int N)

{

if(N==1)

return 1;

if(N==2)

return 2;

if(N>=3)

return f(N-1)+f(N-2);       /*發現後面答案都是f(N-1)和f(N-2)的結果相加*/

}

 

int main(void)

{

int N;

 

while(cin>>N)

cout<<f(N)<<endl;

 

return 0;

}

 

時間複雜度O(2^n)

你跑 N=100 試試看

他會算到天荒地老

 

用DP 只有 時間複雜度只有 O(n)

DP大概像這樣

#include<cstdio>
main(){
int a,b,n;
while(~scanf("%d",&n)){
a=b=1;
while(n--)
a=(b+=a)-a;
printf("%d\n",a);
}
}
AC (2ms, 72KB)
 
ZeroJudge Forum