【面试题】输出杨辉三角

昨天去面试了让我输出杨辉三角

16年中的时候,自己学了几个月的js,当时就做过这个。

先看看杨辉三角的样子

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

通过上面的例子我们看到,除了第一二排,第三排开始,除去第一个和最后一个,下一排的其他数是上一排的两个数字之和

/**
 * 生成杨辉三角数组
 * @param  int $n 生成几行
 * @return array  生成的杨辉三角数组
 */
function fun ($n) {
    // 定义返回数组
    $ret = [];
    // 如果小于0 返回空数组
    if($n < 0 ) return $ret;
    // 将第一行加入返回数组
    $current = [1];
    $ret[] = $current;
    // 如果只生成一行 直接返回即可
    if($n == 1){
        return $ret;
    }
### 去除开始
// 去除第二行也可以,兼容下面的生成方式
    // 将第二行加入返回数组
    $current = [1,1];
    $ret[] = $current;
    // 如果只生成两行 直接返回即可
    if($n == 2){
        return $ret;
    }
### 去除结束
    // 从第三行开始 遵循以下规律
    for ($i=2; $i < $n; $i++) {
        // 定义下一排的临时数组 $current 代表当前排的数据 $next 代表需要生成的下一排的数据
        // 第一位添加一个 1
        $next = [1];
        foreach ($current as $k => $v) {
            // 如果没用下一位数据 跳过
            if(empty($current[$k + 1])){
                continue;
            }
            // 把当前排的 俩个数据加起来放到下一排中
            $next[] = $v + $current[$k + 1];
        }
        // 在下一排的最后添加 1
        $next[] = 1;
        // 把下一排的数据添加到返回数组,并把下一排设置为当前排
        $ret[] = $current = $next;
    }
    return $ret;
}

生成函数定义好了,下面我们输出试试吧

$arr = fun (10);

foreach ($arr as $v){
	echo implode(' | ', $v), "\n";
}

// 下面是输出结果
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

到此就可以看到 杨辉三角成型了,至于输出的格式,可以根据自己喜好自己调整。

阿杰博客
请先登录后发表评论
  • latest comments
  • 总共1条评论
阿杰博客

温馨????????:其实第二排就已经可以使用下面的规律了。

2019-11-13 17:28:01 回复