难！算法，已知和，求数值

Question

怎样求出1-20中任取四个数（不能重复），四个数之和为28的所有组合

Answer 1

直接穷举procedure TForm1.Button1Click(Sender: TObject);
var
  i, j, k: Integer;
begin
  Memo1.Lines.Clear;
  for i := 1 to 20 do
    for j := i + 1 to 20 do
      for k := j + 1 to 20 do
        if (i + j + k > 7) and (i + j + k + k < 28) then
          Memo1.Lines.Add(IntToStr(i) + '+' + IntToStr(j) + '+' + IntToStr(k)
              + '+' + IntToStr(28 - i - j - k) + '=28');
end;

Answer 2

改进型一：
procedure TForm1.Button1Click(Sender: TObject); 
  var  i, j, k: Integer; 
begin  
  Memo1.Lines.Clear; 
  for i := 1 to 20 do
    for j := i + 1 to 20 do
    Begin
      If i+j>=28 Then
      Break;  
      for k := j + 1 to 20 do
      Begin
      If i+j+k>=28 then
      Break;  
        if (i + j + k > 7) and (i + j + k + k < 28) then 
          Memo1.Lines.Add(IntToStr(i) + '+' + IntToStr(j) + '+' + IntToStr(k) + '+' + IntToStr(28 - i - j - k) + '=28'); 
      End;    
End;
end;
第二层循环或第三层循环的时候和已经大于或等于28 
再循环下去已经没有必要了
还有比这更好的方法
 正在想.......

Answer 3

procedure TForm1.Button1Click(Sender: TObject);
var
  n, i, j, k: Integer;
begin
  Memo1.Lines.Clear;
  n := 0;
  for i := 1 to 20 do
    for j := i + 1 to 20 do
      for k := j + 1 to 20 do
      begin
        if (28 - i - j - k <= 20) and (28 - i - j - k >= k + 1) then
          Memo1.Lines.Add(IntToStr(i) + '+' + IntToStr(j) + '+' + IntToStr(k)
              + '+' + IntToStr(28 - i - j - k) + '=28');
        Inc(n);
      end;
  Memo1.Lines.Add('穷举循环次数：' + IntToStr(n));
end;穷举循环次数：1140

Answer 4

钻牛角尖了吧。
看看别人的代码吧
if (28 - i - j - k <= 20) and (28 - i - j - k >= k + 1) then
这句判断应该不难看懂吧？
汗~

Answer 5

