当前位置:编程学习 > 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){

     

补充:软件开发 , C语言 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,