鸡兔同笼问题时间复杂度的演进

发表于

鸡兔同笼，是中国古代著名典型趣题之一，记载于《孙子算经》之中。这四句话的意思是：有若干只鸡兔同在一个笼子里，从上面数，有35个头，从下面数，有94只脚。问笼中各有多少只鸡和兔？下面我们将从时间复杂度的角度来演进代码。

O(n^2)

下面的代码大家应该都能看懂，我们使用双层循环进行遍历，把x当成鸡的数量，把y当初兔子的数量。根据鸡有两条腿，兔子有4条腿的计算规则，那么很容易得出x + y == 35 and 2 * x + 4 * y == 94这个数学公式，经过暴力遍历，我们就可以求出鸡和兔子的数量了。

1
2
3
4
5
scss复制代码def check1():
    for x in range(1, 36):
        for y in range(1, 36):
            if x + y == 35 and 2 * x + 4 * y == 94:
                print(x, y)

O(n)

现在我们转变思路，根据我们初中学习的二元一次方程可以得知，当我们设鸡为x时，那么兔子的数量便为35-x,同样我们根据鸡有两条腿，兔子有4条腿的计算规则，此时我们只需要一层遍历就可以解决问题，并且时间复杂度很好的控制在了一个线性阶。

1
2
3
4
5
6
arduino复制代码def check2():
    x = 35
    for i in range(1, x + 1):
        if 2 * i + 4 * (35 - i) == 94:
            print(i, 35 - i, i)
            break

O(1)

咋一看下面的代码可能有点懵，现在我们来解释一下。为什么使用头的数量（35）乘2呢？我们来考虑一个极端方向，就是一共有35个头，那么我们把这35个都先当成鸡，因为鸡有两条退。那么此时35*2=70,但是我们还有一个前提条件94条腿，此时94-70=24,那么这24条腿只能兔子的，我们在将24 / 2= 12，即为兔子的数量。那么此法即为抬腿法：假设鸡和兔子都抬起2只脚，所有抬起的脚：35×2=70只，那么地上剩余的脚：94-70=24只，此时地上的脚只能是兔子的脚（因为鸡的脚已经抬完了），而且每只兔子有2只脚着地。

1
2
3
4
5
ini复制代码def check3():
    x = (94 - 35 * 2) / 2
    y = 35 - x
    if int(x) == x:
        print(x, y)

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%