文件名称：pascal取数游戏
文件大小：1KB
文件格式：PAS
更新时间：2015-04-16 11:34:40
pascal 取数游戏 贪心算法
给出2n个（n<=100）个自然数（数小于等于30000）。游戏双方分别为A方（计算机方）和B方（对弈的人）。只允许从数列两头取数。A先取，然后双方依次轮流取数。取完时，谁取得的数字总和最大即为取胜方；若双方的和相等，属于A胜。试问A方可否有必胜的策略？ 输入： Input n:4 Input 2*n data:7 9 3 6 4 2 5 3 输出： Computer'chioce is:3 Selete L/R:L Your chioce is:7 Computer's chioce is:9 Selete L/R:R Your chioce is:5 Computer's chioce is:2 Selete L/R:R Your chioce is:4 Computer's chioce is:6 Selete L/R:L Your chioce is:3 Sum of computer:20 Sum of Person:19 共3n+2行，其中前3*n行为游戏经过。每3行分别为A方所取的数和B方所取的数，及B方取数前应给予的适当提示，让游戏者选择取哪一头的数（L/R—左端或右端）。最后两行分别为A方取得的数和B方取得的数和。 分析： 我们设计一种原始的贪心策略，让A方每次取数列两头大的那个数，则游戏者也不傻，他也会这么干，所以在上面的数列中，A方会按顺序取得7，3，4，5，B会取得9，6，2，3，由此得出A会取得的数和为19，B方取得的和为20，按规则判定A输 如果按上述贪心策略去游戏，成败取决于给你的测试数据，不过，虽然A方败给B方，但我们却发现一个有趣的事实： A方取走偶数位置的数后，剩下两端数都处于奇数位置；反之，若A取走奇数位置的数后，剩下两端数都处于偶数位置，即无论B方如何取法，A既可以取走奇数位置的所有数，也可以取走偶数位置的所有数。由此萌发一种有效的贪心策略： 若能够让A方取走“数和较大大的奇（或偶）位置上的所有数”，则A方必胜。这样，取数问题边对应于一个简单问题：让A方取奇偶位置中数和较大的一半数。设j为A取数的奇偶位置标志，则j=0表示偶数位置数和较大，A取偶数位置上的所有数；反之则去奇数位置上的所有数 设SA，Sb分别表示A方取数和，B方取数和（SA>=SB）；a存储2*n个自然数序列；lp,rp为序列的左端位置和右端位置；ch为B方取数的位置信息（‘L’或‘R’）；