来个经典题目,大家写算法

Question

/*有个商人不小心把40磅的砝码摔碎了,摔成了4块,欲哭无泪时发现这4块砝码恰好可以组合成1-40的任意重量,求这4块碎砝码的质量.*/
  我用遍历的方法做,不知道有什么更好的方法.反正第一块肯定是1磅.

Answer 1

n个砝码应该怎样设计才能使这n个砝码能表示1--m的重量，并使m最大，m和n的关系是怎样的呢？

Answer 2

算法还不知道，不过数学上的命题是这样的(以下用符号^表示指数。如3^2表示3的2次方)：
假设有序列An= ｛3^0, 3^1, 3^2,...,3^n｝,
要证明可以用该序列中的1~n个元素通过加减法组合出Sum(An)中的任意整数。
可以用数学归纳法获得证明。
证明：
当n=1，n=2时，可以用手工方法检验该命题是正确的。假设当n=K时该命题成立，即对Sum(AK)中的任意整数p，都可以找到这样的纯加减算法P(AK)，使得P(AK)=p。那么当n=K+1时...
对于Sum(AK)中的任意整数P，我们可以用原先的算法P(AK)生成。
对于对于Sum(AK)~Sum(A[K+1])之间的整数，我们把它分成2段：
第一段：Sum(AK)+1 ,..., 3^(K+1)-1,
第二段: 3^(K+1), 3^(K+1)+1, ..., 3^(K+1)+Sum(AK)。
对于第2段的数字q，可以将它拆分成q=3^(K+1)+p，我们可以用Q(A[K+1])=3^(K+1)+P(AK)这样的方法导出算法，因此也是成立的。
然后对于第1段数据进行分析。
高中的数学知识告诉我们，对于公比为q的等比数列{a,a*q,a*q^2,...,a*q^n}，其求和公式为
S= a*(1-q^(n+1))/(1-q)。
在本题中，Sum(AK)+1= (3^(K+1)-1)/2 + 1= (3^(K+1)+1)/2 > (3^(K+1)-1)/2。
所以对第一段中的数字q，可以将它拆分为q=3^(K+1)-p,且0<=p<=Sum(AK)。 我们可以用 Q(A[K+1])=3^(K+1)-P(AK)这样的方法导出算法。
因此当n=K+1的时候该命题也是成立的。另外：对于任意序列AN= {a1,a2,...,aN}，如果能利用某种加减算法拼接出1~Sum(AN)中的所有整数，那么考虑到加，减两种可能的算法，如果a[N+1]<=Sum(AN)+1，该命题仍然是成立的。而3恰恰是分界线。

Answer 3

m=0;
for(int i=0;i<n;i++) m+=Math.pow(3,i);

Answer 4

