# 从百鸡问题到数学思维

——张丘建《算经》

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

——Roger Bacon《Opus Majus》

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);
}
}
}
}
}

\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.

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);
}
}
}
}

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);
}
}
}
}
}

\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}

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

c \equiv 0\pmod{3}
\tag{3}

\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}

\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}

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

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

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

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

\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}

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

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

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

\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}

\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}


\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}


\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.

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

#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{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}

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

• $a$，购买$a$只鸡翁
• $b$，购买$b$只鸡母
• $c$，购买$c$只鸡雏

\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}

“百钱买百鸡”

\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}

\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}

\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}

\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}

\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}


\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}

\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}


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';
}
}

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

声明: 本文为0xBBC原创, 转载注明出处喵～

## 9 thoughts on “从百鸡问题到数学思维”

1. 瘾瘾说道：

为什么我没有头像 ┭┮﹏┭┮

1. 0xBBC说道：

在 gavatar 用你的邮箱注册上传就有了

2. 你的博客使用的wordpress还是typecho？竟然让我用出了静态博客的感觉……

1. 这评论我的头像显示出来了看样子是wordpress……

2. 0xBBC说道：

诶嘿嘿，是wordpress噢/

3. 不过……
O(n)复杂度的算法灵活性差了一些
如果想改变鸡的价格的话，还要重新推算一遍_(:3 」∠)_
因为公式挂掉了，看起来比较蛋疼……不太确定 Σ( ° △ °|||)︴
还有可读性也下降了_(:3 」∠)_

1. 0xBBC说道：

其实这篇 post 只是为了说明应用数学之后，原来看似不好再优化的算法，也许还有不小的提升空间，，
另外公式没问题，大概是你那边加载不了 cdn.mathjax.com 的内容