简单算法，求解，不懂算法为何！

灵夕920329 发布于 2012-12-22 18:41， 523 次点击

問題描述：

有下面一個這樣的圖形，我們從原點 (0,0) 出發，每次移動只能往上、往右、往右上三種方向其中一種前進。我們可以人工的方式算出走到 (1,1) 有 2 種走法、 (2,2) 有 6 種走法。

只有本站会员才能查看附件，请登录

現在要你寫一個程式，計算從 (0,0) 走到 (n,n)，(1 <= n <= 15) ，共有幾種走法。
以下是正确答案：
输入输出
1    2
2    6
3    22
4    90
5    394
6    1806
7    8558
8    41586
9    206098
10   1037718
11   5293446
12   27297738
13   142078746
14   745387038
15   3937603038

5 回复

azzbcc2012-12-22 18:53

明显数学题有规律的。

(m, n) = (m, n - 1) + (m - 1, n - 1) + (m - 1, n - 1);

灵夕9203292012-12-22 19:54

回复 2楼 azzbcc

什么意思？这个哪看得懂啊？怎么用矩阵表示？能不能帮忙给个程式码？

azzbcc2012-12-22 20:44

。。。。。。。

每个点的路径值等于其左、左下、下(不存在记0)三点路径值之和，由此可以用递归或递推.

灵夕9203292012-12-23 02:20

回复 4楼 azzbcc

我知道用递归，只是数目一大了，我就烦混了，该怎么写就忘了

azzbcc2012-12-23 02:36

这个其实蛮简单，定义一个返回某点路径值的函数 int fun(int x, int y)
就两个限定条件：

1.x <= y 此时应该返回 0

2.x, y >= 0 只需讨论y >= 0 因为 x是大于y的，此时返回 1（底边全为 1）;

把这两个做递归结束条件。

然后直接返回左、左下、下三点之和就行了

只是提供一个思路，还有不少问题：

1.数据结果超int范围； 2.每次递归的最终点都是(0, 0)，只是求一组解还好，依次罗列就会有很多次重复计算

应该还有其他问题吧。。。