游戏开发中经典算法.doc

游戏开发中的经典算法算法是程序设计的精髓，程序设计的实质就是构造解决问题的算法，将其解释为计算机语言。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一个算法应该具有以下五个重要的特征： 有穷性： 一个算法必须保证执行有限步之后结束； 确切性： 算法的每一步骤必须有确切的定义； 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况； 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。 动态规划-航线设置 问题描述:美丽的莱茵河畔,每边都分布着N个城市,两边的城市都是唯一对应的友好城市,现需要在友好城市开通航线以加强往来.但因为莱茵河常年大雾,如果开设的航线发生交叉现象就有可能出现碰船的现象.现在要求近可能多地开通航线并且使航线不能相交! 假如你是一个才华横溢的设计师,该如何设置友好城市间的航线使的航线数又最大又不相交呢? 分析:此问题可以演化成求最大不下降序列来完成.源程序如下: program dongtai; {动态规划之友好城市航线设置问题} var d:array[1..1000,1..4] of integer; i,j,k,n,L,p:integer; procedure print(L:integer); {打印结果} begin writeLn(最多可设置的航线数是 : ,k); repeat writeLn(d[L,1]:4,d[L,2]:4); {输出可以设置航线的友好城市代码} L:=d[L,4] untiL L=0 end; begin writeLn(输入友好城市对数: ); readLn(n); writeLn(输入友好城市对（友好城市放在同一行:); {输入} for i:=1 to n do readLn(d[i,1],d[i,2]); {D[I，1]表示起点，D[I，2]表示终点} for i:=1 to n do begin d[i,3]:=1; {D[I，3]表示可以设置的航线条数} d[i,4]:=0 {D[I，4]表示后继，即下一条航线从哪里开始设置，为0表示不能设置下一条航线} end; for i:=n-1 downto 1 do {从倒数第二个城市开始规划} begin L:=0; p:=0; {L表示本城市后面可以设置的航线数，P表示下条航线从哪个城市开始} for j:=i+1 to n do {找出本城市后面可以设置的最大航线数和小条航线到底从哪个城市开始设置} if (d[i,2] L) then {如果本城市I的终点小于后面城市的终点（即不相交）} {并且此城市后面可以设置的航线数大于L} begin L:=d[j,3]; {那么L等于城市J的可以设置航线数} p:=j {P等于可以设置下条航线的城市代码} end; if L0 then {如果本城市后面总共可以设置的航线数0则} begin d[i,3]:=L+1; {本城市可以设置的航线数在下个城市可以设置航线数的基础上加1} d[i,4]:=p {D[I，4]等于本城市后续城市的代码} end end; k:=d[1,3]; {K为可以设置最大航线数，假设初值为第一个城市可以设置的航线数} L:=1; {L为城市代码，初值为第一个城市} for i:=2 to n do {找出可以设置航线的最大值，赋值给K，同时L记下哪个可以设置最大航线数的城市代码} if d[i,3]k then begin k:=d[i,3]; L:=i end; for i:=1 to n do {打印结果，因为有可能有多种方案，所以只要哪个城市可以设置的航线数等于最大值K就打印结果} if d[i,3]=k then print(i) end.归并排序算法 合并排序（MERGE SORT）是又一类不同的排序方法，合并的含义就是将两个或两个以上的有序数据序列合并成一个新的有序数据序列，因此它又叫归并算法。它的基本思想就是假设数组A有N个元素，那么可以看成数组A是又N个有序的子序列组成，每个子序列的长度为1，然后再两两合并，得到了一个 N/2 个长度为2或1的有序子序列，再两两合并，如此重复，值得得到一个长度为N的有序数据序列为止，这种排序方法称为2—路合并排序。 例如数组A有7个数据，分别是： 49 38 65 97 76 13 27，那么采用归并排序算法的操作过程如图7所示： 初始值 [49] [38] [65] [97] [76] [13] [27