打印杨辉三角--编程算法系列之一

2016-07-17

前言

算法是程序员从职业开始到职业结束，估计都是绕不开的话题。所有大公司技术面试都会考算法题，不管国内国外。我一直想非得这样算法吗，没有别的更好的考察方式吗？有没有算法不行但是写程序很厉害的人？我没有答案。也许算法确实比较好的考察方法，如果你确实是个聪明人，你应该克服算法不行的问题。运用算法解决某些问题，或者编写程序去实现某个算法，对程序员是一个重要的能力。所以我要锻炼自己拥有这个能力。我准备将我以前遇到的一些面试题目，真正的完全靠自己去实现，并记录下来。

杨辉三角

如果你听说过杨辉三角，但是又不记得具体是什么规格，那你跟当年的我一样。大概一两年前，X公司某个项目招人，他们的HR找到我让我去试试，当时我想试试也无妨。前面的一，二技术面试都没太多问题，他们问的都是工作中的技术，后来有一面只面了我纯算法问题，就是打印杨辉三角，我一下懵了，结果是死得很难看。先看看杨辉三角的数字排列是怎样的：

　                         1
                         1   1   
                       1   2   1   
                     1   3   3   1   
                   1   4   6   4   1   
                 1   5   10  10  5   1   
               1   6   15  20  15  6   1   
             1   7   21  35  35  21  7   1   
           1   8   28  56  70  56  28  8   1   
         1   9   36  84  126 126 84  36  9   1   
       1   10  45  120 210 252 210 120 45  10  1   
     1   11  55  165 330 462 462 330 165 55  11  1    
   1   12  66  220 495 792 924 792 495 220 66  12  1

面试时我很容易紧张，人在紧张情况下貌似是很难转起来的，这是我的一大弊端。当时面试官只在纸上画了前5行，只告诉了我杨辉三角的特点就是每个数字都是它左上角的那个数字和右上角的那个数字相加得来，第一个数字是1。我当时只得出运用递归算法来解这道题会比较容易理解。但是该怎么写我写不出来。后来很长一段时间我并没有忘记这道题，但是我没有去查怎么解决，我偶尔会想一下该怎么做。最近这一两周我对解决这个到题的欲望越来越强烈，所以我开始在记事本上动手写代码解决。后来我发现了杨辉三角的一些规律，这些规律帮助我将代码写了出来。

1.杨辉三角第n行有n个数字
2.每个数字都是它左上角的那个数字和右上角的那个数字相加得来，更具体一点这个数字是a(i,j),那么它是a(i-1,j-1)和a(i-1, j)相加得来的
3.第1个数字是1.如果这个数字的左上角或右上角的那个数字不存在，那么就当做0

我的分析过程

说实话，现在看起来这些规律显而易见，但是我还是在编写代码的过程中带才找到的。
我这个人在面试中真的无法做到像平时那样思考，这让我在面试中感觉自己是个无思考能力的人。还有我发现自己一定要先进入编程状态才能进行思考。所以我决定要解决这个问题时，我就打开一文本，开始写一些我已经想到的代码，直到现在，这个文本也还没有关闭过。

第3点很浅显，它是基础，如果用递归实现的话这是递归的出口。第1点让我写出了两个for循环，但是循环体内是怎么实现，我纠结了很久。最开始我想用最简单的方法，把已计算出的数字放入一个数组，然后就把数组中的数字相加得出所需数字。但是我发现这个数组也不太用，我不想用二维数组。后来我才想清楚，直接在循环体内用一个递归函数就这个数字的值，然后把它打印出来，这个是行得通的。然后关键是这个递归函数怎么实现。

一开始我把递归函数的参数设为n，发现怎么实现都不太对，后来发现其实应该是把参数设置为i,j，这样就跟循环体的下标对应起来，就很好解决了。最终要解决的就是递归的出口问题，这个也不是我一开始想的那么简单。我把下标设置成是以1开始的，i<1的话，它的值就是0，1的话就是1. 而对应j,为1的话，它是0，而且j是不能大于i的，大于i它的值也为0。所以程序的最终实现是：

代码实现

\#include <stdio.h>

int yangHuiTriangle(int i, int j) {
    int a, b;
    if (i<1) a = 0;
    else if (i == 1) a = 1;
    else {
        a = yangHuiTriangle(i-1, j-1);
    }
    if ( j<=1) b = 0;
    else if (j>i) a = 0;
    else b = yangHuiTriangle(i-1, j);
    return a+b;
}

void pringYangHuiTriangle(int n) {
    for (int i=1; i<=n; i++) {
        for(int j=1; j<=i; j++) {
            int r = yangHuiTriangle(i,j);
            printf("%d   ", r);
        }
        printf("\n");
    }
}

当我第一次写完代码时，并没有完全写对，j>i的情况没有处理好。我自己对照着杨辉三角的数字来检验的时候，发现了问题，然后改了过来，然后我就把代码拷贝到一个工程里运行，结果出来了，是对的！

打印结果

1   
1   1   
1   2   1   
1   3   3   1   
1   4   6   4   1   
1   5   10   10   5   1   
1   6   15   20   15   6   1   
1   7   21   35   35   21   7   1   
1   8   28   56   70   56   28   8   1   
1   9   36   84   126   126   84   36   9   1   
1   10   45   120   210   252   210   120   45   10   1   
1   11   55   165   330   462   462   330   165   55   11   1   
1   12   66   220   495   792   924   792   495   220   66   12   1

虽然这个打印出来的结果不是金字塔形状，但是它的数字都是对的。对于打印成金字塔形状，以后再研究吧。

Category: 算法 Tagged: 算法杨辉三角

2016-07-17

前言

杨辉三角

我的分析过程

代码实现

打印结果

Comments