python百钱买百鸡问题算法_经典算法题--百钱买百鸡百钱买百鸡的问题算是⼀套⾮常经典的不定⽅程的问题，题⽬很简单：
公鸡5⽂钱⼀只，母鸡3⽂钱⼀只，⼩鸡3只⼀⽂钱，⽤100⽂钱买⼀百只鸡，其中公鸡，母鸡，⼩鸡都必须要有。
问：公鸡，母鸡，⼩鸡要买多少只刚好凑⾜100⽂钱。
分析：估计现在⼩学⽣都能⼿⼯推算这套题，只不过我们⽤计算机来推算，我们可以设公鸡为x，母鸡为y，⼩鸡为z，
那么我们可以得出如下的不定⽅程，
x+y+z=100, ①
5x+3y+z/3=100， ②
①代表100鸡和②代表100钱。
下⾯再看看x，y，z的取值范围。
由于只有100⽂钱，则5x<100 => 0
好，我们已经分析清楚了，下⾯就可以编码了。
usingSystem;usingSystem.Collections.Generic;public classMyClass
{public static voidMain()
{//公鸡的上线
for (int x = 0; x < 20; x++)
{//母鸡的上线
for (int y = 0; y < 33; y++)
{//剩余⼩鸡
int z = 100 - x -y;if ((z % 3 == 0) && (x * 5 + y * 3 + z / 3 == 100))
{
System.Console.WriteLine("公鸡:{0}只，母鸡:{1}只,⼩鸡:{2}只", x, y, z);
}
}
}
Console.ReadLine();
}
}
结果出来了，确实这道题⾮常简单，我们要知道⽬前的时间复杂度是O(N2)，实际应⽤中这个复杂度是不能让你接受的，最多最多能让
⼈接受的是O(N)。
所以说我们必须要优化⼀下，从结果中我们可以发现这样的⼀个规律：公鸡是4的倍数，母鸡是7的递减率，⼩鸡是3的递增率，规律哪⾥
来，肯定需要我们推算⼀下这个不定⽅程。
x+y+z=100 ①
5x+3y+z/3=100 ②
令②x3-① 可得
7x+4y=100
=>y=25-(7/4)x ③
⼜因为0
=> x=4k ④
将④代⼊③可得
=> y=25-7k ⑤
将④⑤代⼊①可知
=> z=75+3k ⑥
根据上⾯得出的 ④⑤⑥ 式⼦求K的区间，要保证0
0<4k<100
0<25-7k<100
0<75+3k<100
满⾜上⾯的三个式⼦，k的取值范围只能是1,2,3，下⾯我们继续上代码。
usingSystem;usingSystem.Collections.Generic;public classMyClass
{public static voidMain()
{intx, y, z;for (int k = 0; k <= 3; k++)
{
x= 4 *k;
y= 25 - 7 *k;
z= 75 + 3 *k;
Console.WriteLine("公鸡:{0}只，母鸡:{1}只,⼩鸡:{2}只", x, y, z);
}
Console.ReadLine();writeline使用方法python
}
}
这⼀次我们做到了O(N)的时间复杂度，很不错，起码优化到了我能接受的范围内，或许我们感觉到了数学的魅⼒，是的，因为....数学是科学的皇后。皇上⾃然就是物理了...

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。