查找序列中的第 n 项

Question

我有一个序列，我正在尝试编写一个程序来查找序列的第 n 项。

顺序如下：

1, 11, 21, 1211, 111221, 312211...

在此序列中，每个术语都描述前一个术语。例如“1211”表示前一项；前一项是“21”，其中出现一次2，然后出现一次1 (=1211)。要得到第三项“21”，请查看第二项：11。1 出现两次，得到“21”。

import java.util.*;
class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
        System.out.println( Main.num(n-1, "1"));
  }
    public static String num(int times, String x){
        if(times == 0){
            return x;
        }else{
            //System.out.println("meow");
            String y = "" + x.charAt(0);
            int counter = 0;
            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 = 0;
                }
            }
            return num(times--, y);
        }
        //return "";
    }
}

我的代码使用递归来查找第 n 项。但是，它给了我们错误:(

首先，我通过向方法“num”传递 items-1 的数量（因为第一项已经给出）和第一项 (1) 开始。

在方法 num 中，我们首先使用条件来建立基本情况（当您找到第 n 项时）。

如果基本情况为假，则您将找到序列中的下一项。

Answer 1

这是一个非常酷的序列！我喜欢它是基于英语的而不是数学的，哈哈。（虽然现在我想知道......我们可以为第n项制定一个公式吗？我很确定这是不可能的，或者使用了一些疯狂的数学，但只是需要考虑一下......）

在您的解决方案中，代码的递归逻辑是正确的：找到每个项后，您使用已知的数字重复该方法，并使用该元素找到下一个项，并在确定第一个n元素时结束。您的基本情况也是正确的。

然而，您开发的用于确定序列中的项的算法是问题所在。

为了确定序列中的下一个元素，我们需要：

逻辑错误：

1. y为下一个元素创建一个空变量。但是，变量counter不应从 开始0。这是因为每个元素总是至少出现一次1，所以我们应该初始化int counter = 1;

2. 遍历 中的字符x。（您正确执行了此步骤）我们从 开始i = 1，因为我们将每个字符与前一个字符进行比较。

3. 如果当前字符等于前一个字符，我们就counter增加1。

4. 否则，我们将counter重复的字符连接到y。请记住，重新初始化counter为1，而不是0。

技术错误：

5. 一旦到达迭代结束x，我们需要将 Finalcounter和字符连接到y，因为 Final 字符的 else 语句永远不会在 for 循环中运行。

这是通过以下代码完成的：y += "" + counter + x.charAt(x.length() - 1);

6. 最后，当您进行递归调用时，您应该执行--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);
        }
    }
}

测试：

6
13112221

另一种方法是使用迭代方法：

import java.util.*;
class CoolSequence2 {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    ArrayList<String> nums = new ArrayList<String>();
    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));
  }
}

6
13112221

在此方法中，我们使用 for 循环来迭代n术语。为了确定每个元素，我们对您的逻辑执行类似的方法：

1. 我们创建一个空字符串val来保存新元素，并将当前元素存储在 中copy。我们还初始化 a cons，类似于您的counter.
2. 当copy不为空时，我们迭代copy并递增，cons直到有一个元素不等于下一个元素。
3. 发生这种情况时，我们将cons重复的元素连接到val，就像在您的代码中一样。然后，我们删除重复的元素copy并继续该过程。
4. 我们添加新值valto nums，并继续迭代n元素。

我希望这两种解决问题的方法对您有所帮助！如果您还有任何其他问题或需要说明，请告诉我:)