其实，题目让求的是组合数，不是排列数，所以不妨设i<j<k<l
i最小，所以i肯定要小于28/4，即i<7,所以i要控制在:1<=i<=6
j最小要为2，若i为1，则j最大为27/3(达不到，因为还有k,l）,所以:2<=j<=8
同理:k最小为3，最大达不到25/2，即3<=k<=12
所以可将dulei115 兄弟的代码循环控制改一下，共有82种组合，循环次数164
要下班了，我仓促回答，疏漏之处请批评

Answer 6

1 <=i <=6
i+1 <=j <=8 
j+1 <=k <=12 

Answer 7

HelloMicrosoft ,你所说的20的4次方是16万次，从里面找出82种组合，我从164次循环里找出来，“毕竟……”什么呢？不会是要从82次循环里找出82种组合吧，关注，想出高招请分享

Answer 8

这类题不是很复杂，因为是从一个有序集合里找出满足一定条件的有限的几个组合数，而且条件比较简单。
本题中，不能过多的着眼在20这个限制条件上（其真实用途见程序），更多的是关注4个数之间的关系。
算法如下：（呵呵，楼主不想用循环，那可以用递归，欢迎指正）
procedure TForm1.Button1Click(Sender: TObject);
var
  n, i, j, k: Integer;
begin
  Memo1.Lines.Clear;
  n := 0;
  for i := 1 to (28-5) div 4 do
  // 28-5: (num+3) div 4 - 2 =(num-5) div 4;
  //+3为4整除运算余数补足;
  //-2因为4个数不重复,如果允许重复则不需，同是下面初始条件改为j=i，k=j。
    for j := i + 1 to (28-i-1) div 3 do
    // 28-i-1: (num+2) div 3 - 1 =(num-1) div 3;
    // +2为3整除运算余数补足，-1因为剩余的3个数不重复
      for k := j + 1 to (28-i-j-1) div 2 do
      //28-i-j-1: (num+1) div 2 - 1 =(num-1) div 2;
      // +1为1整除运算余数补足，-1因为剩余的2个数不重复
      begin
        if (28 - i - j - k)<=20 then
        //1~20条件用在i的初始，以及第4个数的限定;
        //如果此处if不用，则为求1~28-(1+2+3)范围内不重复;
        //1~MaxNum，Sum/MaxNum=n,如果n>1，根据n修正相应循环终止条件min(n，原终止值)。
          Memo1.Lines.Add(IntToStr(i) + '+' + IntToStr(j) + '+' + IntToStr(k)
              + '+' + IntToStr(28 - i - j - k) + '=28');
        Inc(n); //一共84次，去除1+2+3+22=28,1+2+4+21=28,一共82次
      end;
  Memo1.Lines.Add('穷举循环次数：' + IntToStr(n));
end;

Answer 9

以前做过1-100，5个数合为50的算法，和这个相似
如下代码82次，如果能实现1-N，M个数，合计为X的通用算法就好了...
var
  n, i, j, k, e:   Integer;
begin
  Memo1.Lines.Clear;
  n := 0;
  for i := 1 to (28 - 5) div 4 do
    for j := i + 1 to (28 - i - 1) div 3 do
    begin
      e := 8 - i - j;
      if e < j + 1 then e := j + 1;
      for k := e to (28 - i - j - 1) div 2 do
      begin
        Memo1.Lines.Add(IntToStr(i) + '+ ' + IntToStr(j) + '+ ' + IntToStr(k)
          + '+ ' + IntToStr(28 - i - j - k) + '=28 ');
        Inc(n);
      end;
    end;
  Memo1.Lines.Add('返回结果：' + IntToStr(Memo1.Lines.Count));
  Memo1.Lines.Add('穷举循环次数：' + IntToStr(n));
end;
楼主貌似失踪

Answer 10

递归实现，比较通用，看看谁很能优化一下
uses Math;procedure Combined( // 得到从AMin-AMax中选取ACount个数合计为ATotal的全部组合
  AMin, AMax: Integer; // 范围
  ATotal: Integer; // 合计值
  ACount: Integer; // 个数
  AOutput: TStrings // 输出
);  procedure fCombined(
    AMin: Integer; // 范围
    ASum: Integer; // 合计值
    ACount: Integer; // 个数
    APath: string // 路径
  );
  var
    I: Integer;
  begin
    if AMin > AMax then Exit;
    if ACount <= 2 then
    begin
      { TODO : 可以进一步优化 }
      for I := AMin to Min(AMax, Trunc(ASum / ACount - ACount / 2 + 0.5)) do
        if ASum - I <= AMax then
          AOutput.Add(Format('%s%d+%d=%d', [APath, I, ASum - I, ATotal]));
    end else
    begin
      for I := AMin to Min(AMax, Trunc(ASum / ACount - ACount / 2 + 0.5)) do
        fCombined(I + 1, ASum - I, ACount - 1,
          APath + IntToStr(I) + '+');
    end;
  end;begin
  if not Assigned(AOutput) then Exit;
  AOutput.BeginUpdate;
  try
    AOutput.Clear;
    fCombined(AMin, ATotal, ACount, '');
  finally
    AOutput.EndUpdate;
  end;
end;procedure TForm1.Button1Click(Sender: TObject);
begin
  Combined(10, 50, 100, 5, Memo1.Lines);
  Caption := Format('返回结果:%d', [Memo1.Lines.Count]);
end;输出结果：
[code=BatchFile]10+11+12+17+50=100
10+11+12+18+49=100
10+11+12+19+48=100
10+11+12+20+47=100
10+11+12+21+46=100
10+11+12+22+45=100
10+11+12+23+44=100
10+11+12+24+43=100
10+11+12+25+42=100
10+11+12+26+41=100
10+11+12+27+40=100
10+11+12+28+39=100
10+11+12+29+38=100
10+11+12+30+37=100
10+11+12+31+36=100
10+11+12+32+35=100
10+11+12+33+34=100
....
[/code]