这个序列的特殊之处在于，它的每一项都是对前一项的描述。例如，序列 "1, 11, 21, 1211, 111221, 312211..." 中，"11" 描述了 "1" (一个1)，"21" 描述了 "11" (两个1)，"1211" 描述了 "21" (一个2，一个1)，以此类推。 我们的目标是编写一个程序，给定一个整数 n，返回该序列的第 n 项。
递归方法
最初的代码尝试使用递归方法来解决这个问题，但存在一些逻辑和技术错误。下面我们来分析这些错误并提供修正后的代码。
逻辑错误
原始代码中的一个主要逻辑错误是计数器的初始化。在生成序列的下一项时，计数器 counter 应该从 1 开始，而不是 0。因为每个元素至少会出现一次。
技术错误
- 循环结束后的处理： 在循环遍历字符串 x 结束后，需要将最后一个计数器值和字符连接到结果字符串 y 上。原始代码缺少这一步。
- 递归调用中的递减操作： 递归调用时应该使用前置递减运算符 --times，而不是后置递减运算符 times--。前置递减会先减少 times 的值，然后再将其传递给递归函数，而后者则会先传递 times 的原始值，然后再进行递减，导致递归次数错误。
修正后的递归代码
import java.util.*;
class CoolSequence {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
System.out.println(num(n, "1"));
}
public static String num(int times, String x) {
if (times == 0) {
return x;
} else {
String y = "";
int counter = 1;
for (int i = 1; i < x.length(); i++) {
if (x.charAt(i) == x.charAt(i - 1)) {
counter++;
} else {
y += "" + counter + x.charAt(i - 1);
counter = 1;
}
}
y += "" + counter + x.charAt(x.length() - 1);
return num(--times, y);
}
}
}代码解释：
立即学习“Java免费学习笔记（深入）”；
- num(int times, String x) 函数： 递归函数，times 表示还需要递归的次数，x 表示当前的序列项。
- 基本情况： 如果 times 为 0，则表示已经找到了第 n 项，直接返回 x。
-
生成下一项：
- 初始化一个空字符串 y，用于存储下一项。
- 初始化计数器 counter 为 1。
- 循环遍历字符串 x，从第二个字符开始。
- 如果当前字符与前一个字符相同，则计数器加 1。
- 否则，将计数器值和前一个字符连接到 y 上，并将计数器重置为 1。
- 循环结束后，将最后一个计数器值和字符连接到 y 上。
- 递归调用： 使用 --times 递减 times 的值，并使用新生成的序列项 y 进行递归调用。
迭代方法
除了递归方法，还可以使用迭代方法来解决这个问题。
import java.util.*;
class CoolSequence2 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
ArrayList nums = new ArrayList();
int n = scan.nextInt();
String val = "1";
for (int i = 0; i < n; i++) {
String copy = val;
val = "";
while (!copy.equals("")) {
char curr = copy.charAt(0);
int ind = 0;
int cons = 0;
while (ind < copy.length() && curr == copy.charAt(ind)) {
cons += 1;
ind += 1;
}
val += String.valueOf(cons) + copy.charAt(cons - 1);
copy = copy.substring(cons);
}
nums.add(val);
}
System.out.println(nums.get(nums.size() - 1));
}
} 代码解释：
立即学习“Java免费学习笔记（深入）”；
-
main 函数：
- 读取输入的 n。
- 初始化一个字符串 val 为 "1"，表示序列的第一项。
- 使用一个循环迭代 n 次，生成序列的每一项。
-
生成下一项：
- 将当前的序列项 val 复制到 copy 中。
- 初始化一个空字符串 val，用于存储下一项。
- 使用一个 while 循环，只要 copy 不为空，就继续处理。
- 获取 copy 的第一个字符 curr。
- 初始化计数器 cons 为 0。
- 使用一个 while 循环，只要 ind 小于 copy 的长度，并且当前字符与 curr 相同，就将 cons 加 1，并将 ind 加 1。
- 将计数器值 cons 和字符 curr 连接到 val 上。
- 从 copy 中删除已经处理过的字符。
- 输出结果： 循环结束后，nums 列表中存储了序列的每一项，输出最后一项即可。
总结
本文介绍了两种求解特定序列第 n 项的方法：递归和迭代。递归方法代码简洁，但需要注意逻辑和技术细节，例如计数器的初始化和递归调用的递减操作。迭代方法虽然代码稍长，但思路清晰，更容易理解和调试。选择哪种方法取决于具体的需求和个人偏好。 在实际应用中，如果 n 很大，迭代方法可能更有效率，因为递归方法可能会导致栈溢出。
