高中生程式解題系統

#24609: TLE怎麼解

caspar.cy.lin@gmail.com (林承諭)

學校 : 不指定學校
編號 : 133317
來源 : [114.44.78.235]
最後登入時間：
2022-07-27 16:34:29

f424. 高雄市109年資訊競賽國中組第二題 -- 2020 高雄市資訊學科能力複賽 109高雄市資訊學科能力複賽 | From: [1.163.145.59] | 發表日期 : 2021-03-10 22:41

#include <bits/stdc++.h>

using namespace std;

long long f(long long a);

int main(void){

ios_base::sync_with_stdio(false);

cin.tie(0);

long long n;

while(cin>>n){

cout<<f(n)<<endl;

}

return 0;

}

long long f(long long a){

if(a>2)

return f(a-1)+f(a-2);

else if(a==2)

return 3;

else

return 1;

}

如何處理TLE 謝謝

| 回應文章 | 回原始文章

#24634: Re:TLE怎麼解

fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [59.115.180.44]
最後登入時間：
2024-05-03 16:46:17

f424. 高雄市109年資訊競賽國中組第二題 -- 2020 高雄市資訊學科能力複賽 109高雄市資訊學科能力複賽 | From: [61.230.1.112] | 發表日期 : 2021-03-11 19:17

#include <bits/stdc++.h>

using namespace std;

long long f(long long a);

int main(void){

ios_base::sync_with_stdio(false);

cin.tie(0);

long long n;

while(cin>>n){

cout<<f(n)<<endl;

}

return 0;

}

long long f(long long a){

if(a>2)

return f(a-1)+f(a-2);

else if(a==2)

return 3;

else

return 1;

}

如何處理TLE 謝謝

建表

| 回應文章 | 回原始文章

#24637: Re:TLE怎麼解

caspar.cy.lin@gmail.com (林承諭)

學校 : 不指定學校
編號 : 133317
來源 : [114.44.78.235]
最後登入時間：
2022-07-27 16:34:29

f424. 高雄市109年資訊競賽國中組第二題 -- 2020 高雄市資訊學科能力複賽 109高雄市資訊學科能力複賽 | From: [1.163.145.59] | 發表日期 : 2021-03-11 21:59

#include <bits/stdc++.h>

using namespace std;

long long f(long long a);

int main(void){

ios_base::sync_with_stdio(false);

cin.tie(0);

long long n;

while(cin>>n){

cout<<f(n)<<endl;

}

return 0;

}

long long f(long long a){

if(a>2)

return f(a-1)+f(a-2);

else if(a==2)

return 3;

else

return 1;

}

如何處理TLE 謝謝

建表

這樣不是要很久嗎

| 回應文章 | 回原始文章

#24638: Re:TLE怎麼解

fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [59.115.180.44]
最後登入時間：
2024-05-03 16:46:17

f424. 高雄市109年資訊競賽國中組第二題 -- 2020 高雄市資訊學科能力複賽 109高雄市資訊學科能力複賽 | From: [61.230.1.112] | 發表日期 : 2021-03-11 22:07

#include <bits/stdc++.h>

using namespace std;

long long f(long long a);

int main(void){

ios_base::sync_with_stdio(false);

cin.tie(0);

long long n;

while(cin>>n){

cout<<f(n)<<endl;

}

return 0;

}

long long f(long long a){

if(a>2)

return f(a-1)+f(a-2);

else if(a==2)

return 3;

else

return 1;

}

如何處理TLE 謝謝

建表

這樣不是要很久嗎

你用遞迴才更慢查f(40)時會一直重複呼叫f(1)、f(2)

直接建表1~40而已沒有多慢

| 回應文章 | 回原始文章

#24639: Re:TLE怎麼解

fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [59.115.180.44]
最後登入時間：
2024-05-03 16:46:17

f424. 高雄市109年資訊競賽國中組第二題 -- 2020 高雄市資訊學科能力複賽 109高雄市資訊學科能力複賽 | From: [61.230.1.112] | 發表日期 : 2021-03-11 22:09

#include <bits/stdc++.h>

using namespace std;

long long f(long long a);

int main(void){

ios_base::sync_with_stdio(false);

cin.tie(0);

long long n;

while(cin>>n){

cout<<f(n)<<endl;

}

return 0;

}

