no.4_药丸称重
有20瓶藥丸,其中19瓶藥丸質量相同為1克,剩下一瓶藥丸質量為1.1克。瓶子中有
無數個藥丸。要求用一次天平找出藥丸質量1.1克的藥瓶。
?
解答:
可以從藥丸的數量上來制造差異:從第i瓶藥丸中取出i個藥丸,然后一起稱重。 可以知道,
如果第i瓶藥丸重1.1克/粒,那么稱重結果就會比正常情況下重0.1 *i克
?
?
?
是不是不懂:
?
?
?
別急:
解法:有時候,嚴格的限制條件有可能反倒是解題的線索。在這個問題中,限制條件是天平只能用一次。因為天平只能用一次,我們也得以知道一個有趣的事實:一次必須同時稱很多藥丸,其實更準確地說,是必須從19瓶拿出藥丸進行稱重。否則,如果跳過兩瓶或更多瓶藥丸,又該如何區分沒稱過的那幾瓶呢?別忘了,天平只能用一次。
那么,該怎么稱重取自多個藥瓶的藥丸,并確定哪一瓶裝有比較重的藥丸?假設只有兩瓶藥丸,其中一瓶的藥丸比較重。每瓶取出一粒藥丸,稱得重量為2.1克,但無從知道這多出來的0.1克來自哪一瓶。我們必須設法區分這些藥瓶。
如果從藥瓶#1取出一粒藥丸,從藥瓶#2取出兩粒藥丸,那么,稱得重量為多少呢?結果要看情況而定。如果藥瓶#1的藥丸較重,則稱得重量為3.1克。如果藥瓶#2的藥丸較重,則稱得重量為3.2克。這就是這個問題的解題竅門。
稱一堆藥丸時,我們會有個“預期”重量。而借由預期重量和實測重量之間的差別,就能得出哪一瓶藥丸比較重,前提是從每個藥瓶取出不同數量的藥丸。
將之前兩瓶藥丸的解法加以推廣,就能得到完整解法:從藥瓶#1取出一粒藥丸,從藥瓶#2取出兩粒,從藥瓶#3取出三粒,依此類推。如果每粒藥丸均重1克,則稱得總重量為210克(1 + 2 + … + 20 = 20 * 21 / 2 = 210),“多出來的”重量必定來自每粒多0.1克的藥丸。藥瓶的編號可由算式(weight – 210 grams) / 0.1 grams得出。因此,若這堆藥丸稱得重量為211.3克,則藥瓶#13裝有較重的藥丸。
總結
- 上一篇: Spark _13_topN
- 下一篇: Spark _14_SparkShell