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

mathtimes

#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
double nCr(double n,double r)
{
    if(n<r)
    {
        cerr<<"'n<r'!"<<endl;
        exit(EXIT_FAILURE);
    }
    double ret = 1;
    while(r>0)
        ret *= n--/r--;
    return ret;
}

int main()
{
    cout<<std::fixed<<nCr(40,20);
}

jerryxjr1220

package main

import (
        "fmt"
        "time"
)

//题目：
//
//从一个 2×2 网格的左上角开始，有 6 条（不允许往回走）通往右下角的路。
//
//对于 20×20 的网格，这样的路有多少条？

func main() {
        t := time.Now()
        var i, j int = 0, 0

        m := make(map[int]map[int]int64)
        sm := make(map[int]int64)
        for i = 0; i < 21; i++ {
                sm[i] = 1
        }
        sm[0] = 0
        m[0] = sm

        for i = 1; i < 21; i++ {
                sm := make(map[int]int64)
                sm[0] = 1
                for j = 0; j < 21; j++ {
                        sm[j+1] = sm[j] + m[i-1][j+1]
                }
                m[i] = sm
        }
        fmt.Println(m[20][20])
        tt := time.Now()
        fmt.Println("耗时：", (tt.Nanosecond()-t.Nanosecond())/1e6, "ms")
}

输出：

137846528820
耗时： 0 ms 

B1tetheDust

137846528820.0
It costs 0.000034 s

import time as t
from functools import reduce

start = t.perf_counter()
ways = reduce(lambda x, y: x*y, range(1,41))/(reduce(lambda x, y: x*y, range(1, 21)))**2

print(ways)
print('It costs %f s' % (t.perf_counter() - start))

Asss-whom

use std::time::Instant;

fn main() {
    let now = Instant::now();
    let num = c(20);
    println!("cost {} ms.", now.elapsed().as_millis());
    println!("{num}")
}

fn c(n: u128) -> u128 {
    let mut value = 1u128;
    for i in n + 1..2 * n + 1 {
        value *= i
    }
    for i in 1..n + 1 {
        value /= i
    }
    value
}

---
cost 0 ms.
137846528820

zhangjinxuan

标数法