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

PAT (Basic Level) Practice 1084 外观数列

问题分析

• 题设定义外观数列就是第n项是对第n-1项各个数字连续出现次数的统计, 跟"1078 字符串压缩与解压"类似。
• 比如:
  • “2"的下一项是描述"2"出现了1次, 所以是"21”
  • “21"的下一项是"2"出现了1次, 1出现了1次, 所以是"2111”
  • “2111"的下一项是"2"出现了1次, 1出现了3次, 所以是"2113”

完整描述步骤

1. 获取输入: 起始数字, 目标项的序号
2. 如果要求输出的是第1项:
   • 直接输出起始数字
   • 结束程序
3. 初始化记录器:
   • 上一项 = 起始数字
   • 当前项 = 空字符串
   • 上一个字符 = “@”
   • 上一个字符已经出现的次数 = 0
4. 循环(target_order - 1)次:
   • 对于上一项的中每一个字符:
     • 如果是第一个字符:
       • 设置 上一个字符 = 当前字符
       • 设置 上一个字符已经出现的次数 = 1
       • continue
     • 如果当前字符不等于上一个字符:
       • 当前项 += “{上一个字符}{上一个字符已经出现的次数}”
       • 设置 上一个字符 = 当前字符
       • 设置 上一个字符已经出现的次数 = 1
     • 否则:
       • 上一个字符已经出现的次数++
5. 输出当前项

伪代码分析

1. get input: digit, target_order
2. if target_order == 1:
   • print(digit);
   • end procedure;
3. init recorder:
   • last_item = string(digit)
   • current_item = “”
   • last_digit = “@”
   • frequency = 0
4. for i in range(1, target_order):
   for idx, char in last_item:
   - if idx == 0:
   - last_digit = char;
   - frequency = 1;
   - continue;
   - if char != last_digit:
   - current_item += “{last_digit}{frequency}”
   - last_digit = char;
   - frequency = 1;
   - else:
   - frequency++;
5. print(current_item);

注意事项

1. 数组如果不够长, 测试点4可能发生段错误。需要将长度设置为100000.

完整提交代码

/*
# 问题分析
题设定义外观数列就是第n项是对第n-1项各个数字连续出现次数的统计, 跟"1078 字符串压缩与解压"类似。
比如: 
- "2"的下一项是描述"2"出现了1次, 所以是"21"
- "21"的下一项是"2"出现了1次, 1出现了1次, 所以是"2111"
- "2111"的下一项是"2"出现了1次, 1出现了3次, 所以是"2113"# 完整描述步骤
1. 获取输入: 起始数字, 目标项的序号
2. 如果要求输出的是第1项:- 直接输出起始数字- 结束程序
3. 初始化记录器:- 上一项 = 起始数字- 当前项 = 空字符串- 上一个字符 = "@"- 上一个字符已经出现的次数 = 0
4. 循环(target_order - 1)次:- 对于上一项的中每一个字符:- 如果是第一个字符:- 设置 上一个字符 = 当前字符- 设置 上一个字符已经出现的次数 = 1- continue- 如果当前字符不等于上一个字符:- 当前项 += "{上一个字符}{上一个字符已经出现的次数}"- 设置 上一个字符 = 当前字符- 设置 上一个字符已经出现的次数 = 1- 否则:- 上一个字符已经出现的次数++
5. 输出当前项# 伪代码分析
1. get input: digit, target_order
2. if target_order == 1:- print(digit);- end procedure;
3. init recorder:- last_item = string(digit)- current_item = ""- last_digit = "@"- frequency = 0
4. for i in range(1, target_order):for idx, char in last_item:- if idx == 0:- last_digit = char;- frequency = 1;- continue;- if char != last_digit:- current_item += "{last_digit}{frequency}"- last_digit = char;- frequency = 1;- else:- frequency++;
5. print(current_item);# 注意事项
1. 数组如果不够长, 测试点4可能发生段错误。需要将长度设置为100000.*/# include
# includeint main(){int digit, target_order;scanf("%d %d", &digit, &target_order);if (target_order == 1){printf("%d", digit);return 0;}char last_item[100000];char current_item[100000];memset(last_item, 0, 100000);memset(current_item, 0, 100000);last_item[0] = '0' + digit;int last_digit = '@';int frequency = 0;for (int i = 1; i < target_order; i++){int current_idx = 0;for (int j = 0; last_item[j]; j++){if (j == 0){last_digit = last_item[j];frequency = 1;continue;}if (last_item[j] != last_digit){current_item[current_idx] = last_digit;current_item[current_idx + 1] = '0' + frequency;current_idx += 2;last_digit = last_item[j];frequency = 1;} else {frequency++;}}current_item[current_idx] = last_digit;current_item[current_idx + 1] = '0' + frequency;strcpy(last_item, current_item);}printf("%s", current_item);return 0;
}