急求一个算法，请高手指点

Question

用4个for把所有可能性都试一遍。

Answer 1

xiaohaiz(老土进城,两眼通红)：   我想要不重复的结果，一个就可以了

Answer 2

这些数如果是大小有序的，可以采用分类的方法，
比如A=100，队列中如下：1，2，...37，89，98，99等，将1，2，等较小的（既i*4也<100）分为一类，将98，99等较大的分为另一类（既i*4也>>100），可以跳过选取89，98，99，87这样的组合，能减少部分工作量，至于如何分组看楼主的意思了，这个分组法还不是很成熟。

Answer 3

俺暂时没有想到有什么更好的算法来处理，但是正常的想法就是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，如果数据量很大，这样的算法一定效率非常低下，并不推荐采用。

Answer 4

分组的方法应该是能减少运算量的
首先对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
(呵呵，好像就这么一种吧)嗯，思路是这样的，算是抛砖引玉吧
^_^

Answer 5

嗯，还有
3A+C
3A+D
这下应该没有了

Answer 6

三步走
一，排序
二，找到比A大的位置
三，选择，从找到的位置往小的方向选择4个数，如果和为A。ok。最后找完为止。

Answer 7

如果不允许重复，用四个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的数的相加。

Answer 8

谢谢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。如果算法修改成这样，确实效率会得到很大的改善。

Answer 9

不好意思,上面的break应换为continue;

Answer 10

昨天又想了一下，我认为分组应该以分数为为界线，以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个数的类型唯一确定它的类型。