题解 | #百钱买百鸡问题#

思路

我假设公鸡、母鸡、小鸡各x、y、z只，那么满足下列条件：

x + y + z = 100

5x + 3y + z/3 = 100

我们将第2个等式两边x3，得到等式3:

15x + 9y + z = 300

再将等式3与等式1相减，得到：

14x + 8y = 200

即：

7x + 4y = 100

与等式1比较，可得：

7x + 4y = x + y + z

即：

z = 6x+3y

因此求解过程如下：

while let _ = readLine() {
    for x in 0 ..< 20 {
        for y in 0 ... 25 {
            if 7 * x + 4 * y  == 100 {
                let z = 6 * x  + 3 * y
                print("\(x) \(y) \(z)")
            }
        }
    }
}

优化

我们稍加变换可以得到：

7x = 100 - 4y

100-4y是个偶数，且一定能被4整除 7x也是偶数，且能被4整除，因7是个质数，故满足7x能被4整除的条件是，x是4的倍数，也就是x只能取0,4,8,12 不难发现，x最大只能取12。 而 y = (100 - 7x) / 4 z = 6x + 3y 因此，1次循环即可完成求解，代码如下：

for x in [0, 4, 8 , 12] {
    let y = (100 - 7 * x) / 4
    let z = 6 * x + 3 * y
    print("\(x) \(y) \(z)")
}

C语言代码如下：

for(int x = 0; x <= 12; x += 4) {
    int y = (100 - 7 * x) / 4;
    int z = 6 * x + 3 * y;
    printf("%d %d %d\n", x, y, z);
}

此解法的时间复杂度为：O(1).