日，便开始了自己的图书馆之旅，他现在做的事情是要把信息学这个学科重头开始学起。

　　但是，才刚刚上手，他就觉得有些不适应。

　　因为信息学实在是太杂了。

　　初赛考察通用和实用的计算机普及科学知识，以笔试为主。

　　复赛为程序设计，须在计算机上调试完成。

　　而不论是计算机普及科学知识还是程序设计，苏牧都得从头开始学起。

　　他现在手上的两本书是在淘宝上购买的《信息学奥赛一本通·提高篇》和《信息学奥赛之数学一本通C++版》

　　“近些年来的信息学竞赛试题，经常出现求一个问题的可行解或者最优解的题目，这类问题统称为最优化问题，贪心算法是求解这一类问题的常用方法。”

　　苏牧首先打开的是这本《信息学奥赛一本通·提高篇》

　　“最优化问题。”他摸了摸下巴，脑海中闪过了几种数学里关于最优化的解决方案。

　　信息学很多东西本身就是与数学相通的，这让他的心境稍微稳了积分。

　　但是，当他看到例题的时候，脑海中瞬间就出现了几个问号。

　　题目1：在N行M列的正整数矩阵中，要求从每行中选取一个数，使得选出的N个数的和最大。

　　解析：本题可以用贪心算法求解，选N次，每一次选出相应行中的最大值即可。

　　苏牧：“......”

　　这种题目还需要解析？？

　　这不是理所当然的吗？

　　他看向了第二个题目。

　　题目2：在一个N??M的方格阵中，每一个格子赋予一个数（即权值），规定每次移动时只能向上或者向右，现试找一条路劲，使其从左下角至右上角所经过的权值之和最大。

　　解析：在这种情况下.....

　　一步一步看下来。

　　苏牧倒也没觉得有什么难的，只不过是一些取极值的问题。

　　但是，当他翻到后面的经典习题和解析的时候，整个人都不好了。

　　【经典习题】在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。

　　解析：首先这是一个搜索问题，运用深度优先搜索进行求解，算法如下：

　　⒈输入初始位置坐标x，y；

　　⒉步骤c:

　　如果c>64输出一个解，返回上一步骤c--

　　（x，y)←c

　　计算(x，y）的八个方位的子结点，选出那些可行的子结点

　　循环遍历所有可行子结点，步骤c++重复2

　　显然⑵是一个递归调用的过程，大致如下（C++程序解析）：

　　#defineN8

　　voiddfs(intx，inty，intcount)

　　{

　　inti，tx，ty;

　　if(count>N*N)

　　{

　　output_solution();//输出一个解

　　return

　　请收藏：https://m.wrbet.org

（温馨提示：请关闭畅读或阅读模式，否则内容无法正常显示）