solve is computing how many chicks (1 head, 2 legs) and how many pigs (1 head, 4 legs) it takes to total up to the given numbers of heads and legs.
It uses a "brute force", that is, maximally simple, approach:
it tries even possible number of chicks from none at all to as many as was specified as number of heads (that's the role of the loop for numChicks in range(0, numHeads + 1):, since range gives integers from the starting value included to the ending value excluded);
for each given numChicks it computes how many pigs there would be to give the requested number of heads, by the statement numPigs = numHeads - numChicks
then it computes how many total legs those chicks and pigs would have, by totLegs = 4*numPigs + 2*numChicks
then it checks if the totLegs equal the requested number: if so, it returns a list with two items, the numbers of chicks and pigs that solve the problem
lastly, if it "falls of the bottom" of the for loop without having returned a value yet, it knows there's no solution, and signifies that by returning a list each of whose two items is None.
barnYard just delegates the solution to solve, and prints it out in a nice readable way, either as "no solution" or as nicely decorated numbers of chicks and pigs.
Now, to keep progressing, ask yourself if solve could be written more efficiently. Clearly there is no solution if the number of legs is less than twice the number of heads, or more than four times the number of heads, or odd -- maybe solve could test for those case and return [None, None] immediately. Could you code that...?
It may not be obvious, but every other combination of numbers of heads and legs has a solution -- and there IS a way to find it just by arithmetic, without looping. Think about it, maybe with the help of elementary middle-school algebra...
H = C + P
=> 0 = C + P - H [subtract H from both sides]
=> 0 = H - C - P [multiply both sides by -1]
=> P = H - C [add P to both sides] (3)
并将其代入（2）：
L = 2C + 4P
=> L = 2C + 4(H - C) [substitute H-C for P]
=> L = 2C + 4H - 4C [expand 4(H-C) to 4H-4C]
=> L = 4H - 2C [combine 2C-4C into -2C]
=> 0 = 4H - 2C - L [subtract L from both sides]
=> 2C = 4H - L [add 2C to both sides]
=> C = 2H - L/2 [divide both sides by 2] (4)
import sys
def usage (reason):
print "Error: %s"%(reason)
print "Usage: solve <numHeads> <numLegs>"
sys.exit (1);
def solve1 (numLegs, numHeads):
for numChicks in range (0, numHeads + 1):
numPigs = numHeads - numChicks
totLegs = 4 * numPigs + 2 * numChicks
if totLegs == numLegs:
return [numPigs, numChicks]
return [None, None]
def solve2 (numLegs, numHeads):
chicks = numHeads * 2 - int (numLegs / 2)
pigs = numHeads - chicks
if chicks < 0 or pigs < 0: return [None, None]
if chicks * 2 + pigs * 4 != numLegs: return [None, None]
if chicks + pigs != numHeads: return [None, None]
return [pigs, chicks]
if len (sys.argv) != 3:
usage ("Wrong number of parameters (%d)"%(len (sys.argv)))
try: heads = int (sys.argv[1])
except: usage ("Invalid <numHeads> of '%s'"%(sys.argv[1]))
try: legs = int (sys.argv[2])
except: usage ("Invalid <numLegs> of '%s'"%(sys.argv[2]))
print "[pigs, chicks]:"
print " ", solve1 (legs, heads)
print " ", solve2 (legs, heads)
Alex Martelli alludes to an algebraic solution which I'll include here for completeness. It can be worked out with the use of simultaneous equations. Being a simple mathematical solution, it's possibly faster, at least for large numbers of legs and heads :-)
Let:
H be the number of heads;
L be the number of legs;
C be the number of chicks; and
P be the number of pigs.
Given C and P, we can calculate the other two variables with:
H = C + P (1)
L = 2C + 4P (2)
I'll detail every step in the calculations below. The mathematically inclined can no doubt point out that steps could be combined but I'd prefer to be explicit. From (1), we can calculate:
H = C + P
=> 0 = C + P - H [subtract H from both sides]
=> 0 = H - C - P [multiply both sides by -1]
=> P = H - C [add P to both sides] (3)
and substitute that into (2):
L = 2C + 4P
=> L = 2C + 4(H - C) [substitute H-C for P]
=> L = 2C + 4H - 4C [expand 4(H-C) to 4H-4C]
=> L = 4H - 2C [combine 2C-4C into -2C]
=> 0 = 4H - 2C - L [subtract L from both sides]
=> 2C = 4H - L [add 2C to both sides]
=> C = 2H - L/2 [divide both sides by 2] (4)
Now you have two formulae, one that can calculate the number of chicks from head and legs (4), the other which can calculate number of pigs from chicks and heads (3).
So here's the Python code to do it, with appropriate checks to ensure you don't allow some of the more bizarre mathematical solutions, like 2 heads and 7 legs giving us a pig and a half along with half a chick, or 1 head and 12 legs giving 5 pigs and -4 chicks :-)
def solve (numLegs, numHeads):
# Use the formulae (these make integers).
chicks = numHeads * 2 - int (numLegs / 2)
pigs = numHeads - chicks
# Don't allow negative number of animals.
if chicks < 0 or pigs < 0:
return [None, None]
# Don't allow fractional animals.
if chicks * 2 + pigs * 4 != numLegs:
return [None, None]
if chicks + pigs != numHeads:
return [None, None]
return [pigs, chicks]
Of course, if you pass in fractional numbers of head or legs, all bets are off. Here's a complete test program so you can try out various values to ensure both methods return the same values:
import sys
def usage (reason):
print "Error: %s"%(reason)
print "Usage: solve <numHeads> <numLegs>"
sys.exit (1);
def solve1 (numLegs, numHeads):
for numChicks in range (0, numHeads + 1):
numPigs = numHeads - numChicks
totLegs = 4 * numPigs + 2 * numChicks
if totLegs == numLegs:
return [numPigs, numChicks]
return [None, None]
def solve2 (numLegs, numHeads):
chicks = numHeads * 2 - int (numLegs / 2)
pigs = numHeads - chicks
if chicks < 0 or pigs < 0: return [None, None]
if chicks * 2 + pigs * 4 != numLegs: return [None, None]
if chicks + pigs != numHeads: return [None, None]
return [pigs, chicks]
if len (sys.argv) != 3:
usage ("Wrong number of parameters (%d)"%(len (sys.argv)))
try: heads = int (sys.argv[1])
except: usage ("Invalid <numHeads> of '%s'"%(sys.argv[1]))
try: legs = int (sys.argv[2])
except: usage ("Invalid <numLegs> of '%s'"%(sys.argv[2]))
print "[pigs, chicks]:"
print " ", solve1 (legs, heads)
print " ", solve2 (legs, heads)
It is iterating through every possible combination of pigs and chickens (with the specified number of heads) until it finds one that has the correct number of legs, and then returns the numbers of pigs and chickens. If it gets through each combination without finding a valid answer, it returns [None, None] to indicate failure.
Essentially, solve is iterating through every possible combination of chickens and pigs, and when it finds a match, returning it.)
NumChickens + NumPigs must equal NumHeads, so it checks every NumChickens from 0 to NumHeads (that's what for range(0,NumHeads+1) does), and sets NumPigs to be NumHeads-NumChickens.
From there, its just a matter of multiplying out the number of feet, and seeing if they match.
Basically, it's trying to figure out the answer to the problem, "How many chickens and pigs are there in a barnyard if there are X heads and Y legs in the barnyard?" The for numChicks in range(0, numHeads + 1):code creates a variables numChicks, and cycles through it from numChicks = 0 to numChicks = numHeads. (Note: the range function doesn't include the highest value).
For each number of numChicks, it checks to see if that numChicks and corresponding numPigs values comes up with the correct value of numLegs. numHeads will always be correct since numChicks + numPigs = numHeads, but numLegs varies based on the distribution -- hence the loop. If at any point the solution is found (when totLegs == numLegs), then that value is returned. If the entire loop gets done and no solution was found, then the list [None, None] is returned, meaning that there's no solution for this input.
发布评论
评论（5）
solve正在计算需要多少只小鸡（1 头，2 条腿）和多少头猪（1 头，4 条腿）才能达到给定的头和腿数量。它使用“蛮力”，即最简单的方法：
小鸡从没有到多达
被指定为头数
（这就是循环
for 的作用，因为范围内的 numChicks(0, numHeads +
1):
range给出整数从包含的起始值开始
至期末值除外）；
numChicks它计算有多少头猪可以捐
所要求的头数，由
语句 numPigs = numHeads - numChicks ，
那些小鸡和猪会
totLegs = 4*numPigs + 2*numChickstotLegs是否相等请求的号码：如果是，则返回
包含两个项目的列表，其中的数量
最后解决问题的小鸡和猪
for循环但没有返回还没有一个值，它知道没有解决方案，
并表示通过返回一个列表
其中两项均为
None。barnYard只是将解决方案委托给solve，并以良好可读的方式打印出来，要么是“无解”，要么是装饰精美的小鸡和猪的数量。现在，为了继续进步，问问自己是否可以更有效地编写
solve。显然，如果腿的数量小于头部数量的两倍，或者超过头部数量的四倍，或者奇数，则没有解决方案 - 也许solve可以测试这些情况并返回<立即代码>[无，无]。你能编码吗...？这可能并不明显，但是头和腿的数量的所有其他组合都有一个解决方案 - 并且有一种方法可以通过算术找到它，而不需要循环。想一想，或许借助小学初中代数……
solveis computing how many chicks (1 head, 2 legs) and how many pigs (1 head, 4 legs) it takes to total up to the given numbers of heads and legs.It uses a "brute force", that is, maximally simple, approach:
chicks from none at all to as many as
was specified as number of heads
(that's the role of the loop
for, sincenumChicks in range(0, numHeads +
1):
rangegives integersfrom the starting value included
to the ending value excluded);
numChicksit computeshow many pigs there would be to give
the requested number of heads, by the
statement
numPigs = numHeads - numChicksthose chicks and pigs would have, by
totLegs = 4*numPigs + 2*numChickstotLegsequalthe requested number: if so, it returns
a list with two items, the numbers of
chicks and pigs that solve the problem
the
forloop without having returneda value yet, it knows there's no solution,
and signifies that by returning a list
each of whose two items is
None.barnYardjust delegates the solution tosolve, and prints it out in a nice readable way, either as "no solution" or as nicely decorated numbers of chicks and pigs.Now, to keep progressing, ask yourself if
solvecould be written more efficiently. Clearly there is no solution if the number of legs is less than twice the number of heads, or more than four times the number of heads, or odd -- maybesolvecould test for those case and return[None, None]immediately. Could you code that...?It may not be obvious, but every other combination of numbers of heads and legs has a solution -- and there IS a way to find it just by arithmetic, without looping. Think about it, maybe with the help of elementary middle-school algebra...
Alex Martelli 提到了一个代数解决方案，为了完整起见，我将其包含在此处。它可以通过使用联立方程来计算出来。作为一个简单的数学解决方案，它可能会更快，至少对于大量的腿和头来说:-)
令：
H是头的数量；L是腿的数量；C是小鸡的数量；给定
C和P，我们可以通过以下方式计算其他两个变量：我将详细说明下面计算中的每个步骤。数学爱好者无疑可以指出步骤可以组合，但我更愿意明确。从（1），我们可以计算：
并将其代入（2）：
现在你有两个公式，一个可以计算头部和腿部的小鸡数量
(4)，另一个可以计算计算小鸡和头的猪数量(3)。所以这里是执行此操作的 Python 代码，并进行适当的检查以确保您不会允许一些更奇怪的数学解决方案，例如 2 个头和 7 条腿给我们一头半猪和半只小鸡，或者 1 头和 7 条腿给我们一个半猪和半只小鸡。 12 条腿产生 5 头猪和 -4 只小鸡:-)
当然，如果您传递的是头或腿的分数，则所有赌注都会失败。这是一个完整的测试程序，因此您可以尝试各种值以确保两种方法返回相同的值：
Alex Martelli alludes to an algebraic solution which I'll include here for completeness. It can be worked out with the use of simultaneous equations. Being a simple mathematical solution, it's possibly faster, at least for large numbers of legs and heads :-)
Let:
Hbe the number of heads;Lbe the number of legs;Cbe the number of chicks; andPbe the number of pigs.Given
CandP, we can calculate the other two variables with:I'll detail every step in the calculations below. The mathematically inclined can no doubt point out that steps could be combined but I'd prefer to be explicit. From (1), we can calculate:
and substitute that into (2):
Now you have two formulae, one that can calculate the number of chicks from head and legs
(4), the other which can calculate number of pigs from chicks and heads(3).So here's the Python code to do it, with appropriate checks to ensure you don't allow some of the more bizarre mathematical solutions, like 2 heads and 7 legs giving us a pig and a half along with half a chick, or 1 head and 12 legs giving 5 pigs and -4 chicks :-)
Of course, if you pass in fractional numbers of head or legs, all bets are off. Here's a complete test program so you can try out various values to ensure both methods return the same values:
它会迭代猪和鸡的每一种可能的组合（具有指定的头数），直到找到具有正确数量的腿的组合，然后返回猪和鸡的数量。如果它通过每个组合而没有找到有效答案，则返回 [None, None] 以指示失败。
It is iterating through every possible combination of pigs and chickens (with the specified number of heads) until it finds one that has the correct number of legs, and then returns the numbers of pigs and chickens. If it gets through each combination without finding a valid answer, it returns [None, None] to indicate failure.
本质上，solve 会迭代鸡和猪的所有可能组合，当找到匹配项时，将其返回。）
NumChickens + NumPigs 必须等于 NumHeads，因此它会检查从 0 到 NumHeads 的每个 NumChickens（即for range(0,NumHeads+1) 的作用是什么），并将 NumPigs 设置为 NumHeads-NumChickens。
从那里开始，只需将英尺数相乘，然后看看它们是否匹配即可。
Essentially,
solveis iterating through every possible combination of chickens and pigs, and when it finds a match, returning it.)NumChickens + NumPigs must equal NumHeads, so it checks every NumChickens from 0 to NumHeads (that's what
for range(0,NumHeads+1)does), and sets NumPigs to be NumHeads-NumChickens.From there, its just a matter of multiplying out the number of feet, and seeing if they match.
基本上，它试图找出问题的答案：“如果谷仓中有 X 头和 Y 腿，那么谷仓中有多少只鸡和猪？” for numChicks in range(0, numHeads + 1): 代码创建一个变量 numChicks，并从 numChicks = 0 循环到 numChicks = numHeads。 （注意：范围函数不包括最高值）。
对于每个 numChicks 数量，它会检查 numChicks 和相应的 numPigs 值是否与正确的 numLegs 值一致。 numHeads 始终是正确的，因为 numChicks + numPigs = numHeads，但 numLegs 根据分布而变化 - 因此是循环。如果在任何时候找到解决方案（当 totLegs == numLegs 时），则返回该值。如果整个循环完成并且没有找到解决方案，则返回列表 [None, None]，这意味着该输入没有解决方案。
Basically, it's trying to figure out the answer to the problem, "How many chickens and pigs are there in a barnyard if there are X heads and Y legs in the barnyard?" The
for numChicks in range(0, numHeads + 1):code creates a variables numChicks, and cycles through it from numChicks = 0 to numChicks = numHeads. (Note: the range function doesn't include the highest value).For each number of numChicks, it checks to see if that numChicks and corresponding numPigs values comes up with the correct value of numLegs. numHeads will always be correct since numChicks + numPigs = numHeads, but numLegs varies based on the distribution -- hence the loop. If at any point the solution is found (when totLegs == numLegs), then that value is returned. If the entire loop gets done and no solution was found, then the list [None, None] is returned, meaning that there's no solution for this input.