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