long long f(long long a){

if(a>2)

return f(a-1)+f(a-2);

else if(a==2)

return 3;

else

return 1;

}

如何處理TLE 謝謝

建表

這樣不是要很久嗎

你用遞迴才更慢查f(40)時會一直重複呼叫f(1)、f(2)

直接建表1~40而已沒有多慢

#include <stdio.h>
#include <stdlib.h>

int n;

int fibo[50];

int main(void) {
    scanf("%d", &n);
    fibo[0] = 1, fibo[1] = 3;
    for(int i = 2; i < n; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }
    printf("%d\n", fibo[n - 1]);
    return 0;
}

動態規劃的理念

| 回應文章 | 回原始文章

#25561: Re:TLE怎麼解

jammy42786898@gmail.com (よだよ)

學校 : 高雄市立高雄高級中學
編號 : 79989
來源 : [122.254.32.249]
最後登入時間：
2022-02-09 23:21:15

f424. 高雄市109年資訊競賽國中組第二題 -- 2020 高雄市資訊學科能力複賽 109高雄市資訊學科能力複賽 | From: [122.254.32.249] | 發表日期 : 2021-06-01 23:05

#include <bits/stdc++.h>

using namespace std;

long long f(long long a);

int main(void){

ios_base::sync_with_stdio(false);

cin.tie(0);

long long n;

while(cin>>n){

cout<<f(n)<<endl;

}

return 0;

}

long long f(long long a){

if(a>2)

return f(a-1)+f(a-2);

else if(a==2)

return 3;

else

return 1;

}

如何處理TLE 謝謝

建表

這樣不是要很久嗎

你用遞迴才更慢查f(40)時會一直重複呼叫f(1)、f(2)

直接建表1~40而已沒有多慢
#include 
#include 

int n;

int fibo[50];

int main(void) {
    scanf("%d", &n);
    fibo[0] = 1, fibo[1] = 3;
    for(int i = 2; i < n; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }
    printf("%d\n", fibo[n - 1]);
    return 0;
}
動態規劃的理念

遞迴為什麼不行?

我才AC (2ms, 332KB)

| 回應文章 | 回原始文章

#25562: Re:TLE怎麼解

jammy42786898@gmail.com (よだよ)

學校 : 高雄市立高雄高級中學
編號 : 79989
來源 : [122.254.32.249]
最後登入時間：
2022-02-09 23:21:15

f424. 高雄市109年資訊競賽國中組第二題 -- 2020 高雄市資訊學科能力複賽 109高雄市資訊學科能力複賽 | From: [122.254.32.249] | 發表日期 : 2021-06-01 23:07

#include <bits/stdc++.h>

using namespace std;

long long f(long long a);

int main(void){

ios_base::sync_with_stdio(false);

cin.tie(0);

long long n;

while(cin>>n){

cout<<f(n)<<endl;

}

return 0;

}

long long f(long long a){

if(a>2)

return f(a-1)+f(a-2);

else if(a==2)

return 3;

else

return 1;

}

如何處理TLE 謝謝

建表

這樣不是要很久嗎

你用遞迴才更慢查f(40)時會一直重複呼叫f(1)、f(2)

直接建表1~40而已沒有多慢
#include 
#include 

int n;

int fibo[50];

int main(void) {
    scanf("%d", &n);
    fibo[0] = 1, fibo[1] = 3;
    for(int i = 2; i < n; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }
    printf("%d\n", fibo[n - 1]);
    return 0;
}
動態規劃的理念
遞迴為什麼不行?

我才AC (2ms, 332KB)

長這樣

#include <iostream>
#include <cstdlib>
using namespace std;
inline int dihuei(int a, int b, int c) //b=1  c=3
{
    if (a == 1 && b == 1)
        return 1;
    if (a == 2 && c == 3)
        return 3;
    if (a > 2)
    {
        int x;
        x = b + c;
        return dihuei(a - 1, c, x);
    }
    else
        return c;
}
int main()
{
    int a;
    cin >> a;
    cout << dihuei(a, 1, 3) << "\n";
    system("pause");
    return 0;
}

| 回應文章 | 回原始文章

#25563: Re:TLE怎麼解

jammy42786898@gmail.com (よだよ)

學校 : 高雄市立高雄高級中學
編號 : 79989
來源 : [122.254.32.249]
最後登入時間：
2022-02-09 23:21:15

