很久只前我有個朋友提出一道某大公司應聘的題目，今晚突然回想起來，覺得很有趣
如下
有一個 m * n 的矩陣，m n 是提供的確定的數，但算法必須適應任意情況。
里面的數是不確定（任意的）的，要求按一定的方向（如圖），
從左上角第一個元素走到右下角最后一個元素，只能向右和向下走，每走一步，加上那
個數，要求得到的數最小。
要求如下：
第一：算法要簡單
第二：效率要高（因為數據可能很多）
比如：
1 8 0
7 8 8
7 15 1
那么最優路徑就是
1 8 0
8
1
下面我提出自己的想法：
首先：遍歷整個矩陣（二維數組），得到最大的那個數，用一個標記替換他如 '#' ，重復這一，
大概 n 次（n為可能路徑 (還在計算中，會補上的) 的1/3）；
然后：用循環，判斷（排除前面的標記）得到剩下路徑，取出最優值；（如果剩下的個數
還很大，可以重復上一步操作）
這個我的自己的想法，不知道您有沒有其他的想法？請多多指教！
如果您知道，可能的路徑數目的計算公式，也希望你能提供我參考；謝謝！！！
地震讓大伙知道：居安思危，才是生存之道。
posted on 2007-09-03 22:35
小尋 閱讀(2242)
評論(11) 編輯 收藏 所屬分類:
算法