import java.util.*;class  HelloWorld
{
private int generate()
{
int sum = 0; for(int i = 37 ; i > 10 ; i--)
{
for(int j = i ; j > 0 ; j--)
{
if(i + j < 39)
{
for(int m = j ; m > 0 ; m--)
{
if(i + j + m < 40)
{
int n = 40 - i - j - m;
if((n <= m) && this.check(i,j,m,n))
{
sum++;
}
}
}
}
}
}
return sum;
}
private boolean check(int n1, int n2, int n3, int n4)
{
List list = new ArrayList(); int aa = n1;
int bb = n2;
int cc = n3;
int dd = n4; int a = 0;
int b = 0;
int c = 0;
int d = 0; String as = "";
String bs = "";
String cs = "";
String ds = ""; Integer tem = null; for(int i = 0 ; i < 40 ; i++)
{
tem = (Integer)(i + 1);
list.add(tem);
} for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
for(int m = 0 ; m < 3 ; m++)
{
for(int n = 0 ; n < 3 ; n++)
{
switch(i)
{
case 0:
{
a = 0;
as = "";
break;
}
case 1:
{
a = -aa;
as = " - " + aa;
break;
}
case 2:
{
a = aa;
as = " + " + aa;
break;
}
default:
{
break;
} }
switch(j)
{
case 0:
{
b = 0;
bs = "";
break;
}
case 1:
{
b = -bb;
bs = " - " + bb;
break;
}
case 2:
{
b = bb;
bs = " + " + bb;
break;
}
default:
{
break;
} }
switch(m)
{
case 0:
{
c = 0;
cs = "";
break;
}
case 1:
{
c = -cc;
cs = " - " + cc;
break;
}
case 2:
{
c = cc;
cs = " + " + cc;
break;
}
default:
{
break;
} }
switch(n)
{
case 0:
{
d = 0;
ds = "";
break;
}
case 1:
{
d = -dd;
ds = " - " + dd;
break;
}
case 2:
{
d = dd;
ds = " + " + dd;
break;
}
default:
{
break;
} }
if(a + b + c + d > 0)
{
tem = (Integer)(a + b + c + d);
list.remove(tem);
if(list.isEmpty())
{
System.out.println("a = " + aa + " b = " + bb + " c = " + c + " d = " + d);
System.out.println("**************************************************************");
return true;
}
}
}
}
}
}
return false;
}
public static void main(String[] args) 
{
HelloWorld hello = new HelloWorld();

System.out.println("There are " + hello.generate() + " results!");
}
}---------- java ----------
a = 27 b = 9 c = 3 d = 1
**************************************************************
There are 1 result!
Normal Termination
输出完成(耗费 0 秒)。

Answer 5

有没有递归的方法,觉得递归会很简答至少是code...

Answer 6

其实这个题目无法递归....
因为在check的时候,4个砝码,肯定会被用到....测试四个砝码的组成是否满足可以组成任意1-40的重量,那么boolean tryit(int a,int sum)
{
return(a==sum);

}boolean tryit(int a,int b,int sum)
{
return( a+b==sum  ||
-a+b==sum ||
a-b==sum);


} boolean tryit(int a,int b,int c,int sum)
{
return(a+b+c==sum||
a+b-c==sum||
a-b+c==sum||
a-b-c==sum||
-a+b+c==sum||
-a+b-c==sum||
-a-b+c==sum);

}


boolean tryit(int a,int b,int c,int d,int sum)
{


return( 
a+b+c+d==sum||
a+b+c-d==sum||
a+b-c+d==sum||
a+b-c-d==sum||
a-b+c+d==sum||
a-b+c-d==sum||
a-b-c+d==sum||
a-b-c-d==sum||
-a+b+c-d==sum||
         -a+b-c+d==sum||
-a+b-c-d==sum||
-a-b+c+d==sum||
-a-b+c-d==sum||
-a-b-c+d==sum||
-a-b-c-d==sum   
);


}boolean check(int a,int b,int c,int d)
{
boolean flag1=true;
for(int i=1;i<41&&flag1==true;i++)
{
System.out.println("check:"+i);
flag1=(
tryit(a,i)||
tryit(b,i)||
tryit(c,i)||
tryit(d,i)||
tryit(a,b,i)||
tryit(a,c,i)||
tryit(a,d,i)||
tryit(b,c,i)||
tryit(b,d,i)||
tryit(c,d,i)||
tryit(a,b,c,i)||
tryit(a,b,d,i)||
tryit(a,c,d,i)||
tryit(b,c,d,i)||
tryit(a,b,c,d,i)
);
};
System.out.println("the num can do it: "+flag1);
System.out.println();
return flag1;
}

Answer 7

