孤魂居士 发表于 2008-4-18 11:50

帮帮兄弟我求算法

今天遇见了一题目，也许论坛里兄弟们都遇见过了 但是小弟愚昧 想不出来 帮帮兄弟我吧

1，    1--40个数
2，    在里面找i,j,k,l 任意4个数
3，    满足条件：第一：i,j,k,l各不相等。  第二：i,j,k,l  这4个数相互加减可以得到1--40里面任何一个数
  
例如：假如i=1,j=2,k=3,l=4
j-i=1
k-i=2
l-i=3
k+i=4
l+i=5
l+j=6
l+k=7
l+i+k=8
l+k+i+j=9
.
.
但是11就表示不出来了··所以不能为1 2 3 4..
只能用加减 随便怎么加 怎么减 只能这4个数之间···
兄弟们帮帮忙··感激中··
.

孤魂居士 发表于 2008-4-18 13:36

[tk01] 伤心啊··
哪位兄弟帮下忙啦

sunkaidong 发表于 2008-4-18 13:38

你找燕子和孔明问问...他们对算法很感兴趣

孤魂居士 发表于 2008-4-18 15:14

[tk01]
好··谢谢啦

野比 发表于 2008-4-18 19:54

HJin的算法造诣很深。。不过他都是用洋文说话。。。

卧龙孔明 发表于 2008-4-18 20:20

直接枚举(搜索),为提高效率,可考虑:
1.搜索时保证i<j<k<l,这样可以将效率提高许多
2.搜索时保证i+j+k+l>=40,否则减枝
3.搜索时保证l-k-j-i<40,否则减枝

wetwood 发表于 2008-4-18 22:16

设i,i+1,j,k是四个数。
设(a,b,c,d)其中每个元素的取值为(-1，0，1)。用向量(a,b,c,d)和(i,i+1,j,k)相乘就可得出标准表示式，然后再比较

flylee 发表于 2008-4-18 23:01

楼上正解

leeco 发表于 2008-4-20 00:02

刚才算了一下，
40C4 * (4C1 * 2^0 + 4C2 * 2^1 + 4C3 * 2^2 +4C4 * 2^3)
恰好＝40

所以可以有一个非常强的剪枝条件，就是任意的组合算出的数和之前的组合算出的数都不重复

页: [1]

编程论坛