用VBA解欧拉计划题目（15）

grf1973

第15题，有点意思了。
结果是：137846528820

香川群子

数量少的话，用递归函数很简单。

1. Sub test()
   
2.     MsgBox f(10, 10)
   
3. End Sub
   
4. Function f&(x&, y&) 'Gride Route Count / Right or Down
   
5.     If x = 0 Then f = 1 Else If y = 0 Then f = 1 Else f = f(x - 1, y) + f(x, y - 1)
   
6. End Function
   

复制代码

但是x、y>10的话计算就很慢了（递归的效率太低）

所以数量多的话，还是需要数组循环计算吧。

grf1973

我好象试过。20*20递归就卡死了。

香川群子

数组循环也很简单，且计算效率最高。

1. Sub test1()
   
2.     x = 20
   
3.     y = 20
   
4.     ReDim a(x, y)
   
5.     For j = 1 To y
   
6.         a(0, j) = 1
   
7.     Next
   
8.     For i = 1 To x
   
9.         a(i, 0) = 1
   
10.     Next
    
11.    
    
12.     For i = 1 To x
    
13.         For j = 1 To y
    
14.             a(i, j) = a(i - 1, j) + a(i, j - 1)
    
15.         Next
    
16.     Next
    
17.     MsgBox a(x, y)
    
18. End Sub

复制代码

grf1973

1. Sub problem15()   '20*20的格子，左上走到右向有多少种可能（每次只能向下or向右）  '结果：137846528820
   
2. ' 思路：20*20的方格中，从左上角到右下角，不论怎么走，都只需要40步
   
3. '其中必然有20步时横着走，20步时竖着走。
   
4. '所以这个问题变成了从40步中取出20步一共有多少种方法？用排列组合C（20上）（40下）
   
5.     s = 阶乘(40) / 阶乘(20) / 阶乘(20)
   
6.     Debug.Print s
   
7. End Sub
   
8. ''''''''另一种思路：每一交点的方法=左一交点的方法+上一交点的方法，记为f(a,b)=f(a-1,b)+f(a,b-1)，f(20,20)即为结果
   
9. Sub problem15a()
   
10.     Dim f(20, 20): f(1, 1) = 1
    
11.     For a = 0 To UBound(f)
    
12.         For b = 0 To UBound(f)
    
13.             If a * b = 0 Then
    
14.                 f(a, b) = 1
    
15.             Else
    
16.                 f(a, b) = f(a - 1, b) + f(a, b - 1)
    
17.             End If
    
18.         Next
    
19.     Next
    
20.     Debug.Print f(20, 20)
    
21. End Sub
    

复制代码

grf1973

后来发现排列组合的展开就是f(a,b)=f(a-1,b)+f(a,b-1)

大灰狼1976

仔细思考一下就可以发现，20*20的格子，从左上角到右下角，不管怎么走，都是平移20次，纵移20次，
那么，就计算一下总移动步数40里面，20次平移（或纵移，都一样，反正每一步不是平移就是纵移）的分布情况就明白了，也就是40中取20的处理，excel有个函数combin直接可以给出结果：combin(40,20)=137846528820

grf1973

大灰狼1976 发表于 2017-12-14 12:42
仔细思考一下就可以发现，20*20的格子，从左上角到右下角，不管怎么走，都是平移20次，纵移20次，
那么， ...

嗯，这是最自然的想法。