整个代码是class mathDemo {
mathDemo() { n1 = 0;
n2 = 0;
n3 = 0;
n4 = 0;
} boolean tryit(int a,int sum)
{
return(a==sum);

}boolean tryit(int a,int b,int sum)
{
return( a+b==sum  ||
-a+b==sum ||
a-b==sum);


} boolean tryit(int a,int b,int c,int sum)
{
return(a+b+c==sum||
a+b-c==sum||
a-b+c==sum||
a-b-c==sum||
-a+b+c==sum||
-a+b-c==sum||
-a-b+c==sum);

}


boolean tryit(int a,int b,int c,int d,int sum)
{


return( 
a+b+c+d==sum||
a+b+c-d==sum||
a+b-c+d==sum||
a+b-c-d==sum||
a-b+c+d==sum||
a-b+c-d==sum||
a-b-c+d==sum||
a-b-c-d==sum||
-a+b+c-d==sum||
         -a+b-c+d==sum||
-a+b-c-d==sum||
-a-b+c+d==sum||
-a-b+c-d==sum||
-a-b-c+d==sum||
-a-b-c-d==sum   
);


}boolean check(int a,int b,int c,int d)
{
boolean flag1=true;
for(int i=1;i<41&&flag1==true;i++)
{
System.out.println("check:"+i);
flag1=(
tryit(a,i)||
tryit(b,i)||
tryit(c,i)||
tryit(d,i)||
tryit(a,b,i)||
tryit(a,c,i)||
tryit(a,d,i)||
tryit(b,c,i)||
tryit(b,d,i)||
tryit(c,d,i)||
tryit(a,b,c,i)||
tryit(a,b,d,i)||
tryit(a,c,d,i)||
tryit(b,c,d,i)||
tryit(a,b,c,d,i)
);
};
System.out.println("the num can do it: "+flag1);
System.out.println();
return flag1;
} void xunhuan() {
while (n1 < 41 & (flag == false)) { n2 = 1;
n1++;
while (n2 < 41 - n1 & (flag == false)) { n3 = 1;
n2++;
while (n3 < 41 - n2 - n1 & (flag == false)) {
n3++;
n4 = 40 - n1 - n2 - n3;
System.out.print("use the numb:" + n1 + " " + n2 + " " + n3
+ " " + n4 + " to check"); flag = check(n1, n2, n3, n4); }
}
}
} public static void main(String[] agr) { mathDemo a = new mathDemo();
a.xunhuan();
if (a.flag == true) {
System.out.println(a.n1);
System.out.println(a.n2);
System.out.println(a.n3);
System.out.println(a.n4);
} else {
System.out.println();
System.out.println(a.flag);
System.out.println("can't find numbs...");
} } int n1, n2, n3, n4; boolean flag = false;
}

Answer 8

PS:上面打错字了,应该是:数字1,2都是先左边,后右边---------------------------------------------------------------------------
那么现在我们回到楼主的这道题目:组成1-n的任意砝码重量(整数),要求所用的钱币张数最少,那么怎么组合?
关键:
--------------------------------
砝码的组合,可以选择性的放在左右两边那么可以是加法,也可以是减法
----------------------------------因为可以用减法
于是我们得到:假设已经实现了1-N个数字
那么下一个要取的数A的左边和右边都可以"实现"N个数字
左边的实现方法也就是用A-已经实现的1-n
右边的实现方法也就是用A+已经实现的1-n可能这样说有点郁闷例如因为肯定需要一个数字
所以必须实现:1因为实现了1,那么下一个要取的数字B的左边可以B-1,右边B+1,那么都可以实现一个数字第二个数的左边挨着1实现一个数字就是:2那么第二个要取的数字就是:3
那么右边实现一个数字也就是:4
这个数字的左右两边的1个数字是因为1已经实现而实现的好,现在我们已经实现了:1.2.3.4  四个数字同理,
第三个要取的数的左边和右边都可以实现4个数字
那么左边接着4,就是5.6.7.8这四个数
不难看出第三个数字是9
9的右边我们还可以实现:10.11.12.13这4个数字好,我们已经实现了1.2.3.4......11.12.13这13个数字
那么第四个数字的左边也可以实现13个数字:14.15.16........25.26第四个数字就是:27
27的右边再用+法又可以实现:28.29.30........38.39.40
好了,观察一下不难发现公式为:(0+1)*2+1=3
(1+3)*2+1=9
(1+3+9)+1=8
(1+3+9+27)*2+1=81大家也许会发现,和楼上的公式差不多,也是前面的总和+1
但是因为可以用-法,所以每个数的范围扩大为2倍

Answer 9

