關(guān)于爬樓問(wèn)題的最優(yōu)算法實(shí)現(xiàn)
爬樓問(wèn)題：假設(shè)有一段n階的樓梯秤涩，每次可以爬1階或者2階帜乞，問(wèn)：共有多少種爬樓方式.
分析問(wèn)題：假設(shè)n階樓梯的爬樓方式有f(n)種
當(dāng)n=1時(shí)，得到f(1)=1;
當(dāng)n=2時(shí)筐眷，得到f(2)=2;
當(dāng)n>2時(shí),如果第一步走1步的話(huà)則有f(n-1)種方式黎烈，如果第一步走2步的話(huà)則有f(n-2)種，所以可得:f(n)=f(n-1)+f(n-2);
分析完畢浊竟，接下來(lái)就是代碼的實(shí)現(xiàn)了怨喘。
方案一:
由分析很容易想到遞歸的方式來(lái)設(shè)計(jì)代碼.設(shè)計(jì)代碼如下:
unsigned long stepWays(unsigned long num){
if (num == 1) {
return 1;
}
if (num == 2) {
return 2;
}
return stepWays(num-1)+stepWays(num-2);
}
運(yùn)行一下代碼測(cè)試一下
NSDate *date = [NSDate date];
printf("方案一有%lu種方式",stepWays(45));
NSTimeInterval time = date.timeIntervalSinceNow*-1;
printf("\n耗時(shí):%lfs",time);
結(jié)果如下：
方案一有1836311903種方式
耗時(shí):6.249614s
考慮到時(shí)間和空間復(fù)雜度的問(wèn)題，顯然遞歸并不是一個(gè)好的算法解決方案振定。所以考慮到不使用遞歸的方案二來(lái)實(shí)現(xiàn)必怜。
方案二:
根據(jù)f(n)=f(n-1)+f(n-2)表達(dá)式，設(shè)計(jì)代碼如下：
unsigned long stepWays2(unsigned long num){
if (num == 1) {
return 1;
}
if (num == 2) {
return 2;
}
unsigned long n = 3;
unsigned long n1 = 1;//f(n-2)
unsigned long n2 = 2;//f(n-1)
unsigned long res = 0 ;//f(n)
while (n <= num) {
res = n1 + n2;
n1 = n2;
n2 = res;
n ++;
}
return res;
}
很明顯方案二這種設(shè)計(jì)在復(fù)雜度上來(lái)說(shuō)是最優(yōu)的后频。驗(yàn)證一下：
NSDate *date = [NSDate date];
printf("方案二共有%lu種方式",stepWays2(45));
NSTimeInterval time = date.timeIntervalSinceNow*-1;
printf("\n耗時(shí):%lfs",time);
輸出如下：
方案二共有1836311903種方式
耗時(shí):0.000023s
驗(yàn)證方案二為最優(yōu)解
