鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？

——张丘建《算经》

这里从最最简单的算法开始一步一步讲如何优化，主要涉及的还是数学，Roger Bacon曾在《Opus Majus》写到

It is impossible to know things of this world unless you know mathematics.

——Roger Bacon《Opus Majus》

虽然这篇 post 会一直讲百鸡问题，但是主要还是想以此记录一些在解决某些问题是可能用到的数学思维，并不是只为了做百鸡问题。当然，我的数学也不怎么样qwq不过至少在这道题上，应用数学之后的算法在时间上的减少是比较明显的。

这篇 post 由以下几个部分构成

• 一个糟糕的实现
• 稍好一点的实现
• 再略微优化一点点
• 更好的算法
• 考虑多变量时的情况
• 总结

一个糟糕的实现

说到糟糕的实现，大概就是这样的吧，看完题目之后，就决定开始穷举

void chicken() {
    for (int a = 0; a <= 100; a++) {
        for (int b = 0; b <= 100; b++) {
            for (int c = 0; c <= 100; c++) {
                int amount = a + b + c;
                int cost = 15*a + 9*b + c;
                // 抱歉, 实在不忍心把这个版本写上来
                // int cost = 5*a + 3*b + c/3;
                // 这样写连算法的正确性都不能保证
                if (amount == 100 && cost == 300) {
                    printf("%d, %d, %d\n", a, b, c);
                }
            }
        }
    }
}

三重循环，每层都是100，于是最内层要跑100*100*100，也就是一百万次。如果这是才开始学的人写的程序，或许还能忍。这要是哪个程序猿／媛写的代码的话……反手就是一煤气罐

稍好一点的实现

那么稍好一点的实现是什么呢？稍微思考一下，不难得出，因为只有100元，所以即便是全部用来买鸡翁，也才100 / 5 = 20只，同理，全部用来买鸡母则是100 / 3 = 33只，虽然全部买鸡雏可以买到300只，但是题目要求是只能恰好100只。并且很简单的，我们知道因为一共100只，所以只要知道其中两种的确切数量，第三种就可以用100来减去已知的两种的数量得到。

整理成表达式的话就是

