OJ題：超級臺階 時間限制：1000 ms | 內(nèi)存限制：65535 KB 難度：3 描述 有一樓梯共m級，剛開始時你在第一級，若每次只能跨上一級或二級，要走上第m級，共有多少走法？
注：規(guī)定從一級到一級有0種走法。
輸入 輸入數(shù)據(jù)首先包含一個整數(shù)n(1<=n<=100)，表示測試實例的個數(shù)，然后是n行數(shù)據(jù)，每行包含一個整數(shù)m，（1<=m<=40), 表示樓梯的級數(shù)。
輸出 對于每個測試實例，請輸出不同走法的數(shù)量。
一開始是用一個遞推公式來求n階臺階的走法 f(n) = f(n-1) +f(n-2) 從第4階臺階開始，到達(dá)第n階臺階總共有兩種方法，一是從n-1階臺階一次走一步，一是從n-2階臺階一次走兩步，而從n-2階臺階先走一步再走一步到達(dá)的這種情況，實際上是從n-2階臺階先走一步到達(dá)n-1階再走一步，是屬于第一種情況的 以此便可以得出上述遞推式。 而n為1、2、3的情況直接求出便可。 這樣便得出求走n階臺階的方法的函數(shù)
#include <iostream>using namespace std;int f(int m){ if(i==1) return 0; if(i==2) return 1; if(i==3) return 2; return f(m-1)+f(m-2);}int main(){ int s;cin>>s; while(s--) { int m;cin>>m; cout<<f(m)<<endl; } return 0;}而在主函數(shù)調(diào)用時發(fā)現(xiàn)超時 仔細(xì)研究，覺得這個遞推公式應(yīng)該已經(jīng)是最簡單的了 雖然知道遞歸那里時間復(fù)雜度很高，但是發(fā)現(xiàn)每次調(diào)用f（）函數(shù)都要進(jìn)行3次判斷。 剛好發(fā)現(xiàn)了前面的操作可以合成為一個，于是把f（）函數(shù)改成
int f(int m){ if(m<=3) return m-1; return f(m-1)+f(m-2);}這樣時間復(fù)雜度前面的系數(shù)可以變成1/3。 但是果然還是太天真了，還是遞歸了太多層才超的時 突然看到輸入限制中，1<=m<=40 突然想到可以做一個數(shù)組，直接把每一個值的結(jié)果求出來，而因為前面的值已經(jīng)求出來了，求當(dāng)前第n階的方法時，就只需要執(zhí)行一次加法操作 a[n]=a[n-1]+a[n-2]; 果然 修改代碼后AC了。
#include <iostream>using namespace std;int main(){ int s;cin>>s; int a[41]; a[1]=0;a[2]=1;a[3]=2; for(int j=4;j<=40;j++) a[j]=a[j-1]+a[j-2]; while(s--) { int m;cin>>m; cout<<a[m]<<endl; } }然后突然想到前兩天剛開始做OJ做了一道題，一直超時，好像也可以這樣求出來，于是立馬回到那題
OJ題目：孿生素數(shù)問題 時間限制：3000 ms | 內(nèi)存限制：65535 KB 難度：3 描述 寫一個程序，找出給出素數(shù)范圍內(nèi)的所有孿生素數(shù)的組數(shù)。一般來說，孿生素數(shù)就是指兩個素數(shù)距離為2，近的不能再近的相鄰素數(shù)。有些童鞋一看到題就開始寫程序，不仔細(xì)看題，咱們?yōu)榱硕糁埔幌伦x題不認(rèn)真仔細(xì)的童鞋，規(guī)定，兩個素數(shù)相鄰為1的也成為孿生素數(shù)。
輸入 第一行給出N表示測試數(shù)據(jù)組數(shù)。(1<=N<100) 接下來組測試數(shù)據(jù)給出m，表示找出m之前的所有孿生素數(shù)。 (1<=m<1000000)
輸出 每組測試數(shù)據(jù)輸出占一行，該行為m范圍內(nèi)所有孿生素數(shù)組數(shù)
這個問題，一開始是從3開始，遍歷所有不大于m的奇數(shù)，先判斷這個奇數(shù)是不是質(zhì)數(shù)，如果是再判斷相鄰的奇數(shù)是不是質(zhì)數(shù)。 判斷素數(shù)需要√n的時間復(fù)雜度，總共有n/2個數(shù)要判斷。 雖然不能直接相乘，但是應(yīng)該和√n*n的規(guī)模差不多 而m取到最大值的時候，顯然就超時
當(dāng)時做這題篩選法求質(zhì)數(shù)也沒做出來，反而一經(jīng)上題啟發(fā) 直接就開始寫
#include <iostream>using namespace std;int a[1000001];bool PRime(int n){ if(n<=1) return false; for(int i=2;i*i<=n;i++) if(n%i==0) return false; return true;}int pri(int n){ if(prime(n)&&prime(n-2)) return 1; else return 0;}int main(){ a[1]=0;a[2]=0;a[3]=1; for(int i=4;i<1000001;i++) { a[i]=a[i-1]+pri(i); } int s;cin>>s; while(s--) { int n;cin>>n; cout<<a[n]<<endl; } return 0;}基本操作就變成了 a[i]=a[i-1]+pri(i);
兩道題共同的地方就是，規(guī)模已知，然后第n次結(jié)果與前面的結(jié)果有關(guān)聯(lián)，但是如果用遞歸或者蠻力，會很復(fù)雜，并且每次求一個不同的n，都要重新算。那么這樣的話，建立一個等規(guī)模的數(shù)組，直接用前面的值按照公式去推后面的值，應(yīng)該會要好一些。
新聞熱點
疑難解答
