题目15：从20*20的网格的左上角通往右下角有多少条路？

mathtimes

1. #include <cstdio>
   
2. #include <cstdlib>
   
3. #include <iostream>
   
4. using namespace std;
   
5. double nCr(double n,double r)
   
6. {
   
7.     if(n<r)
   
8.     {
   
9.         cerr<<"'n<r'!"<<endl;
   
10.         exit(EXIT_FAILURE);
    
11.     }
    
12.     double ret = 1;
    
13.     while(r>0)
    
14.         ret *= n--/r--;
    
15.     return ret;
    
16. }
    
17. 
    
18. int main()
    
19. {
    
20.     cout<<std::fixed<<nCr(40,20);
    
21. }

复制代码

jerryxjr1220

1. package main
   
2. 
   
3. import (
   
4.         "fmt"
   
5.         "time"
   
6. )
   
7. 
   
8. //题目：
   
9. //
   
10. //从一个 2×2 网格的左上角开始，有 6 条（不允许往回走）通往右下角的路。
    
11. //
    
12. //对于 20×20 的网格，这样的路有多少条？
    
13. 
    
14. func main() {
    
15.         t := time.Now()
    
16.         var i, j int = 0, 0
    
17. 
    
18.         m := make(map[int]map[int]int64)
    
19.         sm := make(map[int]int64)
    
20.         for i = 0; i < 21; i++ {
    
21.                 sm[i] = 1
    
22.         }
    
23.         sm[0] = 0
    
24.         m[0] = sm
    
25. 
    
26.         for i = 1; i < 21; i++ {
    
27.                 sm := make(map[int]int64)
    
28.                 sm[0] = 1
    
29.                 for j = 0; j < 21; j++ {
    
30.                         sm[j+1] = sm[j] + m[i-1][j+1]
    
31.                 }
    
32.                 m[i] = sm
    
33.         }
    
34.         fmt.Println(m[20][20])
    
35.         tt := time.Now()
    
36.         fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
    
37. }
    

复制代码

输出：

1. 137846528820
   
2. 耗时： 0 ms
   

复制代码

B1tetheDust

137846528820.0
It costs 0.000034 s

1. import time as t
   
2. from functools import reduce
   
3. 
   
4. start = t.perf_counter()
   
5. ways = reduce(lambda x, y: x*y, range(1,41))/(reduce(lambda x, y: x*y, range(1, 21)))**2
   
6. 
   
7. print(ways)
   
8. print('It costs %f s' % (t.perf_counter() - start))

复制代码

Asss-whom

1. use std::time::Instant;
   
2. 
   
3. fn main() {
   
4.     let now = Instant::now();
   
5.     let num = c(20);
   
6.     println!("cost {} ms.", now.elapsed().as_millis());
   
7.     println!("{num}")
   
8. }
   
9. 
   
10. fn c(n: u128) -> u128 {
    
11.     let mut value = 1u128;
    
12.     for i in n + 1..2 * n + 1 {
    
13.         value *= i
    
14.     }
    
15.     for i in 1..n + 1 {
    
16.         value /= i
    
17.     }
    
18.     value
    
19. }
    

复制代码

---
cost 0 ms.
137846528820

zhangjinxuan

标数法