RStudio中Collatz猜想序列的回溯检测问题

需求说明 #

针对1至10000的Collatz猜想tibble数据，检测其中是否存在回溯序列，定义为：序列降至起始整数以下后，又至少一次升至起始整数以上，最终到达1。

现有数据示例 #

structure(list(start = 1:6, seq = list(1L, c(2, 1), c(3, 10, 
5, 16, 8, 4, 2, 1), c(4, 2, 1), c(5, 16, 8, 4, 2, 1), c(6, 3, 
10, 5, 16, 8, 4, 2, 1)), length = c(1, 2, 8, 3, 6, 9), parity = c("Odd", 
"Even", "Odd", "Even", "Odd", "Even"), max_val = c(1, 2, 16, 
4, 16, 16)), row.names = c(NA, -6L), class = c("tbl_df", "tbl", 
"data.frame"))

当前代码问题 #

现有实现仅能检测序列是否出现上升，无法判断是否升至起始值以上，不符合回溯序列的定义：

has_backtrack <- function(seq) {
  length_seq <- length(seq)
  if (length_seq < 3) {
    return(FALSE)
  }
  for (i in 2:(length_seq - 1)) {
    if (seq[i] < seq[1] && seq[i + 1] > seq[i]) {
      return(TRUE)
    }
  }
}

修正后的代码 #

has_backtrack <- function(seq) {
  start_val <- seq[1]
  length_seq <- length(seq)
  
  # 序列过短，无法完成"降-升"的回溯过程
  if (length_seq < 3) {
    return(FALSE)
  }
  
  # 标记是否已降至起始值以下
  dropped_below <- FALSE
  
  for (val in seq[-1]) {
    if (!dropped_below) {
      # 先检查是否降到起始值以下
      if (val < start_val) {
        dropped_below <- TRUE
      }
    } else {
      # 已降到过起始值以下，检查是否回升到起始值以上
      if (val > start_val) {
        return(TRUE)
      }
    }
  }
  
  # 遍历完序列未满足回溯条件
  return(FALSE)
}

逻辑说明 #

• 先记录起始值start_val，序列长度小于3时直接返回FALSE（无法完成"降-升"的回溯流程）
• 用dropped_below标记序列是否出现过低于起始值的元素
• 遍历序列后续元素：
  • 未触发dropped_below时，只要遇到小于起始值的元素，就将标记设为TRUE
  • 标记为TRUE后，一旦遇到大于起始值的元素，立即返回TRUE（符合回溯定义）
• 若遍历结束未触发返回TRUE，则返回FALSE

测试验证 #

用现有数据示例测试：

• 起始值为6的序列：c(6, 3, 10, 5, 16, 8, 4, 2, 1)，先降到3（小于6），之后升到10（大于6），函数返回TRUE
• 起始值为3的序列：c(3,10,5,...)，第一个元素10大于3，从未降到起始值以下，返回FALSE
• 起始值为5的序列：c(5,16,...)，全程未低于5，返回FALSE

内容的提问来源于stack exchange，提问作者user22623213