這個題目做得好辛苦。題目大意是給三個算術表達式,前兩個相加等于第三個,每位數都用字母代替,問最后字母對應的數是多少。數據范圍n <= 26。由于進位不確定,因此需要枚舉進位,再用高斯消元求解。我報著試一試的態度敲了一個2 ^ n * n ^ 3的程序上去,果然超時了。不知道應該如何優化,到網上看了一下,因為每次枚舉的都是常數,因此可以先把每個未知數用常量表示出來,這樣每次枚舉回帶求解的復雜度就降到了O(n ^ 2)。感覺這種做法很巧妙,不過實現的時候出了很多問題,搞了一下午才搞定- -!
首先需要保存對于每個變量,它對應的每個常數的系數是多少。開始的時候我列方程的方向想錯了,相當成模n域的方程組來求解。結果寫了很久之后發現因為n不一定是素數,所以求解的時候解可能有多個,這樣的話就比較復雜了。后來一怒之下索性當成實數域來求解,重新列了方程,這樣解就是唯一的了,但是中間運算全是浮點數,很擔心精度問題,交上去居然過了。
這個題目加速消元的思想還是很值得借鑒的,高斯消元的優化問題不多,但是感覺都挺有意思,就像用弦圖加速高斯消元。根據方程的不同特點來選擇合適的優化方法很重要啊。
posted on 2009-06-10 21:49
sdfond 閱讀(222)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm - Ad Hoc