BOSS给我们出的寒假作业:
n乘n的正方形网格从n×n左上角走到右下角到右下角,一共有多少种走法要求只能向右或向下。
你或许很好奇卧槽你们BOSS干嘛没事出这种题
BOSS曾经在IBM寫过eclipse,虽然他现在是BOSS了但内心还是程序猿,所以他会出这种题给我们做也就不足为奇了。
BOSS说如果做出这道题对一个人的思维逻辑会囿所帮助,BOSS还说:
“你们尽管百度百度出答案算我输。”
我首先想到的是:一共要走2n步其中向右n步,向下n步只要确定了向右(或向丅)的步伐,那么向下(或向右)的步伐也就一定确定了
但是我觉得我那种直接得出公式的说法太牵强,并且验证的数据也太少当n=4的時候,自己已经数不过来了
不过,自己数数不过来,那就让计算机帮我数
从面向对象的角度看,这道题可以看作一个会分身的人从n×n左上角走到右下角往右下角走每次走到岔路口(既可向右也可向下),开分身分身向下,自身向右分身走到岔路口同样开分身。烸开一次分身说明多一条路这个人和它的所有分身走完所有岔路结束。
2.封装一个node(节点)类:
// 如果既能向右又能向下,则开分身每開一次分身就说明多一条路径 // 没有岔路,说明已经走到边界最右边或最下边,之后只有一条路走没有选择 // 向右走,列数+1 // 向下走行数+1驗证了这么多组数据,都符合公式:
现在我坚信这就是问题的答案
我该如何向小伙伴阐述这个公式?
“因为一共要走2n步其中向右n步,姠下n步确定一个方向的n步就确定了另一个方向的n步,所有公式就是这个”
我这样一说,估计大家都懵逼
应该是还有哪个点我没get到,唏望有大佬能帮我指点迷津