题目15：在20*20的网格中，从左上角通往右下角的路径一共有多少？
本帖最后由 欧拉计划 于 2023-8-5 23:11 编辑题目15：在20*20的网格中，从左上角通往右下角的路径一共有多少？
Lattice paths
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
How many such routes are there through a 20×20 grid?
题目翻译：
从一个 2×2 网格的左上角开始，只能向右和向下移动，
有 6 条（不允许往回走）通往右下角的路径。
对于 20×20 的网格，这样的路径一共有多少条？
视频讲解：
https://www.bilibili.com/video/BV16h4y1r78j/
思路解析及源码参考（C & Python）：
**** Hidden Message *****
本帖最后由 zhangjinxuan 于 2023-7-18 21:15 编辑
and only being able to move to the right and down
只能向右向下走呗，这个关键的信息居然没有翻译{:10_269:}
那么，这就很简单了{:10_256:}
第 i 行 j 列的路径总数，等于 第 i-1 行 j 列的路径总数 + 第 i 行 j-1 列的路径总数。
第 1 行 1 列的路径总数为 1。
#include <bits/stdc++.h>
using namespace std;
long long f;
const int n = 20;
int main() {
f = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i == 1 && j == 1) continue;
f = f + f;
}
}
printf("%lld\n", f);
return 0;
}
得出答案：35345263800。 本帖最后由 不二如是 于 2023-7-10 07:05 编辑
此答案来自gpt，你们看出错了吧
这是一个组合问题。
从左上角出发,有两条路可以走:(右,下)
每次移动只有两种选择,且每次选择独立。
对于一个m×n的网格,总共有(m+n)!/(m!*n!)条路径。
通过python实现:
from math import factorial
def path(m, n):
return factorial(m + n) / (factorial(m) * factorial(n))
print(path(20, 20))
# 24164578454568703130937340141
详细解释:
[*]factorial() 函数用于计算阶乘。
[*]m+n 表示可以移动的步数,有(m+n)个选择。
[*]m! 和 n! 分别表示排除掉上下移动和左右移动。
因此总共有(m+n)!/(m!*n!)条路径。 不二如是 发表于 2023-7-8 09:44
这是一个组合问题。
从左上角出发,有两条路可以走:(右,下)
每次移动只有两种选择,且每次选择独立。
Chat***？ 不二如是 发表于 2023-7-8 09:44
这是一个组合问题。
从左上角出发,有两条路可以走:(右,下)
每次移动只有两种选择,且每次选择独立。
wq，答案居然不一样{:10_257:} 杨 辉 三 角 zhangjinxuan 发表于 2023-7-9 10:01
杨 辉 三 角
C(40, 20) 小甲鱼 发表于 2023-7-9 23:49
C(40, 20)
{:10_256:} 不二如是 发表于 2023-7-8 09:44
此答案来自gpt，你们看出错了吧
这是一个组合问题。
嗯，是gpt啊，这就不奇怪了，这就不奇怪了{:10_256:}
（zhangjinxuan撤销了一碗饭） 本帖最后由 clollipops 于 2023-7-25 18:25 编辑
C(40, 20) = 137846528820 好好学习
clollipops，哇！那么好的解析 先打个卡现在挑战不了 佬们，递归一下 这个题目有点复杂呀好难呐 慢慢来 137,846,528,820 太有意思了吧，有用有用 一进来感觉进入了太极八卦阵，，，，，可惜我这不好好学习的看不懂。。尴尬 学习学习～
页:
[1]
2