「PAT乙级真题解析」Basic Level 1089 狼人杀-简单版 (问题分析+完整步骤+伪代码描述+提交通过代码)

题设给定假设狼人杀中N名玩家有2人是狼人, 有2名玩家说的不是实话, 只有一个狼人说谎。要求计算出扮演狼人的玩家。 题目的重点在于身份的确认和发言真假的确认。 因为题设固定了狼人的数量只有2个, 所以我们需要从N名玩家中假设2个玩家是狼人, 其余玩家就都认为是好人, 身份的确认就完成了。 发言真假确认通过题设给定的规则, 如果发言认为某人是狼人且该玩家确认是狼人, 则为真; 或者认为某人不是狼人且该玩家确实不是狼人, 则为真; 其余都为假。 最后只需要检查 全部谎言的数量是否为2 且 狼人说谎的数量是否为1

#算法#数据结构#c语言#需求分析#pat考试

Table of Contents

乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT (Basic Level) Practice 1089 狼人杀-简单版

问题分析

  • 题设给定假设狼人杀中N名玩家有2人是狼人, 有2名玩家说的不是实话, 只有一个狼人说谎。要求计算出扮演狼人的玩家。
  • 题目的重点在于身份的确认和发言真假的确认。
  • 因为题设固定了狼人的数量只有2个, 所以我们需要从N名玩家中假设2个玩家是狼人, 其余玩家就都认为是好人, 身份的确认就完成了。
  • 发言真假确认通过题设给定的规则, 如果发言认为某人是狼人且该玩家确认是狼人, 则为真; 或者认为某人不是狼人且该玩家确实不是狼人, 则为真; 其余都为假。
  • 最后只需要检查 全部谎言的数量是否为2 且 狼人说谎的数量是否为1, 则可以知道是否满足题设条件。

题目的迷惑说明

  • 题目没有说清楚输出格式中要求的"最小序列解"中的"序列"到底是什么序列。
    • 是代表身份的0-1序列? 比如:(0, 0, 0, ..., 1, ..., 0)
    • 还是由各个玩家发言组成的序列? 比如: (-2, +3, -4, ..., +4)
  • 由于发言序列其实是固定的, 所以只能是在说身份序列, 则遍历狼人身份是编号从小到大遍历, 输出第一个符合条件的解即可。

完整描述步骤

  1. 获取输入: 玩家数量, 各个玩家的发言
  2. 初始化记录器:
    • 第i个玩家说的话是假的 = {0}
  3. 假设第一个狼人编号为X, X取值区间为[1, N]:
    • 假设第二个狼人编号为Y, Y取值区间为[X+1, N]:
      • 对每一个玩家的发言进行检查:
        • 如果指认了某个狼人是好人, 或者指认了狼人之外的人是坏人:
          • 记录该玩家的发言是谎言
      • 如果 谎言的总数为2 且 狼人撒谎的总数为1:
        • 输出"{第一个狼人的编号} {第二个狼人的编号}"
        • 结束程序
  4. 无解, 输出"No solution"

伪代码描述

  1. get input: play_amount, arguments of players
  2. init recorder:
    • argument_is_lie[play_amount] = {False}
    • total_lie_amount = 0;
    • wolfman_lie_amount = 0;
  3. for wolfman_no_1 in range(0, play_amount):
    • for wolfman_no_2 in range(wolfman_no_1+1, play_amount):
      • for player_index in range(0, play_amount):
        • if check_argument_is_lie(arguments[player_index]) == True:
          • argument_is_lie[player_index] = True;
          • total_lie_amount++;
          • if player_index == wolfman_no_1 or player_index == wolfman_no_2:
            • wolfman_lie_amount++;
      • if total_lie_amount == 2 and wolfman_lie_amount == 1:
        • print("{wolfman_no_1} {wolfman_no_2}");
        • end procedure;
  4. print("No Solution");

注意事项

  1. 玩家的序号是从1开始的, 如果存储和遍历的时候从下标0开始, 那么检查玩家是否说谎的时候需要先把狼人序号+1。

完整提交代码