public static boolean fun1(int sum,int num) //sum为总重量,num为块数
{
if(num==2)
{
return (sum<=4);
}
else{
for(int i=1;i<=sum;i++)
{
if(!fun1((sum-i),(num-1)))
continue;
if((i-(sum-i))>(sum-i+1))
continue;
return true;
}
}
return false;
}这个可以判断一个sum重的砸成num块时是否满足楼主要求

Answer 10

第一个是 1
第二个是 1 * 3 = 3
第三个是 3 * 3 = 9
第四个是 9 * 3 = 27
......
第n个是 （n - 1) * 3 = 3n - 3这个算法很简单吧 :)

Answer 11

import java.util.*;class  HelloWorld
{
private int generate()
{
int sum = 0;for(int i = 37 ; i > 10 ; i--)
{
for(int j = i ; j > 0 ; j--)
{
if(i + j < 39)
{
for(int m = j ; m > 0 ; m--)
{
if(i + j + m < 40)
{
int n = 40 - i - j - m;
if((n <= m) && this.check(i,j,m,n))
{
sum++;
}
}
}
}
}
}
return sum;
}
private boolean check(int n1, int n2, int n3, int n4)
{
List list = new ArrayList();int aa = n1;
int bb = n2;
int cc = n3;
int dd = n4;int a = 0;
int b = 0;
int c = 0;
int d = 0;String as = "";
String bs = "";
String cs = "";
String ds = "";Integer tem = null;for(int i = 0 ; i < 40 ; i++)
{
tem = (Integer)(i + 1);
list.add(tem);
}for(int i = 0 ; i < 3 ; i++)
{
for(int j = 0 ; j < 3 ; j++)
{
for(int m = 0 ; m < 3 ; m++)
{
for(int n = 0 ; n < 3 ; n++)
{
switch(i)
{
case 0:
{
a = 0;
as = "";
break;
}
case 1:
{
a = -aa;
as = " - " + aa;
break;
}
case 2:
{
a = aa;
as = " + " + aa;
break;
}
default:
{
break;
}}
switch(j)
{
case 0:
{
b = 0;
bs = "";
break;
}
case 1:
{
b = -bb;
bs = " - " + bb;
break;
}
case 2:
{
b = bb;
bs = " + " + bb;
break;
}
default:
{
break;
}}
switch(m)
{
case 0:
{
c = 0;
cs = "";
break;
}
case 1:
{
c = -cc;
cs = " - " + cc;
break;
}
case 2:
{
c = cc;
cs = " + " + cc;
break;
}
default:
{
break;
}}
switch(n)
{
case 0:
{
d = 0;
ds = "";
break;
}
case 1:
{
d = -dd;
ds = " - " + dd;
break;
}
case 2:
{
d = dd;
ds = " + " + dd;
break;
}
default:
{
break;
}}
if(a + b + c + d > 0)
{
tem = (Integer)(a + b + c + d);
list.remove(tem);
if(list.isEmpty())
{
System.out.println("a = " + aa + " b = " + bb + " c = " + c + " d = " + d);
System.out.println("**************************************************************");
return true;
}
}
}
}
}
}
return false;
}
public static void main(String[] args) 
{
HelloWorld hello = new HelloWorld();System.out.println("There are " + hello.generate() + " results!");
}
}---------- java ----------
a = 27 b = 9 c = 3 d = 1
**************************************************************
 一定有一块是1磅！！！！

Answer 12

