编程论坛 → C++教室

帮帮兄弟我求算法

孤魂居士发布于 2008-04-18 11:50， 811 次点击

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

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个数之间···
兄弟们帮帮忙··感激中··
.

8 回复

#2

孤魂居士2008-04-18 13:36

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

#3

sunkaidong2008-04-18 13:38

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

#4

孤魂居士2008-04-18 15:14

好··谢谢啦

#5

野比2008-04-18 19:54

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

#6

卧龙孔明2008-04-18 20:20

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

#7

wetwood2008-04-18 22:16

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

#8

flylee2008-04-18 23:01

楼上正解

#9

leeco2008-04-20 00:02

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

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

1