急求一个算法，请高手指点
已知:一百个不连续的数(有小数也有整数)，并知道一个结果A
我希望从这一百个数里找出四个数相加等于上面那个已知的结果A，请高手给出
实现的逻辑或代码，谢谢各位！！！！！！！！
问题点数：0、回复次数：18Top
1 楼mq612（五斗米）回复于 2003-12-02 17:44:40 得分 0
用4个for把所有可能性都试一遍。
Top
2 楼xiaohaiz（城里的老土，两眼依然通红！）回复于 2003-12-02 17:51:37 得分 0
命题不严格嘛。是要一个结果？还是所有可能的结果？
重复算不算？比如A=100，队列中有一个25，捡出来4次相加也得100，算不算？
分析无法做，哪里来得试验。Top
3 楼ddbean（Welsh）回复于 2003-12-02 17:54:26 得分 0
不如楼主把题目改一改Top
4 楼haroldzhh（haroldzhh）回复于 2003-12-03 13:54:52 得分 0
xiaohaiz(老土进城,两眼通红)：
我想要不重复的结果，一个就可以了Top
5 楼crazyman700（crazyman700）回复于 2003-12-03 14:25:01 得分 0
题目不严谨Top
6 楼79cy（火焰）回复于 2003-12-03 14:58:51 得分 0
这些数如果是大小有序的，可以采用分类的方法，
比如A=100，队列中如下：1，2，...37，89，98，99等，将1，2，等较小的（既i*4也<100）分为一类，将98，99等较大的分为另一类（既i*4也>>100），可以跳过选取89，98，99，87这样的组合，能减少部分工作量，至于如何分组看楼主的意思了，这个分组法还不是很成熟。Top
7 楼79cy（火焰）回复于 2003-12-03 15:20:35 得分 0
再补充几句：
这个方法的主要是可以排除一些明显不符合条件的组合，比如4个数相加太小或是太大的数组合。比如，我们取了1这个类中的3个数，将直接去99这个类中取，而不用再在1这个类里去实验，因为肯定不合适。Top
8 楼qm0445（海狗）回复于 2003-12-03 15:24:40 得分 0
HOHO！帮UP：）Top
9 楼xiaohaiz（城里的老土，两眼依然通红！）回复于 2003-12-03 17:13:50 得分 0
俺暂时没有想到有什么更好的算法来处理，但是正常的想法就是4次遍历。可以就此方法展开一下。1楼的兄弟“mq612(理想)”提出的做法是一个很自然的做法，“用4个for把所有可能性都试一遍。”俺们可以肯定这一定是可行的。类似这样：
<<
for( ... )
for ( ... )
for ( ... )
for ( ... )
>>
但是楼主的条件是又不允许重复，所以还需要加上很多判断的临时标示变量。另外，如果变化数目，修改量也是很大，语句就变得很复杂。所以，俺们可以看看有没有更好的办法来做这些遍历。
换一个思路这么看，这一系列数据（100个），可以看作一个聚集来处理。需要做的就是使用迭代来遍历所有的数据，而且可能需要多次迭代（需要2个数就迭代2次，需要3个数就迭代3次，类推），这样，无论需要多少个数，只要多次迭代嵌套就可以了。问题在于，如何在一次迭代的时候避免其他的迭代当前正在处理的INDEX（避免重复）。于是，俺们可以考虑增加一个迭代的缓存来实现这点重复的剔除。俺做了这么一个聚集的简单实现如下：
<<
final class NumberCollections {
private final Map iteratorBuffer = new HashMap();
private final BigDecimal[] nums;
public NumberCollections(BigDecimal[] nums) {
if(nums==null) throw new NullPointerException();
this.nums = new BigDecimal[nums.length];
System.arraycopy(nums, 0, this.nums, 0, nums.length);
}
public Iterator iterator() {
Iterator it = new DefaultIterator();
iteratorBuffer.put(it, new Integer(0));
return it;
}
// private :
private boolean isIndexInBuffer(Iterator thisIt, int index) {
for(Iterator it=iteratorBuffer.keySet().iterator();it.hasNext();) {
Iterator each = (Iterator)it.next();
if(each==thisIt) continue;
Integer eachIndex = (Integer)iteratorBuffer.get(each);
if(eachIndex.intValue()==index) return true;
}
return false;
}
private void updateBuffer(Iterator it, int currentIndex) {
if(!iteratorBuffer.containsKey(it)) return;
iteratorBuffer.put(it, new Integer(currentIndex));
}
private void removeBuffer(Iterator it) {
iteratorBuffer.remove(it);
}
private class DefaultIterator implements Iterator {
private int index = 0;
public boolean hasNext() {
if(index==nums.length) {
removeBuffer(this);
return false;
}
for(int i=index;i<nums.length;i++) {
if(!isIndexInBuffer(this, i)) return true;
}
removeBuffer(this);
return false;
}
public Object next() {
for(int i=index;i<nums.length;i++) {
if(!isIndexInBuffer(this, i)) {
updateBuffer(this, i);
index = i+1;
return nums[i];
}
}
return null;
}
public void remove() {
throw new UnsupportedOperationException();
}
}
}
>>
由于楼主的数据允许整型和浮点，所以使用BigDecimal来处理之。关键在于DefaultIterator这个迭代的实现类和iteratorBuffer的交互处。程序写的比较仓促。:)
在这样的聚集的前提之前，客户端就可以不用处理迭代的逻辑了，只需要简单的嵌套进行迭代即可（应该还有更好的方式来处理）。
简单的例子如下：
<<
NumberCollections nc = new NumberCollections(nums);
for(Iterator it1=nc.iterator(); it1.hasNext(); ) {
BigDecimal n1 = (BigDecimal)it1.next();
for(Iterator it2=nc.iterator(); it2.hasNext(); ) {
BigDecimal n2 = (BigDecimal)it2.next();
for(Iterator it3=nc.iterator(); it3.hasNext(); ) {
BigDecimal n3 = (BigDecimal)it3.next();
for(Iterator it4=nc.iterator(); it4.hasNext(); ) {
BigDecimal n4 = (BigDecimal)it4.next();
if(validate(n1,n2,n3,n4)) {...}
}
}
}
}
>>
只需要实现validate方法来验证是否是需要的组合就可以了。
BTW，如果数据量很大，这样的算法一定效率非常低下，并不推荐采用。Top
10 楼silverswords（笨笨虫冲）回复于 2003-12-03 17:36:13 得分 0
分组的方法应该是能减少运算量的
首先对100个数字进行排序
然后分4组
初步设定个组的边界值为 0，25，75，100
（如果100个数里有这几个值正好，没有也无所谓，最后去掉包含这4个数的组合就是）
这样，我们可以得到4组数据
0～25，26～50，51～75，76～100
A B C D
下面可以通过简单的分析得到一些规律
2A+2B=100
2A+C=100
A+C=100
2A+D=100
(也许还有，数字的意思是从该区域取多少个)
由于我们要求是4个数字相加，且不重复
这样，可能的取法
2A+2B
(呵呵，好像就这么一种吧)
嗯，思路是这样的，算是抛砖引玉吧
^_^Top
11 楼silverswords（笨笨虫冲）回复于 2003-12-03 17:37:39 得分 0
嗯，还有
3A+C
3A+D
这下应该没有了
Top
12 楼silverswords（笨笨虫冲）回复于 2003-12-03 17:40:07 得分 0
还有
3A+B
也有可能等于100
呵呵
其实这些可能的组合
也可以通过程序推出来的
有兴趣自己推吧
Top
13 楼binbin2000（binbin）回复于 2003-12-03 17:40:59 得分 0
三步走
一，排序
二，找到比A大的位置
三，选择，从找到的位置往小的方向选择4个数，如果和为A。ok。最后找完为止。Top
14 楼stonecsdn（东东）回复于 2003-12-03 18:04:41 得分 0
如果不允许重复，用四个for 也是可以的（前提不考虑数据结构和时间复杂度）：
假设数据存放在Array中，
for(int i=0;i<Array.length;++i){
for(int j=0;j<Array.length;++j){
if(i==j) break;
for(int k=0;k<Array.length;++k){
if((k==i)||(k==j)) break;
for(int n=0;l<Array.length;++l){
if((n==i)||(n==j)||(n==k)) break;
if((Array[i]+Array[j]+Array[k]+Array[n])==result)
....相关处理
}
}
}
}
如果要提高效率，最好先进行排序，向楼上几位提的。防止计算向四个大于50的数的相加。Top
15 楼xiaohaiz（城里的老土，两眼依然通红！）回复于 2003-12-03 18:18:04 得分 0
谢谢silverswords(笨笨虫冲)，提出的分组算法确实能够很大程度减少运算量，比4次遍历强太多了。不过那样的分组算法还不够完善，俺来补充一下：
首先，对整个数列进行排序，俺们可以想象这些数分布在一条数轴之上。
然后，俺们可以剔除无解的情况？两种无解：
(1) 最小的连续4个数相加大于A无解；
(2) 最大的连续4个数相加小于A无解；
接下来，俺们可以把A线段提出来，A线段多大？从最小数点到A点的距离即为A线段的长度。
然后，把A线段平均切分为4段，记为S1, S2, S3和S4。然后把数轴上所有数列中的数放入到相应的4段中（在这一步就可能可以剔除很多无用的数据了）
下面要做的事情，就是按照“silverswords(笨笨虫冲)”推出的公式进行遍历计算，得到所有可能得到A的值，比如 3S1 + S3 = A; 3S1 + S4 = A; 2S1 + 2S2 = A。
如果算法修改成这样，确实效率会得到很大的改善。
Top
16 楼stonecsdn（东东）回复于 2003-12-03 21:55:25 得分 0
不好意思,上面的break应换为continue;Top
17 楼79cy（火焰）回复于 2003-12-04 09:55:03 得分 0
昨天又想了一下，我认为分组应该以分数为为界线，以100为例，因为取四个数，所以分4段，分界点分别为100/2，100/3，100/4，这样可以在四重嵌套循环中，分取这四类数据，比如上述数据分别为A类（<25），B类(>25&&<33)，C类(>33&&<50)，D类(>50&&100),这样在取了3个A类数据后，可以直接去取D类数据，而不用考虑B类，C类。
取数的思路是：首先4个数中必有A类，其次D类的数最多1个，C类的数最多2个，B类的数最多3个，而A类的数最多为3个，而取数与顺序无关。
所以可以规定第一个数必须为A类，第二个数可以任选A，B，C，D类，第三个数可以根据思路排除一些不可能的选取法，第四种一般可以根据前3个数的类型唯一确定它的类型。Top
18 楼fantasyCoder（Attitude is everything）回复于 2003-12-04 10:45:54 得分 0
用回朔！！！Top
