0090-方法越來(lái)越妙！你能想到最優(yōu)策略救下最多人嗎？| 囚徒帽子邏輯謎題
0090 囚徒帽子邏輯謎題
程序效果圖：
original array 為隨機(jī)帶的帽子顏色
sum array 為看到的帽子顏色對(duì)應(yīng)數(shù)字求和
rem array 為求和后對(duì)帽子顏色數(shù)量求余
answer array 為囚徒回答帽子的顏色
由圖可見，第一個(gè)報(bào)數(shù)的犧牲了自己保全了前n個(gè)人
代碼如下：
~~~
#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);
? ? // 自動(dòng)生成
? ? srand(time(0));
? ? for(int i = 0; i < number; i++)
? ? {
? ? ? ? array[i] = rand() % n; ?// n 上面得
? ? }
? ? // 手輸數(shù)字
? ? // 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個(gè)人帽子數(shù)求和
? ? 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個(gè)人帽子求和 取 帽子顏色的模
? ? 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);
? ? // 最先報(bào)顏色到倒數(shù)第二個(gè)報(bào)顏色算法，聽到帽子顏色 - 看到帽子顏色（求和求余）
? ? 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 ;
? ? }
// 最后一個(gè)報(bào)顏色算法
? ? 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;
}
~~~
