《动态规划实现多边形游戏.pdf》由会员分享，可在线阅读，更多相关《动态规划实现多边形游戏.pdf（7页珍藏版）》请在三一文库上搜索。
1、一、实验题目 : 利用动态规划实现多边形游戏。二、实验内容：给定 N 个顶点的多边形，每个顶点标有一个整数，每条边上标有+(加)或是 (乘)号，并且 N 条边按照顺时针依次编号为1N。下图给出了一个 N4 个顶点的多边形。游戏规则 ：(1) 首先，移走一条边。(2) 然后进行下面的操作：选中一条边 E，该边有两个相邻的顶点，不妨称为 V1 和 V2。对 V1 和 V2 顶点所标的整数按照E 上所标运算符号 (+或是 )进行运算，得到一个整数； 用该整数标注一个新顶点， 该顶点代替 V1 和 V2 。 持续进行此操作， 直到最后没有边存在， 即只剩下一个顶点。 该顶点的整数称为此次游戏的得分 (
2、Score)。三、实验要求：给定一个多边形， 顶点和边已按上述方式进行标注。问：按照游戏规则，最高得分 (最优值)是多少？对应该最高得分，按照什么顺序移走边(最优解 )？输入文件 ：文件 POLYGON.IN 中存储了多边形的信息，该文件中有两行数据 ： 第一行是一个整数N 第二行按照边顶点边顶点.边顶点的顺序以此存放了N 个顶点和 N 条边的标注信息。其中字符t 表示+，字符 x表示 。输出文件 ：文件 POLYGON.OUT ，该文件中有两行数据：第一行是该游戏可能的最高得分。第二行列出第一次移走哪条边(可能有多个 , 如果是多个，则按照递增顺序排列)，会导致最高得分的出现。四、实验流程图
3、：biginA = mis0; b = mis1; r = (I + s - 1) % n + 1; c = mrj - s0; d = mrj - s1;opr.equals(t)Fmin = a + c;Fmax = b + d;yE1 = a * c;E2 = a * d;E3 = b * c;E4 = b * d;Fmin = Fmax= e1;nk = 2k ekyFmin = ek;yFmax eknFmax = ek;yk+nendnminmax(int i, int j, int s) biginj = 2j = n;j+i = 1;yi Fmins j;s+minmax(i,
4、 j, s);ymij0 = Fmin;mij1 = Fmax;mij1 Fmaxynynnntemp = m1n1;k = 2; k = n;temp mkn1temp = m1n1;yk+yn k = n;temp = mkn1firstmove=firstmove+k+ ;yk+ynnk = 1;endpolymax() 五、实验结果：附录：import java.io.*; public class game /* * param args */ static int n,result; static String op; static int v; static int minf,
5、maxf; static int m; static String firstmove=; public static void minmax(int i, int j, int s) int e = new int5; int a = mis0, b = mis1, r = (i + s - 1) % n + 1, c = mrj - s0, d = mrj - s1; if (opr.equals(t) minf = a + c; maxf = b + d; else e1 = a * c; e2 = a * d; e3 = b * c; e4 = b * d; minf = maxf =
6、 e1; for (int k = 2; k ek) minf = ek; if (maxf ek) maxf = ek; public static int polymax() for (int j = 2; j = n; j+) for (int i = 1; i = n; i+) for (int s = 1; s minf) mij0 = minf; if (mij1 maxf) mij1 = maxf; int temp = m1n1; for (int k = 2; k = n; k+) if (temp mkn1) temp = mkn1; for (int k = 1; k =
7、 n; k+) if(temp = mkn1) firstmove=firstmove+k+ ; return temp; public static void main(String args) throws IOException / TODO Auto-generated method stub BufferedReader read=new BufferedReader(new InputStreamReader(new FileInputStream(POLYGON.IN.txt); String a=new String(); a=read.readLine(); n=Intege
8、r.parseInt(a); op = new Stringn+1; v = new intn+1; m = new intn+1n+12; Stringb=new String2*n; a=read.readLine(); b=a.split( ); int k=1,j=1; for(int i=0;i=2*n-2;i+=2) opk+=bi; vj+=Integer.parseInt(bi+1); for(int i=1; i=n; i+) System.out.print(opi+ +vi+ ); System.out.println(); for(int i=1; i=n; i+) mi10 = vi; mi11 = vi; result=polymax(); System.out.println(result); System.out.println(firstmove); PrintWriter print=new PrintWriter(new OutputStreamWriter(new FileOutputStream(POLYGON.OUT.txt); print.println(result); print.println(firstmove); read.close(); print.close();