进阶实验2-3.1-海盗分赃-编程题
程序员文章站
2022-03-13 15:56:48
...
解题代码
#include<stdio.h>
#include<stdlib.h>
typedef enum{false,true} bool;
typedef struct farray* pfa;
struct farray {
int data;
bool flag;
};
int Pirate(pfa A, int D, int P);
pfa rePirate(pfa A, int D, int left, int right);
void Clearflag(pfa A, int left, int right);
int main()
{
int D;//n of dimonds
int P;//n of persons
scanf("%d %d", &D, &P);
pfa A = (pfa)malloc(P*sizeof(struct farray));
int ret = Pirate(A, D, P);//n of dimonds the first one will be distributed
printf("%d", ret);
return 0;
}
int Pirate(pfa A, int D, int P) {
return rePirate(A, D, 0, P-1)[0].data;
}
pfa rePirate(pfa A, int D, int left, int right) {//initialization:D=10,P=7
if (right - left + 1 == 3) {
A[left].data = D - 1;
A[left].flag = true;
A[left + 1].data = 1;
A[left + 1].flag = true;
A[right].data = 0;
A[right].flag = true;
return A;
}
A = rePirate(A, D, left + 1, right);
Clearflag(A,left,right);
int cnt = (right - left + 1) / 2;
int i, j=-1;
while (cnt) {
j++;
for (i = left + 1; i <= right; i++) {
if (A[i].data == j&&A[i].flag == false) {
A[i].data++;
D -= A[i].data;
A[i].flag = true;
cnt--;
//printf("A[%d].data=%d D=%d cnt=%d\n", i, A[i].data, D, cnt);
if (!cnt) break;
}
}
}
A[left].data = D;
A[left].flag = true;
for (i = left + 1; i <= right; i++) {
if (A[i].flag == false) A[i].data = 0;
}
//for (i = left; i <=right ; i++) printf("%d\t", A[i].data);
//printf("\n");
return A;
}
void Clearflag(pfa A, int left, int right) {
int i;
for (i = left; i <= right; i++) A[i].flag = false;
}
测试结果
问题整理
1.这题和博弈论里的情况不太相似。
比如:倒数第三个人的决策对倒数第二个人的决策的影响不相同
理想状况下,倒数第三个人是可以独吞全部宝石的,而该题是不能这样的,倒数第三个人必须舍弃一个宝石。
下一篇: 基础实验4-2.2-列出叶结点-函数题