「PAT乙级真题解析」Basic Level 1094 谷歌的招聘 (问题分析+完整步骤+伪代码描述+提交通过代码)
题设给定一串数字串以及一个位数, 要求找出最早出现的长度等于指定位数, 且数值为素数的数字串。 所以最直觉的方法就是从数字串第一位开始, 截取指定位数的数字串, 然后检查其代表的数值是否是素数。 如果是素数则输出该数字串, 如果遍历完毕都没有符合条件的数字串, 则输出"404"。
#算法#数据结构#pat考试#c语言#需求分析
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
PAT (Basic Level) Practice 1094 谷歌的招聘
问题分析
- 题设给定一串数字串以及一个位数, 要求找出最早出现的长度等于指定位数, 且数值为素数的数字串。
- 所以最直觉的方法就是从数字串第一位开始, 截取指定位数的数字串, 然后检查其代表的数值是否是素数。
- 如果是素数则输出该数字串, 如果遍历完毕都没有符合条件的数字串, 则输出"404"。
完整描述步骤
- 获取输入: 完整数字串长度, 指定位数, 完整数字串
- 从数字串第一位开始:
- 截取长度为指定位数的数字串
- 检查截取数字串所代表的数值是否是素数
- 如果是素数:
- 输出该数字串
- 结束程序
- 输出"404";
伪代码描述
- get input: total_length, prime_length, content
- for start_idx in range(0, total_length - prime_length + 1):
- string_to_check = content[start_idx: start_idx+prime_length];
- if is_prime_number(int(string_to_check)):
- print(string_to_check);
- end procedure;
- print("404");
注意事项
- 测试点2、测试点4: 遍历的时候, 循环继续条件要使用等号
i <= total_length - prime_length
完整提交代码
/*
# 问题分析
题设给定一串数字串以及一个位数, 要求找出最早出现的长度等于指定位数, 且数值为素数的数字串。
所以最直觉的方法就是从数字串第一位开始, 截取指定位数的数字串, 然后检查其代表的数值是否是素数。
如果是素数则输出该数字串, 如果遍历完毕都没有符合条件的数字串, 则输出"404"。
# 完整描述步骤
1. 获取输入: 完整数字串长度, 指定位数, 完整数字串
2. 从数字串第一位开始:
- 截取长度为指定位数的数字串
- 检查截取数字串所代表的数值是否是素数
- 如果是素数:
- 输出该数字串
- 结束程序
3. 输出"404";
# 伪代码描述
1. get input: total_length, prime_length, content
2. for start_idx in range(0, total_length - prime_length + 1):
- string_to_check = content[start_idx: start_idx+prime_length];
- if is_prime_number(int(string_to_check)):
- print(string_to_check);
- end procedure;
3. print("404");
# 注意事项
1. 测试点2、测试点4: 遍历的时候, 循环继续条件要使用等号`i <= total_length - prime_length`
*/
# include<stdio.h>
# include<math.h>
int is_prime_number(int number){
if (number < 2){
return 0;
}
if (number == 2){
return 1;
}
int digit = number % 10;
if (digit != 1 && digit != 3 && digit != 5 && digit != 7 && digit != 9 ){
return 0;
}
for(int i = 2; i <= sqrt(number); i++){
if(number % i == 0){
return 0;
}
}
return 1;
}
int check_string_is_prime(char* content, int start, int end){
int value = 0;
for (int i = start; i < end; i++){
value = value * 10 + (content[i] - '0');
}
if (is_prime_number(value)){
return 1;
}
return 0;
}
int main(){
int total_length, prime_length;
scanf("%d %d", &total_length, &prime_length);
char content[1001];
scanf("%s", content);
for (int i = 0; i <= total_length - prime_length; i++){
if (check_string_is_prime(content, i, i+prime_length) == 1){
content[i+prime_length] = 0;
printf("%s", content+i);
return 0;
}
}
printf("404");
return 0;
}