矩阵求解问题(数据结构)

4546 发布于 2016/06/19 18:19
阅读 240
收藏 0
[1,2,3
4,5,6,
7,8,9
]
求从[0][0]开始到[2][2]结束的所有可能的解
例如1+2+3+6+9这样算一个解,每次只能往下走或者向又走,求所有可能的解= =

以下是问题补充:

@4546:其实是n*n的矩阵,对矩阵进行遍历,每次只能向右或者向下走,走到[n-1][n-1]为一次遍历结果,求在所有遍历过程中的最大和,用递归思想要如何做,我找不到判断递归结束的点 (2016/06/19 23:46)
加载中
1
O油菜
O油菜
用bfs或者dfs搜索都可以……

这个不叫矩阵求解。

4
4546
不过可能是我的解释有问题
4
4546
我试试,谢谢
0
百世经纶之傲笑红尘
百世经纶之傲笑红尘

矩阵你学过吗?知道它和方程的区别吗

1x+2y=3z

4x+5y=6z

7x+8y=9z

1  2  3

4  5  6

7  8  9

解出x,y,z=0

编程中的数学思想的运用

O油菜
O油菜
回复 @百世经纶之傲笑红尘 : 没有画竖线的矩阵不是方程是三个表达式。把你写的等号全改成加号。
百世经纶之傲笑红尘
百世经纶之傲笑红尘
回复 @O油菜 : 那敢问阁下有什么高见??? 参考百度百科: http://baike.baidu.com/link?url=ahxUPf8aAuRvF_eDxmza0K1LnHlLvCuapVdlwiPatWzeT_ryOdfHsmBnhmplOO1BRgokqcSTcdHtf9Xe60Pw5akkGRI_-pZHxabrIOcQ0BC
O油菜
O油菜
吓尿了。楼主名词用错也就算了,谁教你矩阵和方程这个关系的的?
0
jolphin
jolphin

来一个SQL版本的with递归查询:

WITH temp AS (
SELECT ROWNUM rn, MOD(ROWNUM-1,3)+1 x, CEIL(ROWNUM/3) y 
FROM dual CONNECT BY ROWNUM <= 9
)
,board(x,y,amount,path,lv) AS (
SELECT x, y, rn, to_char(rn), 1 FROM temp WHERE x = 1 AND y = 1 
UNION ALL
SELECT t.x, t.y, b.amount+t.rn, b.path||' + '||t.rn, b.lv+1
FROM board b, temp t 
WHERE b.lv < 9
  AND INSTR(b.path,t.rn) = 0 
  AND (b.y = t.y AND t.x-b.x = 1
    OR b.x = t.x AND t.y-b.y = 1)
)
SELECT * FROM board WHERE x = 3 AND y = 3;
结果:
21 = 1 + 2 + 3 + 6 + 9
23 = 1 + 2 + 5 + 6 + 9
25 = 1 + 2 + 5 + 8 + 9
25 = 1 + 4 + 5 + 6 + 9
27 = 1 + 4 + 5 + 8 + 9

29 = 1 + 4 + 7 + 8 + 9

0
4
4546

引用来自“jolphin”的评论

来一个SQL版本的with递归查询:

WITH temp AS (
SELECT ROWNUM rn, MOD(ROWNUM-1,3)+1 x, CEIL(ROWNUM/3) y 
FROM dual CONNECT BY ROWNUM <= 9
)
,board(x,y,amount,path,lv) AS (
SELECT x, y, rn, to_char(rn), 1 FROM temp WHERE x = 1 AND y = 1 
UNION ALL
SELECT t.x, t.y, b.amount+t.rn, b.path||' + '||t.rn, b.lv+1
FROM board b, temp t 
WHERE b.lv < 9
  AND INSTR(b.path,t.rn) = 0 
  AND (b.y = t.y AND t.x-b.x = 1
    OR b.x = t.x AND t.y-b.y = 1)
)
SELECT * FROM board WHERE x = 3 AND y = 3;
结果:
21 = 1 + 2 + 3 + 6 + 9
23 = 1 + 2 + 5 + 6 + 9
25 = 1 + 2 + 5 + 8 + 9
25 = 1 + 4 + 5 + 6 + 9
27 = 1 + 4 + 5 + 8 + 9

29 = 1 + 4 + 7 + 8 + 9

谢谢
返回顶部
顶部