n乘n的正方形网格，从左上角到右下角一共有多少种走法？
2019-02-10 本文已影响319人
Lol刀妹
背景
BOSS给我们出的寒假作业：
n乘n的正方形网格，从左上角到右下角，一共有多少种走法？要求只能向右或向下。
你或许很好奇卧槽你们BOSS干嘛没事出这种题？
BOSS曾经在IBM写过eclipse，虽然他现在是BOSS了，但内心还是程序猿，所以他会出这种题给我们做，也就不足为奇了。
BOSS说如果做出这道题，对一个人的思维逻辑会有所帮助，BOSS还说：
“你们尽管百度，百度出答案算我输。”
我的思路
我首先想到的是：一共要走2n步，其中向右n步，向下n步，只要确定了向右（或向下）的步伐，那么向下（或向右）的步伐也就一定确定了。
所以结果是：
然后验证了一下：
- n=1,s=2;
- n=2,s=6;
- n=3,s=20
好像真的是这回事。
但是我觉得我那种直接得出公式的说法太牵强，并且验证的数据也太少，当n=4的时候，自己已经数不过来了。
不过，自己数，数不过来，那就让计算机帮我数。
从面向对象的角度看，这道题可以看作一个会分身的人从左上角往右下角走，每次走到岔路口（既可向右也可向下），开分身，分身向下，自身向右，分身走到岔路口同样开分身。每开一次分身说明多一条路。这个人和它的所有分身走完所有岔路结束。
程序设计思路
1.封装一个person类：
@interface Person : NSObject
// 当前所处的节点
@property (nonatomic, strong) Node *currentNode;
// 开分身
- (Person *)divide;
- (void)go;
@end
2.封装一个node（节点）类：
@interface Node : NSObject
// 行
@property (nonatomic, assign) NSInteger row;
// 最大行数
@property (nonatomic, assign) NSInteger maxRow;
// 列
@property (nonatomic, assign) NSInteger col;
// 最大列数
@property (nonatomic, assign) NSInteger maxCol;
// 有向右的分支
@property (nonatomic, assign) BOOL hasRightBranch;
// 有向下的分支
@property (nonatomic, assign) BOOL hasDownBranch;
@end
核心代码
- (void)go {
if ([self.currentNode hasRightBranch] && [self.currentNode hasDownBranch]) {
// 如果既能向右，又能向下，则开分身，每开一次分身就说明多一条路径
Person *shadow = [self divide];
// 路径数+1
[[CountManager sharedManager] add];
[shadow goDown]; // 分身向下
[shadow go]; // 递归，接着走
[self goRight]; // 自身向右
[self go]; // 递归，接着走
} else {
// 没有岔路，说明已经走到边界，最右边或最下边，之后只有一条路走，没有选择
}
}
- (void)goRight {
// 向右走，列数+1
self.currentNode.col ++;
}
- (void)goDown {
// 向下走，行数+1
self.currentNode.row ++;
}
验证
- n=1,s=2;
- n=2,s=6;
- n=3,s=20;
- n=4,s=70;
- n=5,s=252;
- n=6,s=924;
- n=7,s=3432
验证了这么多组数据，都符合公式：
现在我坚信这就是问题的答案。
但是问题来了
我该如何向小伙伴阐述这个公式？
“因为一共要走2n步，其中向右n步，向下n步，确定一个方向的n步就确定了另一个方向的n步，所有公式就是这个。”
我这样一说，估计大家都懵逼。
我也懵逼。
应该是还有哪个点我没get到，希望有大佬能帮我指点迷津。
