鸡兔同笼

2016-01-11

《孙子算经》：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？

穷举法

穷举是一种暴力搜索方法，通过检查每一个可能来寻找问题的解，实现方法有循环和递归。不要把穷举等同于循环，前者是计算机解决问题的一种方法，后者是一种编程结构。

  • 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function solveChickenRabbitProblem(totalHeaders, totalFoots, rabbits = 0) {
    const chickens = totalHeaders - rabbits
    // 无需判断 rabbits + chickens === totalHeaders
    if (rabbits >= 0 && chickens >= 0 && 4 * rabbits + 2 * chickens === totalFoots) {
      return {
        rabbits,
        chickens
      }
    }
    // 增加兔子的数量，检查下一个可能的解（从 totalFoots 开始减少一样）
    if (rabbits < totalFoots) {
      return solveChickenRabbitProblem(totalHeaders, totalFoots, rabbits + 1)
    }
    // 无解
    return null
}

solveChickenRabbitProblem(35, 94)
  • 循环
1
2
3
4
5
6
7
8
9
10
11
12
13
function solveChickenRabbitProblem(totalHeaders, totalFoots) {
  for (let rabbits = 0; rabbits <= totalHeaders; rabbits++) {
    for (let chickens = 0; chickens <= totalHeaders - rabbits; chickens++) {
      if (rabbits + chickens === totalHeaders && 4 * rabbits + 2 * chickens === totalFoots) {
        return {
          rabbits,
          chickens
        }
      }
      return null
    }
  }
}

代数法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function solveChickenRabbitProblem(totalHeads, totalFoots) {
  // 假设鸡的数量为 x，兔的数量为 y
  // 构建方程组
  // x + y = totalHeads
  // 2x + 4y = totalFoots
  for (let x = 0; x <= totalHeads; x++) {
    let y = totalHeads - x
    if (2 * x + 4 * y === totalFoots) {
      return { 
        chickens: x,
        rabbits: y
      }
    }
  }
  return null // 无解
}

逻辑法

  • 抬脚法
1
2
3
4
5
6
7
8
9
10
11
function solveChickenRabbitProblem(totalHeads, totalFoots) {
  const restFoots = totalFoots / 2 // 第一次抬脚
  const rabbits = restFoots - totalHeads // 第二次抬脚

  return {
    rabbits,
    chickens: totalHeads - rabbits
  }
}

solveChickenRabbitProblem(35, 94)

解法思路：第一次抬脚，兔子抬 2 只，鸡抬 1 只，第二次抬脚，兔和鸡都抬 1 只，这时候兔子还站着，鸡已经坐下来。

1
2
3
4
5
6
7
8
9
function solveChickenRabbitProblem(totalHeads, totalFoots) {
  const restFoots = totalFoots - totalHeads * 2
  const rabbits = restFoots / 2

  return {
    rabbits,
    chickens: totalHeads - rabbits
  }
}

解法思路：第一次抬脚，鸡和兔都抬 1 只，第二次抬脚，鸡和兔再都抬 1 只，这时兔子还剩下 2 只脚站着，鸡已经坐下来。

  • 假设法

假设兔子只有两只脚。

1
2
3
4
5
6
7
8
9
10
11
function solveChickenRabbitProblem(totalHeads, totalFoots) {
  const rabbits = (totalFoots - 2 * totalHeads) / 2
  const chickens = totalHeads - rabbits

  return {
    chickens,
    rabbits
  }
}

solveChickenRabbitProblem(35, 94)

解法思路：假设兔子只有两条腿，那么一共有 k 个头就一共有 2k 只脚，totalFoots-2k 就是剩下的脚，而这些脚应该是兔子多出来的脚，每个兔子多两只脚，所以兔子就有 (totalFoots-2k)/2 只，鸡就不言而喻了。