100 元买 100 只，题目：公鸡 5 元一只、母鸡 3 元一只、小鸡 1 元三只求 100 元买一百只，各可以买几只三个变量：公鸡数量为 x 母鸡数量为 y 小鸡数量为 z 满足条件：①：x+y+z=100 ②：5x+3y+z/3=100 以上为计算题目得出方程
/**
* 公鸡 5 元一只、母鸡 3 元一只、小鸡 1 元三只
* 求 100 元买一百只，各可以买几只
* 三个变量：公鸡数量为 x 母鸡数量为 y 小鸡数量为 z
* 满足条件：x+y+z=100 5x+3y+z/3=100
* 以上为计算题目得出方程
*/
void bj(int amount, int num) {
int x, y, z = 0;
// 公鸡数量
for (x = 0; x <= num; x++) {
// 母鸡数量
for (y = 0; y <= num; y++) {
// 小鸡数量
z = num – x – y;
// 满足条件的
if (z % 3 == 0 && x * 5 + y * 3 + z / 3 == amount) {
printf(“ 公鸡：%d, 母鸡：%d, 小鸡：%d\n”, x, y, z);
}
}
}
}
int main(){
bj(100,100);
return 0;
}
以上不是最优的办法，因为最外层循环了 num 次，第二层循环也循环了 num 次，这里可以得到一部分优化
void bj(int amount, int num) {
int x, y, z = 0;
// 公鸡数量
for (x = 0; x <= num / 5; x++) {
// 母鸡数量
for (y = 0; y <= num / 3; y++) {
// 小鸡数量
z = num – x – y;
// 满足条件的
if (z % 3 == 0 && x * 5 + y * 3 + z / 3 == amount) {
printf(“ 公鸡：%d, 母鸡：%d, 小鸡：%d\n”, x, y, z);
}
}
}
}
int main() {
bj(100, 100);
return 0;
}
这样的优化我们不必需要两个循环都循环 num 次了，只要循环符合 amount 的最大数，这样可以避免过多不必要的循环。这样就是最优的解法了吗？当然不是，我们这里可以看到时间复杂度是：O(N2)，那我们有没有办法优化到 O(N) 呢？
我们来看看结果：
公鸡：0, 母鸡：25, 小鸡：75 公鸡：4, 母鸡：18, 小鸡：78 公鸡：8, 母鸡：11, 小鸡：81 公鸡：12, 母鸡：4, 小鸡：84
我们来找一下规律，在这四条结果中，公鸡的规律是 4 的倍数，母鸡是 7 的递减，小鸡是 3 的递增。我们还记得在一开始的时候提到的方程组：①：x+y+z=100 ②：5x+3y+z/3=100 上面两个方程组，有三个未知变量，为不定方程组令②×3-①得：7x+4y=100 由 x+y+z = 100 和 5x + 3y + z/3 = 100 可得 7x+4y=100 则 y = 25 -（7/4）X 再令 x = 4k，则有 y = 25 – 7k，继而 z = 75 + 3k 因为 0 =< z <= 100，所以 k 的可能取值是 0，1，2，3
void bj(int amount, int num) {
int x, y, z = 0;
for (int k = 1; k <= 3; k++) {
x = 4*k;
y = 25-7*k;
z = 75+3*k;
printf(“ 公鸡：%d, 母鸡：%d, 小鸡：%d\n”, x, y, z);
}
}
int main() {
bj(100, 100);
return 0;
}
以上的时间复杂度就可以为 O(N)