「PAT乙级真题解析」Basic Level 1069 微博转发抽奖 (问题分析+完整步骤+伪代码描述+提交通过代码)
题设要求从给定的一组字符串中的指定位置开始, 按照指定的间隔选择对应位置的字符串进行打印, 但是相同的字符串只能被打印一次(所以这里需要记录是否被打印过的标志位). 值得说明的是, 由于C语言中没有"字符串"类型, 所以用二维字符数组来作为一维字符串数组. 另外, 字符串是否被打印过的记录是一个典型的哈希表记录并用于查询的过程, 但是C语言中没有字典或集合等哈希表数据结构, 所以需要使用"字符串数组/二维字符数组"存储打印过的字符串, 通过对数组的遍历查询是否某个字符串已经在数组中来判断是否已经打印过该
#数据结构#算法#需求分析#c语言#pat考试
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
PAT乙级BasicLevelPractice 1069 微博转发抽奖
问题分析
题设要求从给定的一组字符串中的指定位置开始, 按照指定的间隔选择对应位置的字符串进行打印, 但是相同的字符串只能被打印一次(所以这里需要记录是否被打印过的标志位). 值得说明的是, 由于C语言中没有"字符串"类型, 所以用二维字符数组来作为一维字符串数组. 另外, 字符串是否被打印过的记录是一个典型的哈希表记录并用于查询的过程, 但是C语言中没有字典或集合等哈希表数据结构, 所以需要使用"字符串数组/二维字符数组"存储打印过的字符串, 通过对数组的遍历查询是否某个字符串已经在数组中来判断是否已经打印过该字符串.
完整描述步骤
- 获取输入: 转发次数, 抽奖间隔, 第一位中奖者的序号
- 获取输入: 每一次转发对应的转发者的ID
- 初始化统计器:
- 已经抽取的中奖用户个数 = 0
- 对于每一次转发:
- 检查转发次序是否符合中奖条件:
- 如果符合, 检查是否该用户已经被抽中:
- 如果没有被抽中过, 则选择该用户输出并标记该用户抽奖状态为已抽中
- 如果已经抽中过, 则不断顺次检查下一个用户直到检查到未抽中过的用户
- 已经抽取的中奖用户个数+1
- 如果符合, 检查是否该用户已经被抽中:
- 检查转发次序是否符合中奖条件:
- 如果抽中用户个数为0, 则输出"Keep going..."
伪代码描述
- get input: share_amount, interval, first_selected_order
- get input: user_name of each share
- for (int i = 0; i < share_amount; i++):
- all_user_name[i] = user_name;
- for (int i = 0; i < share_amount; i++):
- init recorder:
- user_name_been_selected;
- selected_amount = 0;
- for (int i = 0; i < share_amount; i++):
- if i+1 == selected_amount * interval + first_selected_order:
- while all_user_name[i] in user_name_been_selected:
- i++
- first_selected_order++
- user_name_been_selected[all_user_name[i]] == 1
- selected_amount++;
- print(all_user_name[i]);
- while all_user_name[i] in user_name_been_selected:
- if i+1 == selected_amount * interval + first_selected_order:
- if selected_amount == 0:
- print("Keep going...");
注意事项
- 题设说的"中奖间隔"是实际每一个被抽中的用户到下一个开始检查的用户的距离, 也就是说, 当某位用户已经被抽中过而发生顺延的时候, 应该从最终选中的用户开始一个间隔距离的用户开始进行下一轮的检查。
- 具体实现为: 每次发生顺延, 都将第一个中奖号码也跟着顺延, 就可以保持每次检查是否中奖的表达式不变
- 忽略这点会导致测试点3错误
完整提交代码
/*
# 问题分析
题设要求从给定的一组字符串中的指定位置开始, 按照指定的间隔选择对应位置的字符串进行打印,
但是相同的字符串只能被打印一次(所以这里需要记录是否被打印过的标志位).
值得说明的是, 由于C语言中没有"字符串"类型, 所以用二维字符数组来作为一维字符串数组.
另外, 字符串是否被打印过的记录是一个典型的哈希表记录并用于查询的过程,
但是C语言中没有字典或集合等哈希表数据结构, 所以需要使用"字符串数组/二维字符数组"存储打印过的字符串,
通过对数组的遍历查询是否某个字符串已经在数组中来判断是否已经打印过该字符串.
# 完整描述步骤
1. 获取输入: 转发次数, 抽奖间隔, 第一位中奖者的序号
2. 获取输入: 每一次转发对应的转发者的ID
3. 初始化统计器:
- 已经抽取的中奖用户个数 = 0
3. 对于每一次转发:
- 检查转发次序是否符合中奖条件:
- 如果符合, 检查是否该用户已经被抽中:
- 如果没有被抽中过, 则选择该用户输出并标记该用户抽奖状态为已抽中
- 如果已经抽中过, 则不断顺次检查下一个用户直到检查到未抽中过的用户
- 已经抽取的中奖用户个数+1
4. 如果抽中用户个数为0, 则输出"Keep going..."
# 伪代码描述
1. get input: share_amount, interval, first_selected_order
2. get input: user_name of each share
- for (int i = 0; i < share_amount; i++):
- all_user_name[i] = user_name;
3. init recorder:
- user_name_been_selected;
- selected_amount = 0;
4. for (int i = 0; i < share_amount; i++):
- if i+1 == selected_amount * interval + first_selected_order:
- while all_user_name[i] in user_name_been_selected:
- i++
- first_selected_order++
- user_name_been_selected[all_user_name[i]] == 1
- selected_amount++;
- print(all_user_name[i]);
5. if selected_amount == 0:
- print("Keep going...");
# 注意事项
1. 题设说的"中奖间隔"是实际每一个被抽中的用户到下一个开始检查的用户的距离, 也就是说, 当某位用户已经被抽中过而发生顺延的时候, 应该从最终选中的用户开始一个间隔距离的用户开始进行下一轮的检查。
- 具体实现为: 每次发生顺延, 都将第一个中奖号码也跟着顺延, 就可以保持每次检查是否中奖的表达式不变
- 忽略这点会导致测试点3错误
*/
# include<stdio.h>
# include<string.h>
char name_checked[1000][21];
int user_has_been_selected(char* name, int selected_amount){
for (int i = 0; i < selected_amount; i++){
if (strcmp(name, name_checked[i]) == 0) return 1;
}
return 0;
}
int main(){
int share_amount, interval, first_selected_order;
scanf("%d %d %d", &share_amount, &interval, &first_selected_order);
int selected_amount = 0;
char all_user_name[share_amount][21];
for (int i = 0; i < share_amount; i++){
scanf("%s", all_user_name[i]);
}
for (int i = 0; i < share_amount; i++){
if(i+1 == selected_amount * interval + first_selected_order){
while (user_has_been_selected(all_user_name[i], selected_amount) == 1){
i++;
first_selected_order++;
}
strcpy(name_checked[selected_amount], all_user_name[i]);
printf("%s\n", all_user_name[i]);
selected_amount++;
}
}
if (selected_amount == 0){
printf("Keep going...\n");
}
return 0;
}