\begin{equation}
\left\{
\begin{aligned}
0\le a&\le 20\\
0\le b&\le 33\\
0\le c&\le 100\\
a + b &= 100 - c
\end{aligned}
\right.
\end{equation}

翻译到代码则是

void chicken() {
    for (int a = 0; a <= 20 /* 100 / 5 */; a++) {
        for (int b = 0; b <= 33 /* 100 / 3 */; b++) {
            int c = 100 - a - b;
            int cost = 15*a + 9*b + c;
            if (cost == 300) {
                printf("%d, %d, %d\n", a, b, c);
            }
        }
    }
}

这个算法有两层循环，最内层的部分将会运行21 * 34 = 714次，可以看到，从之前的 1000000 一下子就降到了 714，好几个数量级呢。

如果我们将“百元百鸡”的“百”看作是变量n的话，那么先前的算法的最内层运行了\(n^3\)次，复杂度也是\(O(n^3)\)，而现在的算法则是最内层运行\(\frac{n}{5}\frac{n}{3}=\frac{n^2}{15}\)次，复杂度为\(O(n^2)\)。

再略微优化一点点

那么既然引入了变量n，不如继续看看还有没有别的可优化的。比如这个变量c，因为题目中说“鸡雏三值钱一”，则必然变量c是3的倍数。我们可以先验证变量c，再去判断总花费是否符合要求。

void chicken(int n) {
    for (int a = 0; a <= 20 /* 100 / 5 */; a++) {
        for (int b = 0; b <= 33 /* 100 / 3 */; b++) {
            int c = n - a - b;
            if (c % 3 == 0) {
                int cost = 5*a + 3*b + c/3;
                if (cost == n) {
                    printf("%d, %d, %d\n", a, b, c);
                }
            }
        }
    }
}

在这个算法中，我们的确省掉了\(c\not=0\pmod{3}\)的情形，但是整体上仍旧是有两层循环，复杂度依旧是\(O(n^2)\)

更好的算法

可以看到，如果不再做更深入的数学上的分析的话，似乎很难提高算法的效率了。那么现在开始用一些数学的方法来一步一步地分析吧。

由“百鸡”可知

\begin{equation}
\label{constraints-1}
\left\{
\begin{aligned}
0\le a&\le n\\
0\le b&\le n\\
0\le c&\le n
\end{aligned}
\right.
\tag{1}
\end{equation}

再由“百钱买百鸡”有

\begin{equation}
\label{spend-amount}
\left\{
\begin{aligned}
5a+3b+\frac{c}{3}&=n\\
a+b+c&=n
\end{aligned}
\right.
\tag{2}
\end{equation}

由刚才我们讨论过的“鸡雏三值钱一”可知

\begin{equation}
c \equiv 0\pmod{3}
\tag{3}
\end{equation}

因为总的花费为\(n=5a+3b+\frac{c}{3}\)，故每一部分的上界都是\(n\)，即下列不等式

\begin{equation}
\label{constraints-2}
\left\{
\begin{aligned}
0\le a\le \lfloor\frac{n}{5}\rfloor\\
0\le b\le \lfloor\frac{n}{3}\rfloor\\
0\le c\le 3n
\end{aligned}
\right.
\tag{4}
\end{equation}

结合先前的限制条件 (1)，得到如下不等式

\begin{equation}
\label{constraints-final}
\left\{
\begin{aligned}
0&\le a\le \lfloor\frac{n}{5}\rfloor\\
0&\le b\le \lfloor\frac{n}{3}\rfloor\\
0&\le c\le n
\end{aligned}
\right.
\tag{5}
\end{equation}

现对式2变形

 
\begin{equation}
\label{spend-amount-variation}
\left\{
\begin{aligned}
5a+3b&=n-\frac{c}{3}\\
a+b&=n-c
\end{aligned}
\right.
\tag{6}
\end{equation}

消去变量\(b\)

\begin{equation}
\label{elminate-b}
\left\{
\begin{aligned}
15a + 9b &= 3n - c\\
9a + 9b &= 9n - 9c
\end{aligned}
\right.
\tag{7}
\end{equation}

\begin{equation}
\label{var-a}
a = -n + \frac{4}{3}c
\tag{8}
\end{equation}

由限制条件 (5)可得

\begin{equation}
\label{constraint-a}
0 \le -n + \frac{4}{3}c \le \lfloor\frac{n}{5}\rfloor
\tag{9}
\end{equation}

解得

\begin{equation}
\label{constraint-a-c}
\left\{
\begin{aligned}
\frac{3}{4}n &\le c\\
c &\le \frac{3}{4}\lfloor\frac{n}{5}\rfloor + \frac{3}{4}n
\end{aligned}
\right.
\tag{10}
\end{equation}

同理，消去变量\(a\)，得到关于\(c\)的不等式

\begin{equation}
\label{elminate-a}
\left\{
\begin{aligned}
15a + 9b &= 3n - c\\
15a + 15b &= 15n - 15c
\end{aligned}
\right.
\tag{11}
\end{equation}

\begin{equation}
\label{var-b}
b = 2n - \frac{7}{3}c
\tag{12}
\end{equation}

\begin{equation}
\label{constraint-b}
0 \le 2n - \frac{7}{3}c \le \lfloor\frac{n}{3}\rfloor
\tag{13}
\end{equation}

\begin{equation}
\label{constraint-b-c}
\left\{
\begin{aligned}
c &\le \frac{6}{7}n\\
\frac{6}{7}n - \frac{3}{7}\lfloor\frac{n}{3}\rfloor &\le c
\end{aligned}
\right.
\tag{14}
\end{equation}

最后，可由式(10)与式(14)确定\(c\)的范围

\begin{equation}
    \label{constraint-c-final}
    \left\{
        \begin{aligned}
            c &\le\text{min}(\frac{6}{7}n,\frac{3}{4}\lfloor\frac{n}{5}\rfloor + \frac{3}{4}n)\\
            c &\ge\text{max}(\frac{6}{7}n - \frac{3}{7}\lfloor\frac{n}{3}\rfloor, \frac{3}{4}n)
        \end{aligned}
    \right.
    \tag{15}
\end{equation}

因为\(c \equiv 0\pmod{3}\)，故分别将\(c\)的上下界调整为3的整倍数，调整方法如下

\begin{equation}
    \label{upper-lower-bound-adjustment}
    \left\{
        \begin{aligned}
            c_{upper} &= c_{upper} - (c_{upper} \mod{3})\\
            c_{lower} &= \left\{
                             \begin{aligned}
                                 c_{lower} + 3 - (c_{lower} \mod 3) \quad&\text{if }c_{lower} = 0 \pmod 3\\
                                 c_{lower}\quad&\text{ otherwise}
                             \end{aligned}
                         \right.
        \end{aligned}
    \right.
    \tag{16}
\end{equation}

随后从\(c_{lower}\)开始循环，每次增加3，直到\(c\)等于\(c_{upper}\)。循环体内，通过式(8)、式(12)计算\(a,b\)的值即可。

因为向下取整在C++中与两个整数类型的变量相除等价，故式(15)可重写为

\begin{equation}
\label{constraint-c-computer}
\left\{
\begin{aligned}
c &\le\text{min}(\frac{6}{7}n,\frac{9}{10}n)\\
c &\ge\text{max}(\frac{5}{7}n, \frac{3}{4}n)
\end{aligned}
\right.
\end{equation}

显然的有

\begin{equation}
\left\{
\begin{aligned}
c &\le\frac{6}{7}n\\
c &\ge\frac{3}{4}n
\end{aligned}
\right.
\end{equation}

最后，C++代码实现如下

#include <stdio.h>
#include <iostream>

void chicken(int n) {
    int c = 3*n/4;
    if (c % 3 != 0) c += 3 - c % 3;
    int c_upper = 6*n/7;
    c_upper -= c_upper % 3;
    for (; c <= c_upper; c += 3) {
        // 因为整除的原因
        // 需要判断a的值是否小于0
        int a = 4*c/3 - n;
        if (a < 0) continue;
        printf("%d, %d, %d\n", a, 2*n - 7*c/3, c);
    }
}

int main(int argc, const char * argv[]) {
    chicken(100);
}

现在，我们的算法中只有一个循环了，

\begin{equation}
\begin{aligned}
&\frac{c_{upper} - c_{lower}}{3}\\
=&\frac{\frac{6}{7}n - \frac{3}{4}n}{3}\\
=&\frac{\frac{3}{28}n}{3}\\
=&\frac{n}{28}
\end{aligned}
\end{equation}

循环部分共执行了\(\frac{n}{28}\)次，于是这个算法的复杂度是\(O(n)\)

多变量时的情况

首先我们来定义变量，

• \(n\)，总花费、总购买只数
• \(x\)，鸡翁价格
• \(y\)，鸡母价格
• \(z\)，鸡雏价格
• \(p\)，每\(x\)元可买\(p\)只鸡翁
• \(q\)，每\(y\)元可买\(q\)只鸡母
• \(w\)，每\(z\)元可买\(w\)只鸡雏

最后，目标是求

• \(a\)，购买\(a\)只鸡翁
• \(b\)，购买\(b\)只鸡母
• \(c\)，购买\(c\)只鸡雏

同样的，由“百鸡”这一信息有

\begin{equation}
\label{constraints-1-multi}
\left\{
\begin{aligned}
0&\le \frac{a}{p}x\le n\\
0&\le \frac{b}{q}y\le n\\
0&\le \frac{c}{w}z\le n
\end{aligned}
\right.
\tag{17}
\end{equation}

“百钱买百鸡”

 
\begin{equation}
\label{spend-amount-multi}
\left\{
\begin{aligned}
\frac{a}{p}x+\frac{b}{q}y+\frac{c}{w}z&=n\\
a+b+c&=n
\end{aligned}
\right.
\tag{18}
\end{equation}

类似的，由“鸡雏三值钱一”可知

\begin{equation}
\label{constraint-multi}
\left\{
\begin{aligned}
a &\equiv 0\pmod{p}\\
b &\equiv 0\pmod{q}\\
c &\equiv 0\pmod{w}
\end{aligned}
\right.
\tag{19}
\end{equation}

对式18变形，得到

\begin{equation}
\label{spend-amount-variation-multi}
\left\{
\begin{aligned}
\frac{a}{p}x+\frac{b}{q}y&=n-\frac{c}{w}z\\
a+b&=n-c
\end{aligned}
\right.
\tag{20}
\end{equation}

消去变量\(b\)

\begin{equation}
\label{elminate-b-multi}
\left\{
\begin{aligned}
\frac{a}{p}x+\frac{b}{q}y&=n-\frac{c}{w}z\\
\frac{y}{q}a+\frac{y}{q}b&=\frac{y}{q}n-\frac{y}{q}c
\end{aligned}
\right.
\tag{21}
\end{equation}

化简得到\(a\)关于\(c\)的表达式

\begin{equation}
    \label{var-a-multi}
    \begin{aligned}
        \frac{ya}{q}-\frac{ax}{p}&=(\frac{y}{q}-1)n-(\frac{y}{q}c-\frac{c}{w}z)\\
        \frac{yap-axq}{pq}&=\frac{y-q}{q}n-\frac{ycw-zcq}{wq}\\
        yap-axq&=pn(y-q)-\frac{pycw-pzcq}{w}\\
        a(yp-xq)&=pn(y-q)-\frac{pycw-pzcq}{w}\\
        a&=\frac{pn(y-q)}{yp-xq}-\frac{pc(yw-zq)}{w(yp-xq)}
    \end{aligned}
    \tag{22}
\end{equation}

同样的，消去变量\(a\)

\begin{equation}
\label{elminate-a-multi}
\left\{
\begin{aligned}
\frac{a}{p}x+\frac{b}{q}y&=n-\frac{c}{w}z\\
\frac{x}{p}a+\frac{x}{p}b&=\frac{x}{p}n-\frac{x}{p}c
\end{aligned}
\right.
\tag{23}
\end{equation}

化简得到\(b\)关于\(c\)的表达式

\begin{equation}
    \label{var-b-multi}
    \begin{aligned}
        \frac{xb}{p}-\frac{yb}{q}&=(\frac{x}{p}-1)n-(\frac{x}{p}c-\frac{z}{w}c)\\
        \frac{xbq-ybp}{pq}&=\frac{x-p}{p}n-\frac{xcw-zcp}{wq}\\
        xbq-ybp&=qn(x-p)-\frac{qxcw-qzcp}{w}\\
        b(xq-yp)&=qn(x-p)-\frac{qxcw-qzcp}{w}\\
        b&=\frac{qn(x-p)}{xq-yp}-\frac{qc(xw-zp)}{w(xq-yp)}
    \end{aligned}
    \tag{24}
\end{equation}

此时对变量\(c\)迭代即可得出\(a,b\)

C++代码实现如下

#include <iostream>
#include <tuple>
#include <vector>

/**
 *  百鸡问题
 *  @param n    总花费、总购买只数
 *  @param x    鸡翁价格
 *  @param y    鸡母价格
 *  @param z    鸡雏价格
 *  @param p    每\(x\)元可买\(p\)只鸡翁
 *  @param q    每\(y\)元可买\(q\)只鸡母
 *  @param w    每\(z\)元可买\(w\)只鸡雏
 *  @return     [(a, b, c)] 在给定条件下的所有可行购买方案
 */
std::vector<std::tuple<int,int,int>> chicken(int n, int x, int y, int z, int p, int q, int w) {
    std::vector<std::tuple<int,int,int>> result;
    for (int c = 0; c <= n; c += w) {
        // \(a=\frac{pn(y-q)}{yp-xq}-\frac{pc(yw-zq)}{w(yp-xq)}\)
        int a = (p*n*(y-q))/(p*y-q*x) - p*c*(y*w-z*q)/(w*(p*y-q*x));
        if (a < 0) continue;
        // \(b=\frac{qn(x-p)}{xq-yp}-\frac{qc(xw-zp)}{w(xq-yp)}\)
        int b = (q*n*(x-p))/(q*x-p*y) - q*c*(x*w-z*p)/(w*(q*x-p*y));
        if (b >= 0) result.emplace_back(a,b,c);
    }
    return result;
}

int main(int argc, const char * argv[]) {
    int a,b,c;
    for (auto p : chicken(100, 5, 3, 1, 1, 1, 3)) {
        std::tie(a,b,c) = p;
        std::cout << a << ", " << b << ", " << c << '\n';
    }
}

总结

可以看到，解决百鸡问题，算法的复杂度从完全不带脑子的\(O(n^3)\)，到思考之后的\(O(n^2)\)，再降到利用数学作为工具分析之后的\(O(n)\)。当时，一般写出来会是\(O(n^2)\)的复杂度，但是也别小看\(O(n^2)\)到\(O(n)\)的差距，当规模n变到足够大的时候，时间上的差异将会是相当惊人的。

（即便如此，最后提出的这个算法也不见得是最优的QAQ）