一步一步寫算法（之爬樓梯）

1、 HYPERLINK /feixiaoxing/article/details/6871148一步一步寫算法（之爬樓梯） 前兩天上網(wǎng)的時(shí)候看到一個(gè)特別有意思的題目，在這里和朋友們分享一下： 有一個(gè)人準(zhǔn)備開始爬樓梯，假設(shè)樓梯有n個(gè)，這個(gè)人只允許一次爬一個(gè)樓梯或者一次爬兩個(gè)樓梯，請問有多少種爬法？ 在揭曉答案之前，朋友們可以自己先考慮一下： 這個(gè)人爬n層樓梯，那么它也不是一下子就可以爬這么高的，他只有兩個(gè)選擇，要么從n-2層爬過來，要么從n-1層爬過來。除此之外，他沒有別的選擇。此時(shí)相信朋友其實(shí)已經(jīng)早看出來了，這就是一道基本的遞歸題目。 （1）首先我們建立一個(gè)函數(shù)，判斷函數(shù)的合法性cpp HYPE

2、RLINK /feixiaoxing/article/details/6871148#view plainHYPERLINK /feixiaoxing/article/details/6871148#copyvoid jump_ladder(int layer, int* stack, int* top) if(layer = 0) return; return; （2）判斷當(dāng)前的層數(shù)是為1或者是否為2cpp HYPERLINK /feixiaoxing/article/details/6871148#view plainHYPERLINK /feixiaoxing/article/detai

3、ls/6871148#copyvoid jump_ladder(int layer, int* stack, int* top) if(layer = 0; index -) printf(%d, stackindex); printf(n); while(0) void printf_layer_one(int layer, int* stack, int* top) int index ; GENERAL_PRINT_MESSAGE(1); void printf_layer_two(int layer, int* stack, int* top) int index; GENERAL_P

4、RINT_MESSAGE(11); GENERAL_PRINT_MESSAGE(2); 注： a）代碼中我們使用了宏，注意這是一個(gè)dowhile(0)的結(jié)構(gòu)，同時(shí)我們對x進(jìn)行了字符串強(qiáng)轉(zhuǎn) b）當(dāng)剩下臺階為2的時(shí)候，此時(shí)有兩種情形，要么一次跳完；要么分兩次 （4）當(dāng)階梯不為1或者2的時(shí)候，此時(shí)需要遞歸處理cpp HYPERLINK /feixiaoxing/article/details/6871148#view plainHYPERLINK /feixiaoxing/article/details/6871148#copyvoid _jump_ladder(int layer, int* st

5、ack, int* top, int decrease) stack(*top)+ = decrease; jump_ladder(layer, stack, top); stack-(*top) = 0; void jump_ladder(int layer, int* stack, int* top) if(layer = 0) return; if(layer = 1) printf_layer_one(layer, stack, top); return; if(layer = 2) printf_layer_two(layer, stack, top); return; _jump_ladder(layer- 1, stack, top, 1); _jump_ladder(layer- 2, stack, top, 2); 祝：這里在函數(shù)的結(jié)尾添加了一個(gè)函數(shù)，主要是遞歸的時(shí)候需要向堆棧中保存一些數(shù)據(jù)，為了代碼簡練，我們重新定義了一個(gè)函數(shù)?？偨Y(jié)： 1）這道題目和斐波那契數(shù)列十分類似，是一道地地道道的遞歸題目 2）遞歸的函數(shù)也需要好好測試，使用