走台阶OR台阶走—《狂人C》习题解答14(第三章习题4)

题目：

4. 有一段楼梯有6级台阶,规定每一步只能跨一级或两级,要登上第6级台阶有几种不同的走法?

     这个题目从数学角度来看可能有一点难度，但一经点破也就没什么难度了。
     首先第1级台阶只有一种走法。第2级台阶有两种走法，因为可以直接跨上，也可以从第1级跨上。
     换句话说，由于登上第2级台阶可以从第0阶（最初的状态）也可以从第1阶登上，所以
          登上第2级台阶的走法的数目 = 登上第0级台阶的走法的数目 + 登上第1级台阶的走法的数目
其中登上第0级台阶的走法的数目显然为1种。 
     这个道理就如同到某地有三条陆路两条水路，那么到该地一共有五条路一样。
     后面各阶走法的数目的求法和第2阶的求法类似。
     描述这个求解过程的代码为：

#include <stdio.h>
#include <stdlib.h>

int main( void )
{
  int num_of_step0 = 1 , num_of_step1 = 1 , num_of_step2 , ,
      num_of_step3 , num_of_step4 , num_of_step5 , num_of_step6;

  num_of_step2 = num_of_step1 + num_of_step0 ;
  num_of_step3 = num_of_step2 + num_of_step1 ;
  num_of_step4 = num_of_step3 + num_of_step2 ;
  num_of_step5 = num_of_step4 + num_of_step3 ;
  num_of_step6 = num_of_step5 + num_of_step4 ;

  printf("登上第6级台阶有%d种不同的走法\n" , num_of_step6 );

  system("PAUSE");
  return 0;
}

     这种写法的缺点是变量太多，如果阶数更多，就需要定义更多的变量。那样的话即使不把人累死也会把人给笨死。
     因为这种方法仿佛是自己从第2阶走到第6阶，如果走的阶数很多，那确实很累人。
     实际上，走台阶是从人的主观出发的一种想法，这种情况关心有多少级台阶是很自然的想法；但是如果换一种情境，稍微发挥一点想象力的话，不难发现如果人不动让台阶反方向"走"，问题的本质是一样的。这时你不会关心一共有多少级台阶，你只会也只需要关心后面的两级台阶和当前面对的台阶。也就是 
          登上当前台阶走法的数目 = 登上后面第1级台阶走法的数目 + 登上后面第2级台阶走法的数目
     不难看出，这是一种基于"相对"的思考方法和描述方法，而前面那种写法则是基于"绝对"的思考方法和描述方法。
     台阶反方向"走"一步之后，状态就变了。后面第1级台阶变成了后面第2级台阶，可以描述为 
          登上后面第2级台阶走法的数目 = 登上后面第1级台阶走法的数目
     而当前面对的台阶则变成了后面第1级台阶，因而
          登上后面第1级台阶走法的数目=当前台阶走法的数目
     现在你会发现你要解决的是和刚才完全一样的问题。后面的代码可以如法炮制。 
     反复解决同样的问题是令人愉快的，这样的代码好写也不容易错，只要认真把第一次写对，然后复制粘贴就可以了。 代码为：

#include <stdio.h>
#include <stdlib.h>

int main( void )
{
  int num_of_current_step , //当前面对台阶走法数目
      num_of_passed_step1 , //后面第1级台阶走法数目
      num_of_passed_step2 ; //后面第2级台阶走法数目

  //在第0阶时
  num_of_current_step = 1 ; //根据分析

  //在第1阶时
  num_of_passed_step1 = num_of_current_step ; //当前退后1阶
  num_of_current_step = 1 ; //根据分析

  //在第2阶时
  num_of_passed_step2 = num_of_passed_step1 ; //退后1阶
  num_of_passed_step1 = num_of_current_step ; //退后1阶
  num_of_current_step = num_of_passed_step1
                      + num_of_passed_step2 ; //当前等于后面两阶之和

  //在第3阶时 。从这里开始可以复制粘贴了
  num_of_passed_step2 = num_of_passed_step1 ; //退后1阶
  num_of_passed_step1 = num_of_current_step ; //退后1阶
  num_of_current_step = num_of_passed_step1
                      + num_of_passed_step2 ; //当前等于后面两阶之和

  //在第4阶时
  num_of_passed_step2 = num_of_passed_step1 ; //退后1阶
  num_of_passed_step1 = num_of_current_step ; //退后1阶
  num_of_current_step = num_of_passed_step1
                      + num_of_passed_step2 ; //当前等于后面两阶之和

  //在第5阶时
  num_of_passed_step2 = num_of_passed_step1 ; //退后1阶
  num_of_passed_step1 = num_of_current_step ; //退后1阶
  num_of_current_step = num_of_passed_step1
                      + num_of_passed_step2 ; //当前等于后面两阶之和
  //在第6阶时
  num_of_passed_step2 = num_of_passed_step1 ; //退后1阶
  num_of_passed_step1 = num_of_current_step ; //退后1阶
  num_of_current_step = num_of_passed_step1
                      + num_of_passed_step2 ; //当前等于后面两阶之和

  printf("登上第6级台阶有%d种不同的走法\n" , num_of_current_step );

  system("PAUSE");
  return 0;
}

     这种写法无疑更加简单也更强大，因为变量少，而且很容易扩展为解决其他阶数同样的问题。更主要的是后面几段代码可以通过复制粘贴不做任何修改简单地完成。
     可能有人觉得第2种写法代码太长，这个问题在后面学习了循环控制语句之后很容易解决。代码的结构简单是更重要的。第2段代码由于是在反复做同样的事（这恰恰是计算机的长处），所以结构是简单的。而第一段代码，复制粘贴后由于需要修改变量名，从某种意义上来说，结构在不断变化，因而是复杂的。况且修改变量名很容易发生错误，这也可以视为更加复杂。 
     只要有可能，尽量写简单的代码是编程的一项基本原则，这就是所谓的KISS原则——Keep It Simple Stupid。
     然而我们从前面不难看到，写出简单不易错的代码往往是需要多动一些脑筋的，而复杂容易错的代码则往往是不加思索一蹴而就的产物。
     有句名言：把事情变简单很复杂，把事情变复杂很简单。
     这话我们似乎同样可以理解为写代码是简单的，但在写代码之前的思考则是复杂的。
     对于高手来说，一旦开始写代码，那就往往意味着代码即将完成。看似简单轻松完成的东西，其实写之前在心里不知布局谋划苦心经营了多久。 
     初学者往往一拿到题目就立刻开始写代码，这是很不好的编程习惯，绝对不会写出优秀的代码。