[较难]组合的定位问题,(300)

  • 主题发起人 liugaohui
  • 开始时间
L

liugaohui

Unregistered / Unconfirmed
GUEST, unregistred user!
比如:12选3的所有组合有220注,01 02 03 01 02 04 01 02 05 01 02 06 01 02 07 .......09 11 12 10 11 12 如果按照生成的顺序进行标记,01 02 03为第1组, 01 02 04 为第2组,依此类推,那么 09 11 12 为第多少组?如何计算?谢谢
 
L

liuls

Unregistered / Unconfirmed
GUEST, unregistred user!
procedure TForm1.btn1Click(Sender: TObject);var iCount: Integer;
i, j, k: Integer;
TmpStr: string;
begin
iCount := 0;
for i := 1 to 12do
begin
for j := i + 1 to 12do
begin
for k := j + 1 to 12do
begin
Inc(iCount);
TmpStr := '第' + IntToStr(iCount) + '注:' + #9 + IntToStr(i) + #9 + IntToStr(j) + #9 + IntToStr(k);
mmo1.Lines.Add(TmpStr);
end;
if i >= 12 -1 then
Break;
end;
if i >= 12 -2 then
Break;
end;
end;
 
L

liugaohui

Unregistered / Unconfirmed
GUEST, unregistred user!
to liuls,谢谢回复!我觉得这种算法没有通用性,比如12选4变为30选7时,对100期历史数据均计算出第多少组时,速度很慢
 
S

smlabc

Unregistered / Unconfirmed
GUEST, unregistred user!
计算12选3,输入 a b ca<b<c所以a=1时,个数为(12-1)*(12-2)/2=55a=2时,个数为(12-2)*(12-3)/2=45...a=10时,个数为(12-10)*(12-11)/2 = 1,公式(12-a)*(11-a)/2先计算1到a-1的个数: for i := 1 to a-1do
Inc(Result, (12-i)*(11-i)/2);再计算N=a时,M=a+1到b-1的个数: for i := a+1 to b-1do
Inc(Result, (12-i));最后计算N=a,M=b时的个数 Inc(Result, c-b);
 
S

smlabc

Unregistered / Unconfirmed
GUEST, unregistred user!
function Calc(a, b, c: Integer): Integer;var i: Integer;
begin
Result := 0;
for i := 1 to a-1do
Inc(Result, Trunc((12-i)*(11-i)/2));
for i := a+1 to b-1do
Inc(Result, (12-i));
Inc(Result, c-b);
end;
比较郁闷的是Inc(Result, Trunc((12-i)*(11-i)/2));需要加个Trunc,明明就是整数了,哎,以上时间复杂度为O(N),估计没更优的了
 
L

liugaohui

Unregistered / Unconfirmed
GUEST, unregistred user!
谢谢各位,我试试
 
L

liugaohui

Unregistered / Unconfirmed
GUEST, unregistred user!
to smlabc:能否实现通用的x选y形式的,比如30选7,15选5等
 
S

smlabc

Unregistered / Unconfirmed
GUEST, unregistred user!
function Calc(a: array of Integer;
TolCount: Integer): Integer;var i, j, k, N: Integer;
begin
Result := 0;
for i := Low(a)+1 to High(a)-1do
begin
for k := a[i-1]+1 to a-1do
begin
N := 1;
for j := 1 to High(a)-ido
N := N*(TolCount+1-j-k);
for j := 1 to High(a)-ido
N := Trunc(N/j);
Inc(Result, N);
end;
end;
Inc(Result, a[High(a)]-a[High(a)-1]);
end;
如30选4:var a: array[0..4] of Integer;
//注意从0开始begin
a[0] := 0;
//注意第一位留0 a[1] := 1;
//查看1,28,29,30 的排位 a[2] := 28;
a[3] := 29;
a[4] := 30;
Caption := IntToStr(Calc(a, 30));
 
L

liuls

