最新消息:

城市网格与帕斯卡三角及java打印杨辉三角

算法 大步 1085浏览 0评论
问题:
对于一个nxn的正方形,以最左上角的为起点,则从该起点到达正方形中任意一点的最短路径有多少种?注意:每条边走过之后就不能再走了,且每一步只能往右或者往下走。
举例,对于2x2的正方形,从最左上角到最右下角的所有可能路径有6条,如下:
0.8104784479364753
分析:
假设启动点坐标是(0,0),则到点(2,2)。假设往右走是R,往下走是D,则所有的组合是:
RDDR, RRDD, RDRD, DRDR, DDRR, DRRD。
可见,无论怎么走,都要走4步,而且必须有两步是往右走(即组合中必出现两个R)。所以,就等于组合,即253799953
注意:排列组合公式为:
254690015
所以,对于NxN的正方形,到达最右下角的路径总共有253954171
同时,我们进一步分析,就会发现,不仅仅是到达最又下角,到达正方形中任意一点,它的所有路径的总步数是固定的,而且R出现的次数也是固定的。假设要从(0,0)到达(i,j),则所有路径的总步数是 i+j , R(往右走的步数)是j。所以,总的路径数是254168062
我们可以将帕斯卡三角放到正方形的方格中,如下,一个3x3的正方形:
pascalstriangle
我们就会发现一个规律,那就是每一点的值,就是从点(0,0)到该点的所有最短路径的条数
从帕斯卡三角形的顶点到任意一行的每一点的总的步数是相同的,且往右的步数(R出现的次数)也是固定的
这样,我们就可以得到帕斯卡三角的每个元素的值与它的位置之间的关系,如下:
假设元素是第r行,第k个元素。则该元素的值,就是:
254565328
例如:
87b05bc18852b533a4ee0914ee6f8039_38942062.png
刚开始想到的是将上面一行元素保存起来,共下一行使用。但是这种太占空间了。于是,就想是否能够得到前后两个元素之间的关系。这样就不用占空间。
见wiki:https://en.wikipedia.org/wiki/Pascal's_triangle
每个元素的值相当于组合公式:

C(n, k) 表示的是第n+1行的第k+1个元素的值
但是因为里面有阶乘,所以还是太复杂。我们通过这个公式,推导出前一个元素与后一个元素之间的关系:
C(n,k-1) =  C(n,k)*Fun。
根据上面的公式,推导可知:

于是,该算法的复杂度是O(n2),java代码如下(格式的关键在于print函数的格式化):
参考:

 

来自为知笔记(Wiz)

 

转载请注明:大步's Blog » 城市网格与帕斯卡三角及java打印杨辉三角

SiteMap