/*
# 问题分析
题设给定假设狼人杀中N名玩家有2人是狼人, 有2名玩家说的不是实话, 只有一个狼人说谎。要求计算出扮演狼人的玩家。
题目的重点在于身份的确认和发言真假的确认。
因为题设固定了狼人的数量只有2个, 所以我们需要从N名玩家中假设2个玩家是狼人, 其余玩家就都认为是好人, 身份的确认就完成了。
发言真假确认通过题设给定的规则, 如果发言认为某人是狼人且该玩家确认是狼人, 则为真; 或者认为某人不是狼人且该玩家确实不是狼人, 则为真; 其余都为假。
最后只需要检查 全部谎言的数量是否为2 且 狼人说谎的数量是否为1, 则可以知道是否满足题设条件。
 
## 题目的迷惑说明
题目没有说清楚输出格式中要求的"最小序列解"中的"序列"到底是什么序列。
是代表身份的0-1序列? 比如:(0, 0, 0, ..., 1, ..., 0)
还是由各个玩家发言组成的序列? 比如: (-2, +3, -4, ..., +4)
由于发言序列其实是固定的, 所以只能是在说身份序列, 则遍历狼人身份是编号从小到大遍历, 输出第一个符合条件的解即可。
 
# 完整描述步骤
1. 获取输入: 玩家数量, 各个玩家的发言
2. 初始化记录器:
    - 第i个玩家说的话是假的 = {0}
3. 假设第一个狼人编号为X, X取值区间为[1, N]:
    - 假设第二个狼人编号为Y, Y取值区间为[X+1, N]:
        - 对每一个玩家的发言进行检查:
            - 如果指认了某个狼人是好人, 或者指认了狼人之外的人是坏人:
                - 记录该玩家的发言是谎言
        - 如果 谎言的总数为2 且 狼人撒谎的总数为1:
            - 输出"{第一个狼人的编号} {第二个狼人的编号}"
            - 结束程序
4. 无解, 输出"No solution"
 
# 伪代码描述
1. get input: play_amount, arguments of players
2. init recorder:
    - argument_is_lie[play_amount] = {False}
    - total_lie_amount = 0;
    - wolfman_lie_amount = 0;
3. for wolfman_no_1 in range(0, play_amount):
    - for wolfman_no_2 in range(wolfman_no_1+1, play_amount):
        - for player_index in range(0, play_amount):
            - if check_argument_is_lie(arguments[player_index]) == True:
                - argument_is_lie[player_index] = True;
                - total_lie_amount++;
                - if player_index == wolfman_no_1 or player_index == wolfman_no_2:
                    - wolfman_lie_amount++;
        - if total_lie_amount == 2 and wolfman_lie_amount == 1:
            - print("{wolfman_no_1} {wolfman_no_2}");
            - end procedure;
4. print("No Solution");
 
# 注意事项
1. 玩家的序号是从1开始的, 如果存储和遍历的时候从下标0开始, 那么检查玩家是否说谎的时候需要先把狼人序号+1。
*/
 
# include<stdio.h>
 
int check_argument_is_lie(int argument, int wolfman_no_1, int wolfman_no_2){
    wolfman_no_1++;
    wolfman_no_2++;
    if (argument > 0 && argument != wolfman_no_1 && argument != wolfman_no_2){
        return 0;
    }
    
    if (argument < 0 && -argument == wolfman_no_1){
        return 0;
    }
 
    if (argument < 0 && -argument == wolfman_no_2){
        return 0;
    }
    
    return 1;
}
 
int is_meet_conditions(int *argument_is_lie, int play_amount, int wolfman_no_1, int wolfman_no_2){
    int lie_amount = 0;
    int wolfman_lie_amount = 0;
    for (int i = 0; i < play_amount; i++){
        if (argument_is_lie[i]){
            lie_amount++;
            if (i == wolfman_no_1 || i == wolfman_no_2){
                wolfman_lie_amount++;
            }
        }
    }
 
    if (lie_amount == 2 && wolfman_lie_amount == 1){
        return 1;
    }
 
    return 0;
}
 
int main(){
    int player_amount;
    scanf("%d", &player_amount);
    
    int arguments[player_amount];
    int argument_is_lie[player_amount];
    for (int i = 0 ; i < player_amount; i++){
        scanf("%d", &arguments[i]);
        
    }
    
    for (int wolfman_no_1 = 0; wolfman_no_1 < player_amount; wolfman_no_1++){
        for (int wolfman_no_2 = wolfman_no_1 + 1; wolfman_no_2 < player_amount; wolfman_no_2++){
            for (int i = 0; i < player_amount; i++){
                argument_is_lie[i] = check_argument_is_lie(arguments[i], wolfman_no_1, wolfman_no_2);
            }
            if (is_meet_conditions(argument_is_lie, player_amount, wolfman_no_1, wolfman_no_2)){
                printf("%d %d", wolfman_no_1+1, wolfman_no_2+1);
                return 0;
            }
        }
    }
    
    printf("No Solution\n");
    return 0;
}
「PAT乙级真题解析」Basic Level 1089 狼人杀-简单版 (问题分析+完整步骤+伪代码描述+提交通过代码) | 生活糖果