Euler Project 挨个做 - 之一(Q1-50)

tree_new_bee

看完上贴的分析， 其实已经能够用纯数学方法人肉计算出来了。

对于示例图， 我们可以把可以把6种方案描述为： 11, 12, 13, 22, 23, 33

可以看出， 这实际上就是从3个数中允许重复的情况下取2个数的组合。 (如果允许路径回溯， 就成为3个数中允许重复的情况下取2个数的排列)

对于n*n的grid,就是 从n+1个数中允许重复的情况下取n个数的组合. H(n+1, n) = C(n+1+n-1, n)
n=20时， 即是H(21, 20) = C(20+21-1,20) = C(40,20) =  137846528820

[ 本帖最后由 tree_new_bee 于 2010-12-16 13:23 编辑 ]

〇〇

原帖由 tree_new_bee 于 2010-12-16 13:21 发表
看完上贴的分析， 其实已经能够用纯数学方法人肉计算出来了。

对于示例图， 我们可以把可以把6种方案描述为： 11, 12, 13, 22, 23, 33

可以看出， 这实际上就是从3个数中允许重复的情况下取2个数的组合。 (如果允许路径回溯， 就成为3个数中允许重复的情况下取2个数的排列)

对于n*n的grid,就是 从n+1个数中允许重复的情况下取n个数的组合. H(n+1, n) = C(n+1+n-1, n)
n=20时， 即是H(21, 20) = C(20+21-1,20) = C(40,20) =  137846528820

不是从1~6个横线 从取2个吗，怎么是3个数中取2个

〇〇

原帖由 〇〇 于 2010-12-16 14:46 发表

不是从1~6个横线700198从取2个吗，怎么是3个数中取2个

知道了，是从1-3层中取2个

tree_new_bee

原帖由 〇〇 于 2010-12-16 14:59 发表

知道了，是从1-3层中取2个

虽说有了人肉算法。
我还是想要用算法来真正有效率的实现， 不过似乎太难了。 需要继续探索。

tree_new_bee

回答答案以后，看该题目的帖子， 发现有另一种方法也能得到C(40,20)的结果：
把向右表示为0， 向下表示为1， 那么所有可能路径就是：
0000000000000000000011111111111111111111
1111111111111111111100000000000000000000
这些之间的给中组合。 因为0和1的数目相等，无论从0还是从1来看， 都是从40个位置中找20个位置放置这个数字。
这样可能的摆放方法有：C(40,20)种。



另外一个发现，也比较有意思， 就是观察Pascal三角：
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

就是说，n*n的路径数等于pascal三角中第2n层的中间那个数， 或者说是第n个有奇数个数的层的中间那个数。
这之间为什么有这种关系， 先不明白。

〇〇

可以用作科学院的公务员考题

tree_new_bee

看这个图就明白那个pascal三角的道理了。

从右下角开始， 右下角到终点的路径数为0
右边和下边的点到终点的路径都是1条。在这些点上标上1(左图)


其它点的路径数，则是右侧和下侧邻居的路径数目和(右图)



这样，左上角的数字正好是pascal三角偶数行的中间数。

用这个算法， 也许能快速做出解答了。

tree_new_bee

上面这个思路，很适合用model语句来做。
正好拿来练练手。

with t as (select rownum n from dual connect by rownum<=21)
,t1 as ( SELECT r,c,s
  FROM t t1,t t2
MODEL
    DIMENSION BY (t1.n r, t2.n c)
    MEASURES (0 s)
    RULES update
    (
      s[any,1]=1, s[1,any]=1,s[1,1] = 0
     ,s[any, any] = case when cv(r)>1 and cv(c)>1 then  s[cv(r)-1,cv(c)] + s[cv(r), cv(c)-1] else s[cv(r),cv(c)] end
) )
select r-1, c-1, s from t1 where r=c and r>1

       R-1        C-1          S
---------- ---------- ----------
         1          1          2
         2          2          6
         3          3         20
         4          4         70
         5          5        252
         6          6        924
         7          7       3432
         8          8      12870
         9          9      48620
        10         10     184756
        11         11     705432
        12         12    2704156
        13         13   10400600
        14         14   40116600
        15         15  155117520
        16         16  601080390
        17         17 2333606220
        18         18 9075135300
        19         19 3534526380
        20         20 1378465288

20 rows selected

Executed in 0.172 seconds


OK! 至此，这个问题算是完满了。

〇〇

完满

tree_new_bee

刚知道强大的Google，强大到多么邪恶的地步。
Google计算器： http://www.google.com/search?q=40+choose+20

40 choose 20 = 137 846 528 820


可惜不知道它都能识别哪些函数或者公式。

试了一些，似乎能想到的都有了：        
cos pi  : cos(pi) = -1
tan pi:   tan(pi) = 0
2^10 = 1 024
10 ! = 3 628 800
sqrt 16:  sqrt(16) = 4
ln e :ln(e) = 1
还有复数：  i^2 = -1

[ 本帖最后由 tree_new_bee 于 2010-12-16 18:15 编辑 ]