直角三角形的路径题

2016-10-11

1. 前言

这个是一个非常常见的编程题目咯，我至少见过这个题目的三种变形考法，大抵都是递归的方法。

2. 题目

存在一个等腰三角形如下

A
*
**
***
****B

如上三角形的边长为N=3，假定小人从A出发向B，并且小人只能向下(输出1)向右(输出0)
那么当N=2时，小人理论上需要走如下路径"[1,1,0,1,0,0],[1,1,1,0,0,0]"(假定小人从A,B点都需要在走一步才能到达)

请问：编程以求出当输入为n时，所有的路径，并输出为以上格式。

3. 解答

题目很简单，我打算使用的是递归的方法，大抵是这样的（代码写的不太好见谅~）：

//currX-当前x位置
//currY-当前y位置
//sum  -当前行总长度
//max  -y方向总长度
//str  -初始化str
function findWay(max,currX,currY,sum,str){
    if(!str) str = "[1";
	if(!currX && typeof currX != "number") currX = 0;
	if(!currY && typeof currY != "number") currY = 0;
	if(!sum && typeof sum != "number") sum = 0;
	if(currX < sum && currY < max) return findWay(max,currX+1,currY,sum,str+",0")+","+findWay(max,currX,currY+1,sum+1,str+",1");
	if(currX < sum && currY == max) return findWay(max,currX+1,currY,sum,str+",0");
	if(currX == sum && currY < max) return findWay(max,currX,currY+1,sum+1,str+",1");
	return str+",0]";
}
findWay(3);

方法写的比较丑见谅/(ㄒoㄒ)/~~ 就这样咯，各位88……

本文标题：直角三角形的路径题

本文链接：https://iceprosurface.com/2016/10/11/2016/2016-10-11-are-recursive-slash-question/index.html

作者授权：除特别说明外，本文由 icepro 原创编译并授权刊载发布。