如何用一个23升的水桶和一个16升的水桶

北京中科医院好不好 http://news.39.net/bjzkhbzy/170210/5218643.html
有一个水龙头，一个水箱（假设可以装任意多的水），一个23升的大桶和一个16升的小桶。目标是在水箱中正好放进1升水，你将如何做到这一点？这有可能吗？如果想在水箱里放7升水，那就很容易了，把大桶装满23升水，倒进水箱，然后把小桶倒满。但我们的目标恰恰是1升。裴蜀等式（Bézout’sIdentity）裴蜀等式说，如果a和b是整数，最大公约数为d，那么存在整数x和y，使ax+by=d。最大公除数是指能同时除a和b的最大数字，例如，如果a=33，b=44，那么d=11。在我们上面的水桶例子中，a=23，b=16，d=1。根据裴蜀等式，一定有一些整数x和y使得23x+16y=1。这就是说，上述问题有一个解，但它是什么？欧几里得算法欧几里德算法是计算两个整数a和b的最大公约数d的一种有效方法。我们用gcd(a,b)代替d。你可能会想，既然我们已经知道gcd(23,16)=1，为什么还要用欧几里得算法？事实证明，该算法将回答我们的上述问题，即得到x和y的值，使23x+16y=1。下面是计算某些数字a和b的gcd(a,b)的步骤(假设a≥b)：获取a除以b的余数，称之为r如果r=0，那么gcd(a,b)=b.如果r≠0，则执行b除以r，得到一个新的余数，称其为r^如果r^=0，则gcd(a,b)=r，如果r^≠0，则执行r除以r^，得到一个新的余数，称为r^^如果r^^=0，那么gcd(a,b)=r^，如果r^^≠0，那么....继续这样做，直到余数为零得到的最后一个非零余数就是最大公约数。例子：gcd(23,16)==1*16+7（这里r=7）16=2*7+2（这里r^=2）7=3*2+1（这里r^^=1，最后一个非零余数）2=2*1+0（这里r^^=0）这里的*表示乘法。最后一个非零余数是1，所以这是23和16的最大公约数。在处理更大的数字时，这个算法会很有用。现在我们可以按照上面的步骤进行倒推。这里的想法是保持余数为1，并尝试得到一个只有16和23的方程。我们可以用上面的第二个等式乘以3，然后代入第三个等式，去除余数2。这样我们就可以得到：3*16=6*7+(7-1)=7*7-1现在用第一个等式乘以7，再代入上面的方程，得到：7*23+(-10)*16=1因此我们问题的答案是x=7和y=10。答案我们可以先在水箱中装7大桶水，然后再倒出10小桶。我才是老胡

多谢赏识??

转载请注明：http://www.abuoumao.com/hykz/230.html