(B卷,100分)- 数列描述（Java & JS & Python）

题目描述

有一个数列a[N] (N=60)，从a[0]开始，每一项都是一个数字。数列中a[n+1]都是a[n]的描述。其中a[0]=1。规则如下：

• a[0]:1
• a[1]:11(含义：其前一项a[0]=1是1个1，即“11”。表示a[0]从左到右，连续出现了1次“1”）
• a[2]:21(含义：其前一项a[1]=11，从左到右：是由两个1组成，即“21”。表示a[1]从左到右，连续出现了两次“1”)
• a[3]:1211(含义：其前一项a[2]=21，从左到右：是由一个2和一个1组成，即“1211”。表示a[2]从左到右，连续出现了1次“2”，然后又连续出现了1次“1”)
• a[4]:111221(含义：其前一项a[3]=1211，从左到右：是由一个1、一个2、两个1组成，即“111221”。表示a[3]从左到右，连续出现了1次“1”，连续出现了1次“2”，连续出现了两次“1”)

请输出这个数列的第n项结果（a[n]，0≤n≤59）。

输入描述

数列的第n项(0≤n≤59)

4

输出描述

数列的内容

111221

用例

题目解析

这题是一个典型的动态规划题目，因为它存在明显的：下一个阶段状态依赖于上一个阶段状态，存在状态转移。

这题难点在于找状态转移方程，即上一个状态与上一个状态之间的变化关系，按照题目意思应该是一种描述关系。即下一个状态是对于上一个状态的描述。

我这边实现：比如上一个状态是1211，则将其转为字符数组arr，取出第0个字符缓存到变量val中，并定义一个变量count，用于记录val字符出现的次数。

然后开始遍历字符数组，从第1个开始遍历，比较arr[0]和arr[1]，如果相同，则count++，如果不同，则输出描述count + "" + val，然后将arr[1]作为新的val，并且count重置为1，接着比较arr[1]和arr[2]，逻辑如上。

JS算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const n = parseInt(line);
  console.log(getSeq(n));
});

/* 算法逻辑 */
function getSeq(n) {
  let base = "1";
  for (let i = 1; i <= n; i++) {
    base = describe(base);
  }
  return base;
}

function describe(seq) {
  let res = [];

  let count = 1;
  let val = seq[0];
  for (let i = 1; i < seq.length; i++) {
    if (seq[i] === seq[i - 1]) {
      count++;
    } else {
      res.push(count);
      res.push(val);
      count = 1;
      val = seq[i];
    }
  }
  res.push(count);
  res.push(val);
  return res.join("");
}

Java算法源码

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    System.out.println(getSeq(n));
  }

  public static String getSeq(int n) {
    String base = "1";
    for (int i = 1; i <= n; i++) {
      base = describe(base);
    }
    return base;
  }

  public static String describe(String seq) {
    StringBuilder sb = new StringBuilder();

    int count = 1;
    char val = seq.charAt(0);

    for (int i = 1; i < seq.length(); i++) {
      if (seq.charAt(i) == seq.charAt(i - 1)) {
        count++;
      } else {
        sb.append(count).append(val);
        count = 1;
        val = seq.charAt(i);
      }
    }
    sb.append(count).append(val);
    return sb.toString();
  }
}

Python算法源码

# 输入获取
n = int(input())


def describe(seq):
    res = []

    count = 1
    val = seq[0]

    for i in range(1, len(seq)):
        if seq[i] == seq[i - 1]:
            count += 1
        else:
            res.append(count)
            res.append(val)
            count = 1
            val = seq[i]

    res.append(count)
    res.append(val)
    return "".join(map(str, res))


# 算法入口
def getResult():
    base = "1"
    for i in range(1, n + 1):
        base = describe(base)
    return base


# 算法调用
print(getResult())