如何对格斗场次计算的Backward recursion递归函数做反向求解

逆运算实现思路 #

原正向计算函数qwe(n)是严格递增函数，所有初始人数n都可以拆成 n = k * 2^m（k为奇数，m为非负整数），对应总场次公式展开为：

s = k*(2^m -1) + k*(k-1)/2

基于这个规律可以通过两种方式实现逆运算，以下是可直接运行的JS实现：

方式1：枚举法（逻辑最简单，不易出错） #

利用正向函数单调递增的特性，从小到大遍历可能的初始人数，直到计算出的总场次匹配目标值即可。

// 原正向计算函数
function qwe(number) {
  if(number % 2) {
    return number * (number - 1) / 2
  } else {
    const half = number / 2; 
    return half + qwe(half)
  }
}

// 逆运算：输入总场次s，返回所有符合的初始人数数组
function reverseQwe(s) {
  const solutions = []
  let n = 1
  while(true) {
    const current = qwe(n)
    if(current === s) solutions.push(n)
    if(current > s) break
    n++
  }
  return solutions
}

// 测试用例
console.log(reverseQwe(3)) // 输出 [3,4] 两个解
console.log(reverseQwe(6)) // 输出 [6]
console.log(reverseQwe(10)) // 输出 [5]

方式2：递归法（效率更高，无需重复计算正向值） #

直接基于推导的公式递归查找所有符合条件的k和m组合：

function reverseQweRecursive(s, multiple = 1, solutions = []) {
  // 校验当前s是否对应奇数k的单循环场次
  const discriminant = 1 + 8 * s;
  const sqrtD = Math.sqrt(discriminant);
  if (Number.isInteger(sqrtD)) {
    const k = (1 + sqrtD) / 2;
    if (k % 2 === 1) {
      solutions.push(k * multiple);
    }
  }
  // 递归边界：剩余场次不足时停止
  if (s - multiple < 0) return solutions;
  // 进入下一层2的倍数计算
  return reverseQweRecursive(s - multiple, multiple * 2, solutions);
}

// 测试用例
console.log(reverseQweRecursive(3)) // 输出 [3,4]
console.log(reverseQweRecursive(6)) // 输出 [6]
console.log(reverseQweRecursive(10)) // 输出 [5]

补充说明 #

部分总场次会对应多个合法初始人数，比如总场次为3时，3人（奇数直接单循环打3场）和4人（两两对战2场剩2人，再打1场剩1人结束，总场次3）都是合法解，上述两个实现都会返回所有符合的结果，如果只需要最小/最大解，返回对应位置的元素即可。

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