法国数学家梅齐亚克的砝码问题

砝码问题 写道

法国数学家梅齐亚克在他著名的《数字组合游戏》(1962)中提出了一个问题：一位商人有一个重40磅的砝码，一天不小心将砝码摔成了四块。后来商人称得每块的重量都是整磅数，而且发现这四块碎片可以在天平上称1至40磅之间的任意重量。请问这四块碎片各重多少？

 

*问题分析与算法设计 写道

*问题分析与算法设计
本题是上一题的发展。题目中给出的条件是“在天平上”，这意味着：同一砝码既可以放在天平的左侧，也可以放在天平的右侧。若规定重物只能放在天平的左侧，则当天平平衡时有：
重物重量+左侧砝码重量总和=右侧砝码重量总和
由此可得：
重物重量=右侧砝码重量总和-左侧砝码重量总和
编程时只要根据以上公式，使“右侧砝码重量总和-左侧砝码重量总和”可以表示1到40之间的全部重量即可。编程中要注意的是：怎样采用一种简单的方法来表示一个砝码是在天平的左侧还是在天平的右侧，或是根本没有使用。
以下程序采用1、 -1和0分别表示上述三种情况，请注意理解。

 

*程序说明与注释
#include<stdio.h>
#include<math.h>
int main()
{
int weight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag; /*flag:满足题意的标记*/
printf("The weight is broke up as following 4 pieces:");
for(weight1=1;weight1<=40;weight1++) /*将40分解成4份*/
for(weight2=weight1+1;weight2<=40-weight1;weight2++)
for(weight3=weight2+1;weight3<=40-weight1-weight2;weight3++)
if((weight4=40-weight1-weight2-weight3)>=weight3)
{
for(flag=1,x=1;x<41&&flag;x++) /*判断可否称出1~40之间的全部重量*/
for(flag=0,d1=1;d1>-2;d1--) /*将重物放在天平的左边*/
for(d2=1;d2>-2&&!flag;d2--) /*1:砝码在天平右边*/
for(d3=1;d3>-2&&!flag;d3--) /*0：不用该砝码*/
for(d4=1;d4>-2&&!flag;d4--) /*-1:砝码在天平的左边*/
if(x==weight1*d1+weight2*d2+weight3*d3+weight4*d4)
flag=1;
if(flag) printf("%d %d %d %d\n",weight1,weight2,weight3,weight4);
flag=0;
}
}

*运行结果
The weight is broke up as following 4 pieces: 1 3 9 27 

 

 

百度的解释 写道

能够算出四块分别是27,9,3,1.因为任何一个1-40.都能写成A*3^3+B*3^2+C*3^1+D*3^0.构造一个三进制的数.则1-40 改为三进制数表示为(ABCD)3.A,B,C,D表示各个数位上的数,其取值范围为{0,1,2}.当四个数位上的数值都是0或者1时,用对应的砝码放在同一个盘称就行了,当某个数位上的数值为2的时候,则把它前一位的砝码和其他需要的砝码放一个盘,这一位的砝码和重物放一个盘就能称.如需要称33磅, 他用三进制的数表示为(1020)3,将27磅和9磅的砝码放左盘,3磅的砝码放右盘和重物放一起就能称量.另外,如前一位的数值为1或者2的时候,应该再往前推一位,如15磅,写成三进制的数为(0120),应将一个27磅的砝码放左盘,右盘放9磅和3磅的砝码,加上重物就能称量了.
这是利用了3的N次方,通过加减运算能表示仍一个正整数的原理.为什么呢,刚才构造的三进制的数是能表示任一个正整数的,当进行减法运算的时候,就可以表示成该数位上的数为-1.也就意味着,他的前一个数位应该加1,而这个数位的数值变成了2.这样3的N次方加减后,得到的数,能够表示成三进制数的形式,所以也就能表示任一个正整数了

http://zhidao.baidu.com/question/29463395.html

 

写道

定理： 由m个数构成的由小到大排列的数列{a(1),a(2),...a(m)}，设A(k)=∑a(i)， 其中i从1到k， 则
a(1) = 1且a(j+1) <= 2A(j) +1， j取1,2,..,m-1 （1式）
是该数列作为砝码序列可称量{0,1,..,Am}范围内的任意整数重量的充要条件。特别的，上式取等号时，该序列是唯一可能的砝码序列，并且有a(j) = 3^(j-1)， 对于j=1,2,..,m