Unregistered / Unconfirmed
GUEST, unregistred user!
// 算阶乘function CalcFactorial(AFac: Integer): Int64;
begin
Result := 1;
while AFac > 0do
begin
Result := Result * AFac;
Dec(AFac);
end;
end;
// 算组合function CalcCombination(const ABottom, ATop: Integer): Integer;var TmpInt: Integer;
iNumerator, iDenominator: Int64;
begin
iNumerator := 1;
TmpInt := ABottom;
while TmpInt > (ABottom - ATop)do
begin
iNumerator := iNumerator * TmpInt;
Dec(TmpInt);
end;
iDenominator := CalcFactorial(ATop);
Result := iNumerator div iDenominator;// Result := CalcFactorial(ABottom) div ((CalcFactorial(ABottom - ATop) * CalcFactorial(ATop)));
end;
function Calc(const AMin, AMax: Integer;
ASelNum: Integer;
APFirst: PInteger): Integer;var I: Integer;
iCalcCount: Integer;
iFrom, iTo: Integer;
PInt: PInteger;label label1;
begin
Result := 0;
iCalcCount := 0;
PInt := APFirst;
// 第一位 Inc(iCalcCount);
iFrom := AMin;
iTo := PInt^;
for I := iFrom to iTo - 1do
Inc(Result, CalcCombination(AMax - I, ASelNum - iCalcCount));
label1: // 第 iCalcCount 位 Inc(iCalcCount);
Inc(PInt);
iFrom := iTo;
iTo := PInt^;
for I := iFrom + 1 to iTo - 1do
Inc(Result, CalcCombination(AMax - I, ASelNum - iCalcCount));
if iCalcCount < ASelNum - 1 then
goto label1;
// 最后一位// Inc(iCalcCount);
Inc(PInt);
iFrom := iTo;
iTo := PInt^;
Inc(Result, iTo - iFrom);
end;
procedure TForm1.btn1Click(Sender: TObject);var PSelFirst: PInteger;
SelArr: array of Integer;
begin
SetLength(SelArr, 7);
SelArr[0] := 30;
SelArr[1] := 31;
SelArr[2] := 32;
SelArr[3] := 33;
SelArr[4] := 34;
SelArr[5] := 35;
SelArr[6] := 36;
PSelFirst := @SelArr[0];
Caption := IntToStr(Calc(1, 36, 7, PSelFirst));
// 会等于 CalcCombination(36, 7) // Caption := IntToStr(Calc(2, 36, 7, PSelFirst));
// 会等于 CalcCombination(35, 7)end;
 
S

smlabc

Unregistered / Unconfirmed
GUEST, unregistred user!
测试了下效率,都差不多,10000次运行速度大概都在100毫秒左右.var PSelFirst: PInteger;
i: Integer;
SelArr: array of Integer;
begin
SetLength(SelArr, 7);
SelArr[0] := 30;
SelArr[1] := 31;
SelArr[2] := 32;
SelArr[3] := 33;
SelArr[4] := 34;
SelArr[5] := 35;
SelArr[6] := 36;
PSelFirst := @SelArr[0];
N := GetTickCount;
for i := 1 to 10000do
Calc(1, 36, 7, PSelFirst);
N := GetTickCount-N;
Caption := IntToStr(N);以及var SelArr: array[0..7] of Integer;
i: Integer;
begin
SelArr[0] := 0;
SelArr[1] := 30;
SelArr[2] := 31;
SelArr[3] := 32;
SelArr[4] := 33;
SelArr[5] := 34;
SelArr[6] := 35;
SelArr[7] := 36;
N := GetTickCount;
for i := 1 to 10000do
Calc1(SelArr, 36);
N := GetTickCount-N;
Caption := IntToStr(N);
 
L

liugaohui

Unregistered / Unconfirmed
GUEST, unregistred user!
谢谢两位高手,我看看,尽快结帖
 
L

liugaohui

Unregistered / Unconfirmed
GUEST, unregistred user!
请两位先去领分,随后结帖http://www.delphibbs.com/delphibbs/dispq.asp?lid=3941999
 
L

liugaohui

Unregistered / Unconfirmed
GUEST, unregistred user!
多人接受答案了。
 

Similar threads

D
回复
0
查看
761
DelphiTeacher的专栏
D
D
回复
0
查看
714
DelphiTeacher的专栏
D
D
回复
0
查看
705
DelphiTeacher的专栏
D
D
回复
0
查看
2K
DelphiTeacher的专栏
D
顶部