其实就是求这样的方程的通项拉
a0=1;
ai=Sum(a0+...+a[i-1])*2+1，
记得好像是可以用差分方程解出来的，可惜不记得怎么做的了:(

Answer 13

mooninsun() ( )  
 
? 
1,3,9,27
 
 
肯定是错的2就拼不出来了

Answer 14

lyf040230427(枫叶)钱的算法和砝码的算法是不同的
原因在于:
两个重量不同的砝码可以放在天平的两边产生一个重量为(大砝码-小砝码)重量的砝码
所以可以用-法可是钱的组合,你不可能把一个10块钱和一个3块钱一起给人家,然后告诉人家这是7块钱吧....所以,钱只能用+法....

Answer 15

public class Test
{
private int generate()
{
int sum = 0;for(int i = 37 ; i > 10 ; i--)
{
for(int j = i ; j > 0 ; j--)
{
if(i + j < 39)
{
for(int m = j ; m > 0 ; m--)
{
if(i + j + m < 40)
{
int n = 40 - i - j - m;
if((n <= m) && this.check(i,j,m,n))
{
sum++;
}
}
}
}
}
}
return sum;
}
private boolean check(int n1, int n2, int n3, int n4)
{
boolean[] check = new boolean[40];
for(int i=0;i<40;i++)
check[i]=false;
for(int i1=-1;i1<=1;i1++)
{
for(int i2=-1;i2<=1;i2++)
{
for(int i3=-1;i3<=1;i3++)
{
for(int i4=-1;i4<=1;i4++)
{
int sum=i1*n1+i2*n2+i3*n3+i4*n4;
if(sum>=1)
check[sum-1]=true;
}
}
}
}
for(int i=0;i<40;i++)
if(check[i]==false)
return false;
System.out.println("a="+n1+" b="+n2+" c="+n3+" d="+n4);
return true;
}
public static void main(String args[])
{
Test newTest= new Test();
System.out.println("There is/are "+newTest.generate()+" result(s).");
}
}答案:a=27 b=9 c=3 d=1

Answer 16

JAVA交流群-22065798
互相学习  互相提高

Answer 17

java交流群-22065798
互相学习 共同提高

Answer 18

俺来给数学证明吧
问题扩展为称重1-n任意整数磅的物体
首先可以知道一定有1磅的砝码
假设已经找到k个砝码（用a(i)表示，其中i=1...k;a(i)从小到大排列）能够称重1-N磅的任意整数磅的物体
现在考虑增加一个砝码a(k+1)使得k+1个砝码能够称重更多任意整数磅的物体
那么增加的砝码a(k+1)的重量的最大值为2N+1（大家思考一下）
这里有等式
a(1)+a(2)+...+a(i)+...+a(k)=N
a(k+1)=2N+1方便起见记S(k)=a(1)+a(2)+...+a(i)+...+a(k)则a(k+1)=2S(k)+1
(1)当k=1时a(2)=2*a(1)+1=3(2)当k>=2时a(k+1)-a(k)=2S(k)+1-(2S(k-1)+1)=2*a(k)
   即 a(k+1)=3*a(k)
   为等比数列
   a(k)=3^(k-2)*a(2)=3^(k-1)   (*)
  (*)式也满足a(1)=1的情况
综上有
当k个砝码的重量为a(i)=3^(k-1) 其中i=1....k能够称重1-N任意重量的物体
其中N=S(k)=(3^k - 1)/2

Answer 19

zdsdiablo(十分钟年华老去) ( ) 信誉：100 mooninsun() ( )  
 
? 
1,3,9,27
 
 
肯定是错的2就拼不出来了
// 怎么拼不出来天平的左边放   天平的右边
物体+1         3如果平衡 物体=2天平的左边放   天平的右边
物体           1+3如果平衡 物体重=4 
依次类推。。

Answer 20

晕
看来写JAVA 要学号数学啊!!!
现在意识到了 !!!!!!!!!!

Answer 21

fangshao(方少) ( ) 信誉：100  2006-3-28 21:14:51  得分: 0  4个里面取一个有4种方法
4个里面取2个有12种方法
4个里面取3个有4种方法
4个里面有取个有1种方法
中共只有21种组成方法  请问 1－40  40种组成方法能成立吗？无解...........................想法很有创意，但是取3个和取4个时并不是一种取法只能表示一种整数质量
比如1，3，9，可以表示13，可以表示5，11，这个题目是可以相减的。另外我觉得这道题的算法毕竟只适用这一类型题，如果求所有解，自然是要有些复杂的算法，
如果只求一个解，3的n次幂就可以了