推论： 重量为n的物体要分成m份重量为整数的物体的序列{a(1),a(2),..a(m)}，设M=∑3^(i-1)，其中i从1到m，则有三种情况：
1） M<n， 无解；
2） M=n，有唯一的解 a(j)=3^(j-1), j=1,2,..m;
3） M>n，可能有多组解，解为满足（1式）并且∑a(i)=n,其中i从1到m，的所有整数序列。

定理的证明：
（充分性）
用数归法：
当i=1的时候，a(i)=1显然成立；
假设i=k的时候定理充分性成立，即用满足（1）式的前k个砝码可以称量的重量W(k)为满足0<=W(k)<=A(k)的所有整数，则i=k+1时，应可以称量W(k+1),应为0<=W(k+1)<=A(k+1)范围内的所有整数。分段讨论如下：
(a)对于0<=W(k+1)<=A(k)，显然可以由前k个砝码称量；
(b) 对于A(k)<W(k+1)<=a(k+1)， 由假设0<=W(k)<=A(k)，交换左右盘的砝码，可以产生配合砝码a(k+1)使用的负砝码为W(k)' 可以是满足-A(k)<=W(k)'<=0的所有整数。与大砝码a(k+1)一起使用可以得到a(k+1)+W(k)' ，一定可以称量某段连续范围的所有整数，因为a(k+1) <=2A(k)+1， 所以a(k+1)-A(k) <= A(k)+1，因此a(k+1)+W(k)'产生的下限为a(k+1)-A(k)，上限为a(k+1),所以可以称量 A(k)<W(k+1)<=a(k+1)内的所有W(k+1)；
(c)对于a(k+1)<=W(k+1)<=A(k+1)，与(b)同理可以得到称量的上下限分别为：a(k+1)+A(k) = A(k+1)和a(k+1)；
因此当i=k+1的时候定理充分性也成立，由数归法知定理充分性成立。

（必要性）
i=1时，显然必须有总量为1的砝码；
i>1时，反证之，如果存在某个K，使得（1）不成立，即2A(k)+1<a(k+1)，则重量A(k)+1既不能用前面的k-1个砝码称重，又因为a(k+1)-A(k)>A(k)+1而不能用a(k+1)配合着称重。所以矛盾，因此必要性成立。

推论也可以用数归法简单的证明，这里我就不证了，打字太累了：）

根据以上的定理和推论，可以很容易的求出对于重量为任意的n的物体，用m个砝码可以称出来的砝码的方案。当n=∑3^(i-1)， i从1到m的时候，有唯一解a(i)=3^(i-1)，可以改写成a(i)=2(∑aj)+1，其中j从1到i-1，一个循环就直接输出了；当n> ∑3^(i-1)的时候无解；当n<∑3^(i-1)的时候只要根据式（1）并保证∑a(i)=n搜索就可以了。可以递归的搜索求解。具体我就不写程序了。

http://www.zaoxue.com/article/tech-25044.htm

 

csdn给出的方法 写道

1 3 9 27 ： 后项是前面各项和的2倍再加1
3 ＝ 2×1 + 1
9 ＝ 2×（1+3) + 1
27 = 2*(1+3+9 )+ 1

和那个一个金项链分成几块，用来支付工资，要求分割最少，可以满足各种需求的题目是一样的

*******************************************************
就是3进制数，任何一个数写成3进制，然后等价的转换成在-1,0,1上面的3进制表示，
然后就可以知道如何用这几个数来称了

*******************************************************
//砝码称重dp思想
#include<stdio.h>
int main()
{
int num[6]={1,2,3,5,10,20};//砝码重量序列
int a[6];//6个砝码的个数
bool vist[1000]={false};//访问标志位
int no[1000];//no[0]为不同重量个数，no[j]--第j种重量1<=j<=no[0]
int i,j,k,total;//total:目前称出的重量
for(i=0;i<6;i++)
scanf("%d",&a[i]);//输入6个砝码的个数
no[0]=1;no[1]=0;//称出第一种质量0
for(i=0;i<6;i++)//阶段：分析第i种砝码
for(j=0;j<no[0];j++)//状态：枚举现有的不同重量
for(k=0;k<a[i];k++)//决策：在现有重量的基础上放k块第i种砝码
{
total=no[j]+k*num[i];//产生重量
if(!vist[total])
{
vist[total]=true;//若该重量未产生过，则设访问标志
no[0]++;
no[no[0]]=total;
// printf("%d\n",total);

}
}
printf("%d\n",no[0]-1);
return 0;
}


http://topic.csdn.net/t/20050908/16/4257762.html