0090-方法越来越妙！你能想到最优策略救下最多人吗？| 囚徒帽子逻辑谜题
0090 囚徒帽子逻辑谜题
程序效果图：
original array 为随机带的帽子颜色
sum array 为看到的帽子颜色对应数字求和
rem array 为求和后对帽子颜色数量求余
answer array 为囚徒回答帽子的颜色
由图可见，第一个报数的牺牲了自己保全了前n个人
代码如下：
~~~
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void print_arr(int *arr, int n)
{
printf(": ");
for(int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main(int argc, char const *argv[])
{
int n, i;
int number;
printf("input people number :");
scanf("%d", &number);
printf("input hat color quantity :");
scanf("%d", &n);
int *array = (int *)malloc(sizeof(int) * number);
// 自动生成
srand(time(0));
for(int i = 0; i < number; i++)
{
array[i] = rand() % n; // n 上面得
}
// 手输数字
// printf("input number: ");
// for (i = 0; i < number; i++)
// {
// scanf("%d", &array[i]);
// }
printf("\n");
printf("original array");
print_arr(array,number);
printf("\n");
// 前面n-1-i个人帽子数求和
int *arr = (int *)malloc(sizeof(int) * number - 1);
int sum = 0;
for (int i = number - 1; i > 0; i--)
{
sum += array[i];
arr[i-1] = sum;
}
printf("sum array");
print_arr(arr, number - 1);
// 前面n-1-i个人帽子求和 取 帽子颜色的模
int *arr_0 = (int *)malloc(sizeof(int) * number - 1);
for (int i = number - 1; i > 0; i--)
{
arr_0[i-1] = arr[i-1]%n;
}
printf("rem array");
print_arr(arr_0, number - 1);
// 算法算出自身帽子颜色
int *arr_1 = (int *)malloc(sizeof(int) * number);
// 最先报颜色到倒数第二个报颜色算法，听到帽子颜色 - 看到帽子颜色（求和求余）
arr_1[0] = arr_0[0];
for (int i = 1; i < number - 1; i++)
{
arr_1[i] = (arr_0[i-1] - arr_0[i] + n)%n ;
}
// 最后一个报颜色算法
int temp = arr_1[0];
for (int i = 1; i < number - 1; i++)
{
temp = (temp - arr_1[i] + n)%n;
}
arr_1[number - 1] = temp;
printf("answer array");
print_arr(arr_1, number);
free(array);
free(arr);
getchar();
system("pause");
return 0;
}
~~~
