欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

进阶实验2-3.1-海盗分赃-编程题

程序员文章站 2022-03-13 15:56:48
...

进阶实验2-3.1-海盗分赃-编程题

解题代码

#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;
}

测试结果

进阶实验2-3.1-海盗分赃-编程题

问题整理

1.这题和博弈论里的情况不太相似。
	比如:倒数第三个人的决策对倒数第二个人的决策的影响不相同
	理想状况下,倒数第三个人是可以独吞全部宝石的,而该题是不能这样的,倒数第三个人必须舍弃一个宝石。