程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一步一步寫算法(之爬樓梯)

一步一步寫算法(之爬樓梯)

編輯:關於C語言

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

    前兩天上網的時候看到一個特別有意思的題目,在這裡和朋友們分享一下:

 

    有一個人准備開始爬樓梯,假設樓梯有n個,這個人只允許一次爬一個樓梯或者一次爬兩個樓梯,請問有多少種爬法?

 

    在揭曉答案之前,朋友們可以自己先考慮一下:

 

    這個人爬n層樓梯,那麼它也不是一下子就可以爬這麼高的,他只有兩個選擇,要麼從n-2層爬過來,要麼從n-1層爬過來。除此之外,他沒有別的選擇。此時相信朋友其實已經早看出來了,這就是一道基本的遞歸題目。

 

    (1)首先我們建立一個函數,判斷函數的合法性

 

 

void jump_ladder(int layer, int* stack, int* top) 

    if(layer <= 0) 

        return; 

 

    return; 

void jump_ladder(int layer, int* stack, int* top)

{

       if(layer <= 0)

              return;

 

       return;

}

    (2)判斷當前的層數是為1或者是否為2

 

 

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; 

    } 

 

    return; 

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;

       }

 

       return;

}    (3)對於2中提及的打印函數進行設計,代碼補全

 

 

#define GENERAL_PRINT_MESSAGE(x)\  

    do {\ 

        printf(#x);\ 

        for(index = (*top) - 1 ; index >= 0; index --)\ 

            printf("%d", stack[index]);\ 

        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_PRINT_MESSAGE(11); 

    GENERAL_PRINT_MESSAGE(2); 

#define GENERAL_PRINT_MESSAGE(x)\

    do {\

        printf(#x);\

        for(index = (*top) - 1 ; index >= 0; index --)\

            printf("%d", stack[index]);\

           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_PRINT_MESSAGE(11);

       GENERAL_PRINT_MESSAGE(2);

}    注:a)代碼中我們使用了宏,注意這是一個do{}while(0)的結構,同時我們對x進行了字符串強轉

 

             b)當剩下台階為2的時候,此時有兩種情形,要麼一次跳完;要麼分兩次

 

 

 

 

    (4)當階梯不為1或者2的時候,此時需要遞歸處理

 

 

void _jump_ladder(int layer, int* stack, 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); 

void _jump_ladder(int layer, int* stack, 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);

}

    祝:這裡在函數的結尾添加了一個函數,主要是遞歸的時候需要向堆棧中保存一些數據,為了代碼簡練,我們重新定義了一個函數。

 

 

 

 

總結:

 

    1)這道題目和斐波那契數列十分類似,是一道地地道道的遞歸題目

 

    2)遞歸的函數也需要好好測試,使用不當,極容易堆棧溢出或者死循環。對此,我們可以按照參數從小到大的順序依次測試,比如說,可以測試樓梯為1、2、3的時候應該怎麼運行,同時手算和程序相結合,不斷修正代碼,完善代碼。

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved