算法设计与分析五邑大学

《算法设计与分析五邑大学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计问题示例计算机科学的本质是算法计算机硬件系统仅仅是依照特定的算法，按照物理和电子学原理，采用特定的工艺流程生产的一种电子计算装置计算机程序设计语言是仅仅是程序员与计算机硬件系统进行沟通、交流的一种工具语言熟练掌握一种程序设计语言是成为一名优秀程序员的基础要成为一名优秀的、能够解决各类疑难问题的程序员必须具有良好的算法设计的品质1.中国象棋中马的走法问题描述：在4×5的棋盘上已知马的起始坐标(x,y)，求马能够返回到起始位置的不重复的所有不同走法的总数。回溯法！马当前所在的位置是当前扩展结点！每个活结

2、点可能有八个孩子结点！如何记录马行走的路径？152643classHorse{private:intchess[5][6];intd[2][8]={(1,2,2,1-1,-2,-2,-1),(2,1,-1,-2,-2,-1,1,2)};intsx,sy;intcount;public:Horse(intx,inty){sx=x;sy=y;for(inti=0;i<6;i++)for(intj=0;j<5;j++)chess[i][j]=0;}staticlongcomputer(){count=0;if(s

3、x<0

4、

5、sy<0

6、

7、sx>=6

8、

9、sy>=5)return;backtrack(sx,sy);returncount;}Privatestaticvoidbacktrack(intp1,intp2);};PrivatestaticvoidHorse::backtrack(intp1,intp2){intpi,pj;for(inti=0;i<7;i++){pi=p1+d[0][i];pj=p2+d[1][j];if(pi>=0&&pi<6&&pj>=0&&pj<5&&ch[pi][pj]==0){chess

10、[pi][pj]=1;backtrack(pi,pj);chess[pi][pj]=0;}elseif(pi==sx&&pj==sy)count++;}};2.合法的括号序列问题描述：定义合法的括号序列：1.空序列是合法的括号序列；2.如果符号串S是合法的括号序列，则(S)和[S]均是合法的括号序列；3.如果符号串A和B是合法的括号序列，则AB也是合法的括号序列。现有由(，)，[，]组成的任意符号串X=x1x2…xn，请添加尽可能少的四种括号，使其成为一个合法的括号序列。动态规划！分析：假设子问题Xij=x

11、ixi+1…xkxk+1…xj-1xj最少需要添加m[i][j]个括号，则：0i>j1i=jm[i][j]=min{m[i][j],m[i+1][j-1]}xi=(&&sj=)

12、

13、xi=[&&xj=]min{m[i][j],m[i+1][j]}+1xi=(

14、

15、xi=[min{m[i][j],m[i][j-1]}+1xj=)

16、

17、xj=]min{m[i][j],m[i][k]+m[k+1][j]}（i<=k

18、[]m=newint[m+1][n+1];for(inti=1;i<=n;i++)m[i][i-1]=0;for(inti=1;i<=n;i++)m[i][i]=1;for(intr=2;i<=n;r++)for(inti=1;i<=n-r+1;i++){intj=i+r-1;m[i][j]=MaxINT;if(x[i]==‘(‘&&x[j]==‘)’

19、

20、x[i]==‘[‘&&x[j]==‘]’)m[i][j]=min(m[i][j],m[i+1][j-1]);if(x[i]==‘(‘

21、

22、x[i]==‘[’

23、)m[i][j]=min(m[i][j],m[i+1][j])+1;if(x[j]==‘)‘

24、

25、x[j]==‘]’)m[i][j]=min(m[i][j],m[i][j-1])+1;for(intk=i;k

26、成了n块矩形棋盘。一块矩形棋盘的总分是他的所有格子的分值之和。请设计算法，给出把原棋盘分割成n块矩形棋盘的方案，使得各矩形棋盘总分的平方和最小。其中xi是第i块棋盘的总分。动态规划！x1,y1x2,y2ab3.棋盘的最优分割假设左上角为(x1,y1)、右下角为(x2,y2)的棋盘的总分为：s[x1,y1,x2,y2]，被切割k次后得到的k+1块矩形的总分平方和的最小值是：d[k,x1,y1,x2,y2]则：d[k