f424. 高雄市109年資訊競賽國中組第二題 -- 2020 高雄市資訊學科能力複賽 109高雄市資訊學科能力複賽 | From: [122.254.32.249] | 發表日期 : 2021-06-01 23:17

#include <bits/stdc++.h>

using namespace std;

long long f(long long a);

int main(void){

ios_base::sync_with_stdio(false);

cin.tie(0);

long long n;

while(cin>>n){

cout<<f(n)<<endl;

}

return 0;

}

long long f(long long a){

if(a>2)

return f(a-1)+f(a-2);

else if(a==2)

return 3;

else

return 1;

}

如何處理TLE 謝謝

建表

這樣不是要很久嗎

你用遞迴才更慢查f(40)時會一直重複呼叫f(1)、f(2)

直接建表1~40而已沒有多慢
#include 
#include 

int n;

int fibo[50];

int main(void) {
    scanf("%d", &n);
    fibo[0] = 1, fibo[1] = 3;
    for(int i = 2; i < n; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }
    printf("%d\n", fibo[n - 1]);
    return 0;
}
動態規劃的理念
遞迴為什麼不行?

我才AC (2ms, 332KB)
長這樣

#include <iostream>

#include <cstdlib>

using namespace std;

inline int dihuei(int a, int b, int c) //b=1  c=3

{

    if (a == 1 && b == 1)

        return 1;

    if (a == 2 && c == 3)

        return 3;

    if (a > 2)

    {

        int x;

        x = b + c;

        return dihuei(a - 1, c, x);

    }

    else

        return c;

}

int main()

{

    int a;

    cin >> a;

    cout << dihuei(a, 1, 3) << "\n";

    system("pause");

    return 0;

}

應該是你重複算的東西太多了

你的話會長這樣

f(2)

f(3)

f(4) f(1)

f(2)

f(5)

f(2)

f(3)

f(1)

| 回應文章 | 回原始文章

#25564: Re:TLE怎麼解

jammy42786898@gmail.com (よだよ)

學校 : 高雄市立高雄高級中學
編號 : 79989
來源 : [122.254.32.249]
最後登入時間：
2022-02-09 23:21:15

f424. 高雄市109年資訊競賽國中組第二題 -- 2020 高雄市資訊學科能力複賽 109高雄市資訊學科能力複賽 | From: [122.254.32.249] | 發表日期 : 2021-06-01 23:20

#include <bits/stdc++.h>

using namespace std;

long long f(long long a);

int main(void){

ios_base::sync_with_stdio(false);

cin.tie(0);

long long n;

while(cin>>n){

cout<<f(n)<<endl;

}

return 0;

}

long long f(long long a){

if(a>2)

return f(a-1)+f(a-2);

else if(a==2)

return 3;

else

return 1;

}

如何處理TLE 謝謝

建表

這樣不是要很久嗎

你用遞迴才更慢查f(40)時會一直重複呼叫f(1)、f(2)

直接建表1~40而已沒有多慢
#include 
#include 

int n;

int fibo[50];

int main(void) {
    scanf("%d", &n);
    fibo[0] = 1, fibo[1] = 3;
    for(int i = 2; i < n; i++) {
        fibo[i] = fibo[i - 1] + fibo[i - 2];
    }
    printf("%d\n", fibo[n - 1]);
    return 0;
}
動態規劃的理念
遞迴為什麼不行?

我才AC (2ms, 332KB)
長這樣

#include <iostream>

#include <cstdlib>

using namespace std;

inline int dihuei(int a, int b, int c) //b=1  c=3

{

    if (a == 1 && b == 1)

        return 1;

    if (a == 2 && c == 3)

        return 3;

    if (a > 2)

    {

        int x;

        x = b + c;

        return dihuei(a - 1, c, x);

    }

    else

        return c;

}

int main()

{

    int a;

    cin >> a;

    cout << dihuei(a, 1, 3) << "\n";

    system("pause");

    return 0;

}
應該是你重複算的東西太多了

你的話會長這樣

f(2)

f(3)

f(4) f(1)

f(2)

f(5)

f(2)

f(3)

f(1)

如此一來又會變成另一題的遞迴

f(3)=2 f(4)=3 f(5)=f(3)+f(4).......

f(n)=f(n-1)+f(n-2)

| 回應文章 | 回原始文章

ZeroJudge Forum