第(2/3)頁

    因為沒有其他事情的束縛，蘇牧現在的行動力變得很高。

    回到家后的第一個工作日，便開始了自己的圖書館之旅，他現在做的事情是要把信息學這個學科重頭開始學起。

    但是，才剛剛上手，他就覺得有些不適應。

    因為信息學實在是太雜了。

    初賽考察通用和實用的計算機普及科學知識，以筆試為主。

    復賽為程序設計，須在計算機上調試完成。

    而不論是計算機普及科學知識還是程序設計，蘇牧都得從頭開始學起。

    他現在手上的兩本書是在淘寶上購買的《信息學奧賽一本通·提高篇》和《信息學奧賽之數學一本通c++版》

    “近些年來的信息學競賽試題，經常出現求一個問題的可行解或者最優解的題目，這類問題統稱為最優化問題，貪心算法是求解這一類問題的常用方法。”

    蘇牧首先打開的是這本《信息學奧賽一本通·提高篇》

    “最優化問題?！彼嗣掳停X海中閃過了幾種數學里關于最優化的解決方案。

    信息學很多東西本身就是與數學相通的，這讓他的心境稍微穩了積分。

    但是，當他看到例題的時候，腦海中瞬間就出現了幾個問號。

    題目1：在n行m列的正整數矩陣中，要求從每行中選取一個數，使得選出的n個數的和最大。

    解析：本題可以用貪心算法求解，選n次，每一次選出相應行中的最大值即可。

    蘇牧：“......”

    這種題目還需要解析？？

    這不是理所當然的嗎？

    他看向了第二個題目。

    題目2：在一個n??m的方格陣中，每一個格子賦予一個數（即權值），規定每次移動時只能向上或者向右，現試找一條路勁，使其從左下角至右上角所經過的權值之和最大。

    解析：在這種情況下.....

    一步一步看下來。

    蘇牧倒也沒覺得有什么難的，只不過是一些取極值的問題。

    但是，當他翻到后面的經典習題和解析的時候，整個人都不好了。

    【經典習題】在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格并且只經過一次的一條路徑。

    解析：首先這是一個搜索問題，運用深度優先搜索進行求解，算法如下：

    1輸入初始位置坐標x，y；

    2步驟c:

    如果c64輸出一個解，返回上一步驟c--

    （x，y)←c

    計算(x，y）的八個方位的子結點，選出那些可行的子結點

    循環遍歷所有可行子結點，步驟c++重復2

    顯然2是一個遞歸調用的過程，大致如下（c++程序解析）：

    #definen8

    voiddfs(intx，inty，intcount)
    第(2/3)頁