一个递归实现的取数游戏
//还没有优化，欢迎各位提出优化意见^.^
题目：
Program国度的人，喜欢玩这样一个游戏，在一块板上写着一行数，共n个。两个游戏者，轮流从最右或最左取一个数。刚开始，每个游戏者的得分均为零。如果一个游戏者取下一个数，则将该数的值加到该游戏者的得分上，最后谁的得分最高谁就赢了游戏。给出这n个数( 从左往右), 假设游戏者都是非常聪明的，问最后两个人的得分(假设第一个人首先取数)．
输入格式：第一行为n(2<=n<=100)，第二行为n个数，每个数字之间均用空格隔开。输出为两个游戏者的得分．第一个数表示第一个游戏者的得分，第二个数为第二个游戏者的得分，两个数字之间用空格隔开。
如输入
6
4 7 2 9 5 2
输出
18 11
/* Copyright (c) aprin at Xiamen University 2005-04
*
*/
#include <stdio.h>
#define MAXN 100
int sum(int data[], int head, int tail);
int best(int data[], int head, int tail) {
int temp1, temp2;
if(head==tail)
return head;
temp1= *(data+head)+sum(data, head+1, tail);
temp2= *(data+tail)+sum(data, head, tail-1);
return (temp1>temp2)?head:tail;/*返回指针*/
}
int sum(int data[], int head, int tail) {
int temp;
if(head==tail)
return 0;/*有0个数据*/
if(tail== head+1)
return (*(data+head)<*(data+tail))?head:tail;/*取小的那一个*/
if(best(data, head, tail)==head)/*改变工作指针，让对方选一个最好值*/
head++;
else tail--;
temp= best(data, head, tail);
if(temp==head)
return *(data+temp)+sum(data, head+1, tail);
else
return *(data+temp)+sum(data, head, tail-1);
}
int main(void) {
int data[MAXN], head, tail, n, i, total1, total2, temp;
scanf("%d", &n);
while((n<2)||(n>100)) {
printf("N is wrong! Please input n(2<=n<=100) again!\n");
scanf("%d", &n);
}
for(i=0; i<n; i++)
scanf("%d", data+i);
total1= total2= 0;
head=0;
tail= n-1;
for(i=0; i<n; i++) {
temp= best(data, head, tail);
if((i+1)%2!=0)
total1= total1+*(data+temp);
else
total2= total2+*(data+temp);
if(temp==head)
head= head+1;
else
tail= tail-1;
}
printf("%d %d\n", total1, total2);
getch();
return 0;
}
