「砝码问题java」砝码问题进制
本篇文章给大家谈谈砝码问题java，以及砝码问题进制对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
德?梅齐里亚克的砝码问题是怎样解决的？
一个商人不慎将一个重40磅的砝码跌落在地面上碎成4块，恰巧每块都是整数磅，后来他又意外发现，可以用这4块碎片做成可以称1到40磅的任意整数磅的重物的新砝码。请你猜一猜，这4块碎片的重量各是多少?
这就是著名的德?梅齐里亚克的砝码问题。这位法国数学家采用“迂回进击”的战术，使问题得到解决。
他是这样演绎的：
首先说明一个结论：如果有一系列砝码，把它们适当地分放在天平的两个托盘上，能称出1到n的所有整数磅重物(这时这些砝码重量的和也一定为n磅)。另设有一块砝码，它的重量为m磅(m＝2n＋1)，那么原来所有的砝码再加砝码m所组成的砝码组便能称出从1到3n＋1的所有整数磅的重物。
因为，原砝码组可称出重量1到n的所有整数磅重物。而原砝码组与重量为m磅的砝码可以秤n＋1到2n＋1磅的所有整数磅重物。
由此可判定这4块砝码的重量：
第一块砝码取m1＝1(磅)
第二块砝码取m2＝2乘以1＋1＝3(磅)
第三块砝码取m3＝2(1＋3)＋1＝9(磅)
第四块砝码取m4＝2(1＋3＋9)＋1＝27(磅)
用这4块砝码可秤从1到(1＋3＋9＋27)＝40磅间的任何一个整数磅重物。
砝码问题
如果你是说各一个
因为2的0次幂是1,2的1次幂是2,2的三次幂是4……
所以无论如何组合都不会有重复
两个一组：4+3+2+1=10种
三个一组：（3+2+1）+（2+1）+1=10种
四个一组：【每组取出一个砝码】5种
五个一组：1种
总共：10+10+5+1=26种
有一个天平，九个砝码，其中一个砝码比另八个要轻一些，问至少要称几次才能将轻的那个找出来
至少要称2次才能将轻的那个找出来。第一次，一边3个，哪边轻就在哪边，一样重就是剩余的3个；第二次，一边1个，哪边轻就是那个，一样重就是剩余的那个。
此题的解决关键是每次使用天平称都把砝码分成三份，只要对其中的2份进行称重对比，就相当于对3份砝码都进行了对比。
扩展资料：
经典砝码称重问题：
为了称出从 1 克到 40 克 所有整数克 的物品，最少需要几个砝码？
据《数学游戏与欣赏》（ [英] 劳斯·鲍尔 [加] 考克斯特 著，杨应辰等 译），这个问题被称作巴协 (Bachet) 砝码问题；而据《数学聊斋》（王树禾著），该问题至少可追溯到 17 世纪法国梅齐里亚克 (Meziriac, 1624) 。他们给出的答案是：
最少需要 4 个砝码，规格分别为 1 克、3 克、9 克和 27 克。
例如，为了称出 2 克的物品，我们只需在天平一端放 3 克砝码，在另一端放上 1 克的砝码；而要称出 7 克的物品，则可以在一端放上 1 克和 9 克的砝码，另一端放上 3 克的砝码。
类似地，要称出 1 克到 4 克中所有整数克的物品，只需要 2 个砝码；要称出 1 克到 13 克中所有整数克的物品，则只需要 3 个砝码；要称出 1 克到 121 克中所有整数克的物品则要 5 个砝码，它们分别是 1 克、3 克、9 克、27 克和 81 克，如此等等。
称砝码问题的一般解
真正的答案在这里，让小弟深入浅出的从头讲起，虽然有点长，但保证各位看完之後彻底理解．
命题A：有3^m个物件，其中1个是次品且知道次品比较轻，这样可以透过m次测量找出次品．
证明：每次测量都有三种结果，所以测量之後都可以将范围缩小成为原先的1/3．
命题B：有3^m个物件，其中1个是次品．此外，对於每一个物件，我们知道＂如果它是次品的话，那麼次品是较轻或是较重＂，这样我们仍然可以透过m次测量找出次品．
举例：现有3^m个物件，其中1个是次品．假设我们知道，如果1号是次品，那麼次品比较轻；如果2号是次品，那麼次品比较重；如果3号是次品，那麼次品比较重．．．如果3^m号是次品，那麼次品比较轻－－这样的话，我们仍可以透过m次测量找出次品．
证明：其实命题B与命题A同构．命题A比较无脑，每次测量之後，我们都可以很简单地确定次品是在＂天平左边＂、＂天平右边＂或是＂秤外＂．相形之下命题B比较复杂，每次测量之後，我们仍然可以将范围缩小成为1/3，这不过这1/3未必像命题A那样通通在秤的某一边，而是＂秤左边的第2号或第4号比较轻＂或者＂秤右边的第5号比较重＂这类的答案．但无论如何，每次测量之後我们还是可以把范围缩小成为1/3，所以命题B与命题A所需要的测量次数是相同的．
命题C：有3^m个物件，其中1个是次品，但不知是轻是重，同时额外还有无数个标准品可供你使用．假设先前有人将这3^m个物件平均分放到天平的两侧（当然要添加一个正品才能凑成偶数），并且测量出结果了（肯定不是平衡的）．此後，你只要再秤一次，就可以把问题改写成为＂3^(m-1)个物件的命题B＂．换句话说，你只要再秤一次，不但可以把范围缩小成为1/3，还可以知道＂如果某一个物件是次品的话，那麼它将是轻还是重＂．
证明：在第二次测量之前，将所有3^m个物件分为三类，每类3^(m-1)个：
第一类：保持不动：原先在天平左边的就留在左边，原先在天平右边的就留在右边．
第二类：左右换位：原先在天平左边的就换到右边，原先在天平右边的就换到左边．
第三类：彻底消失：通通拿下来，放到旁边．
如果左右物件数量不同的话，用额外的标准品补上．
这样的话，如果第二秤与第一秤结果相同，那麼次品就在＂保持不动＂的那一组；如果前两秤结果相反，那麼次品就在＂左右换位＂的那一组；如果第二秤左右平衡了，那麼问题就在＂彻底消失＂的那一组；所以范围可以缩小成为1/3．
又，依据前两秤的结果，我们不难得知如果某一个物品是次品的话，那麼它是较轻还是较重．这样就完全等价於命题B了．
换句话说，命题C告诉我们：＂只需要秤两次，就可以将原问题的范围缩小成为1/3，并简化成为命题B＂．
好，现在来解本题．很明显的，在第一秤时，我们一定是将p个物件分放到天平左右，并留下q个物件在外面；其中p为偶数，q为非负整数．
令f(n)代表＂在秤n次的情况之下，所能够处理的物件数量上限＂，那麼我们可以列出下式：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
f(n) = 如果第一秤的p个物件左右不平衡，我们可以使用命题C解决这p个物件
＋
如果第一秤的p个物件平衡了，则在少了一秤的情况下，我们必须能够解决q个物件
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
先看第一条，我们知道使用命题C要先秤2次，然后才能将3^m个物件缩小成为3^(m-1)个物件的命题B．又命题B告诉我们3^(m-1)个物件需要再秤m-1次才能得到最终答案，因此从头到尾一共要秤m+1次才能解决3^m个物件，故上面公式可以改写为：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
f(m+1) = 第一秤天平左右两端一共有 3^m 个物件，若不平衡必能用命题C解决
＋
如果第一秤平衡了，则在少了一秤的情况下，我们必须能够解决剩下的q个物件
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
其实上式是错的，因为 3^m 是个奇数，我们没有办法将奇数平均分放到天平的左右．别忘了在命题C里面，我们假设＂额外有无数个标准品＂可供我们利用，但这个条件在本题不适用，所以上式必须改写为：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
f(m+1) = 第一秤天平左右两端一共有 (3^m)-1 个物件，若不平衡必能用命题C解决
＋
如果第一秤平衡了，则在少了一秤的情况下，我们必须能够解决剩下的q个物件
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
好，接下来再看第二条：＂在少了一秤的情况下，必须解决剩下的q个物件＂，请问q是多少？不就是 f(m) 吗？想想看前面的定义， f(m) 与 f(m+1) 相比，正是少用一秤所能解决的物件数量．所以上面公式可以改写为：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
f(m+1) = 第一秤天平左右两端一共有 (3^m)-1 个物件，若不平衡必能用命题C解决
＋
如果第一秤平衡了，则在少了一秤的情况下，我们可以解决 f(m) 个物件
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
事实上这公式还有错．当初我们设计 (3^m)-1 这个数字的时候，由於 3^m 是奇数，在没有＂额外的标准品＂可以利用的情况之下，我们无法将 3^m 个物件分放到天平的两端，因此我们才忍痛减1．
然而反观在第一秤平衡之後，当我们处理剩下的 q 个物件的时候，我们手边可是有标准品能够使用的！这与 f(m) 的情况不完全相同．在处理剩下的 q 个物件时，我们可以完全照抄命题C，不必再刻意地减 1 ．因此 q = f(m)+1，而上述公式也可以改写为最终型态：
f(m+1)
= (3^m)-1 + f(m)+1
= 3^m + f(m)
使用穷举实验，我们知道秤2次时最多只能处理4个物件，即 f(2)=4，故：
f(3) = 3^2 + f(2) = 9+4 = 13
f(4) = 3^3 + f(3) = 27+13 = 40
f(5) = 3^4 + f(4) = 81+40 = 121
均合乎预期．
接下来我们开始化简：
f(2) = 4
f(3) = 3^2 + f(2)
f(4) = 3^3 + f(3)
f(5) = 3^4 + f(4)
f(6) = 3^5 + f(5)
.....
+ f(n+1) = 3^n + f(n)
--------------------------
f(n+1) = (3^2+...+3^n) +4
= 3^2*(3^(n-1) - 1)/2 + 4
= (3^(n+1) - 9)/2 + 8/2
= (3^(n+1) - 1)/2
故 f(n) = (3^n -1)/2
证毕．
关于砝码问题java和砝码问题进制的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
发布于：2022-12-04，除非注明，否则均为原创文章，转载请注明出处。