各位大俠, 現有一復雜題請教, 酬金1000(100分)

  • 主题发起人 主题发起人 rixin
  • 开始时间 开始时间
R

rixin

Unregistered / Unconfirmed
GUEST, unregistred user!
要在n條記錄中有一字段quantity(值<500)
找出所有2個相加為500的記錄, 找出的記錄取出待用,
餘下記錄, 找出所有3個相加為500的記錄, 找出的記錄取出待用,
餘下記錄, 找出所有4個相加為500的記錄, 找出的記錄取出待用,
餘下記錄, 找出所有5個相加為500的記錄, 找出的記錄取出待用,
餘下記錄, 找出所有6個相加為500的記錄, 找出的記錄取出待用,
.....一直到找不出...


請提供算法, 最好有程序

多謝!
 
使用交叉表：
Select * from Table T1,Table t2 Where T1.quantity+T2.quantity=500

如果要求同一条记录不能自身相加，只要再加一个条件就行了，比如 T1.ID<>T2.ID
 
如果用交叉表 找20個相加為500的时候怎么办啊
还是先把记录读到本地数组里自己找算法比较妥当。
 
如果只要20条用 Select Top 20 * from ....
 
hi, 已加過記錄不可以重複相加 .....
 
好像不对吧：为什么在“找出所有2個相加為500的記錄”的时候您没有用“Select Top 2 * from ....”呢？
再说，这样做也不可能实现“取出待用”的效果。

同意g622的观点。这个问题不是数据库问题，而是纯粹的算法问题。（我估计此算法的复杂度远大于n^3）
 
不是很复杂吧，用递归就能办到
 
数据库实现最简单，首先将此表复制一个临时表出来，另外再建一个存放结果的临时表，表
结构中多加一个FIELD存放是2个记录相加还是3,4，5，...n个相加等于500。
即有SourceTable,TempTable,ResultTable.只对TempTable进行操作， 当为 n条记录相加
为500时，将TempTable中满足n-1条相加为500的记录删除。用一个存贮过程，其中要
定义CURSOR，且用递归。或不用定义CURSOR，如果预先知道最大的N值(可用SELECT
FROM RODER BY 要累加字段 DESC 求出最大N)，且不太大时，
定义N个TempTable的别名处理。另外，试试可否在存贮过程中用@VAR替代FROM后的表名及WHERE后
的条件表达式，如果可以，用一个循环即可搞定。
 
算法不复杂，不过确实需要一个临时表或者数组。
好在你的字段quantity估计是整形，所以可以这样简化一下：
查quantity=1的记录，查quantity=499的记录与之对应；
……
直到250
 
得循环好多次呢，还是把记录号和值用数组取出，查找完一次就把满足条件的取出来，
这样可以逐步减少计算量。
 
一个思路：

用一个结构体数组存放数据库中出现的分值（排除重复的情况）以及每个分值对应的记录号（可以采用链表），
并从小到大进行排序（便于以后计算分值和的时候使用二分法查找）。对排序后的数组用递归的方法计算2-20个
分值的和为500的情况，每找完一种情况的所有匹配，就将它们从数组中删除（顺便获得这些分值对应的记录号），
然后进行下一种情况的匹配，直到最后一种情况——20个相加为500的搜索结束。
在具体搜索的时候，还有一些细节要处理。例如：某个分值有多少个记录相对应——1个分值为250的记录不能
算在两个相加为500的情况里，如果有2个或2个以上的分值为250的记录就可以了。

下面给出数组元素的结构定义：
CalRec=Record
Grade:Word;
Number:Integer; //成员数
UsedNumber:Integer; //在计算中使用了的成员个数，也可以采用剩余的可以参加计算的成员数
Member:Pointer; //成员链表指针
end;

我的算法基于如下规则：如果某一分值的记录在某此搜索中被选中（取出待用），则所有此分值的元素都将被
取出。例如： 300 200 200 在第一次搜索时（2个相加=500）都将被取出，而不是还剩余一个200的。

最近在写论文，具体算法就不写了。
 
多謝各位大俠,

我現想一種方法, 請大家討論:

先將所有數量放入一數組中, 從 3 到 N 將 10 進制轉成 2 進制,

利用2進制進位特點 , 可以遍歷所有情況.

但是不知有 10 進制轉成 2 進制及 2 進制轉成10 進制 函數
 
還有沒有好方法?
 
31:2 44:7 45:4 57:8 74:10 79:10 90:8 94:2 114:4 131:7 151:4 155:9 167:8
177:4 190:7 203:5 221:9 235:6 241:1 254:7 258:2 271:8 277:6 297:10 312:8
328:4 341:10 357:1 359:10 364:4 371:6 386:1 392:4 402:4 411:6 413:1 415:6
429:9 442:9 452:4 460:9 474:9 482:8 487:7
共 45 个元素.

Level 2 begin.
1个114 1个386
1个203 1个297
****** A level done! ******
114 203 297 386
共减少了 4 个元素

Level 3 begin.
1个44 1个45 1个411
1个44 1个221 1个235
1个57 1个79 1个364
1个57 1个131 1个312
1个74 1个155 1个271
1个79 1个167 1个254
2个94 1个312
2个155 1个190
****** A level done! ******
44 45 57 74 79 94 131 155 167 190 221 235 254 271 312 364 411
共减少了 17 个元素

Level 4 begin.
****** Find nothing in this level! ******

Level 5 begin.
2个31 2个90 1个258
****** A level done! ******
31 90 258
共减少了 3 个元素

Level 6 begin.
****** Find nothing in this level! ******
...
Level 20 begin.
****** Find nothing in this level! ******

耗时不到1秒。使用了我上面提到的算法，如何？
如果您认为我的程序有必要贴出来，说个话。 :-))
 
creation-zy:

煩請把源程序貼一下歐...Thanks
 
循环（i = 0 ; i < 记录总数； i++）
循环 (x=i;x <记录总数； x++ )
如果 成立
加入临时表；
 
经过完善并优化的程序出台了！ ^_^

{递归求和 Ver 1.0 by creation_zy (creation-zy) 2001-6}
const
MaxGrade=499;
AimNumber=500;
type
CalRec=Record
Grade:Word;
Number:Integer; //成员数
UnusedNumber:Integer; //剩余的可以参加计算的成员数
end;
var
RecArray:array[1..MaxGrade] of CalRec; //必须保证分值从小到大
RecCount:Integer;
UsedResults:array[1..MaxGrade]of Boolean;
procedure Add_Line(Str:String);
begin
Form1.Memo1.Lines.Add(Str);
end;
procedure PrepareArray;
var
i:Integer;
begin
for i:=1 to MaxGrade do
UsedResults:=false;
for i:=1 to RecCount do
RecArray.UnusedNumber:=RecArray.Number;
end;
function ValidArray(const Level:integer):Byte;
var
i,Sum,Number:Integer;
begin
Sum:=0;
for i:=1 to RecCount do
Inc(Sum,RecArray.Number);
if Sum<Level then
begin
Result:=3; //总成员数小于相加个数
Add_Line(Format('总成员数小于相加个数!: %d<%d',[Sum,Level]));
exit;
end;
Number:=Level;
Sum:=0;
for i:=1 to RecCount do //计算可能最小值
begin
if RecArray.Number<Number then
begin
Dec(Number,RecArray.Number);
Inc(Sum,RecArray.Number*RecArray.Grade);
end
else begin
Inc(Sum,Number*RecArray.Grade);
break;
end;
end;
if Sum>AimNumber then
begin
Result:=2; //可能最小值已经超过目标值
Add_Line(Format('可能最小值已经超过目标值! %d',[Sum]));
exit;
end;
Number:=Level;
Sum:=0;
for i:=RecCount downto 1 do //计算可能最大值
begin
if RecArray.Number<Number then
begin
Dec(Number,RecArray.Number);
Inc(Sum,RecArray.Number*RecArray.Grade);
end
else begin
Inc(Sum,Number*RecArray.Grade);
break;
end;
end;
if Sum<AimNumber then
begin
Result:=1;
Add_Line(Format('可能最大值小于目标值! %d',[Sum]));
exit;
end;
Result:=0;
end;
procedure CalLevel(const Count,Aim,MinNumber:Integer);
var
i:Integer;
Str:String;
begin
if (Count<0) or (Aim<0) then
exit;
if (Count=0) and (Aim<>0) then
exit;
if (Count=0) and (Aim=0) then
begin
Str:='';
for i:=1 to RecCount do
begin
with RecArray do
begin
if Number>UnusedNumber then
begin
Str:=Str+Format('%d个%d ',[Number-UnusedNumber,Grade]);
UsedResults[Grade]:=true;
end;
end;
end;
Add_Line(Str);
exit;
end;
for i:=MinNumber to RecCount do
begin
with RecArray do
begin
if Grade>Aim then //由于分值是依次增大的...
break;
if UnusedNumber>0 then
begin
Dec(UnusedNumber); //使用
CalLevel(Count-1,Aim-Grade,i); //以后的搜索起始层数不会比这一层小
Inc(UnusedNumber); //释放
end;
end;
end;
end;
procedure PackRecArray; //将使用过的元素从数组中剔除
var
i,j,DecCount:Integer;
Str:String;
begin
DecCount:=0; //在搜索中被取出待用的元组数目
with Form1.Memo1.Lines do
begin
Str:='';
j:=1;
for i:=1 to MaxGrade do
begin
if UsedResults then
begin
while RecArray[j].Grade<>i do
Inc(j);
RecArray[j].Number:=0;
Str:=Str+IntToStr(i)+' ';
Inc(DecCount);
end;
end;
if DecCount>0 then
begin
Add('****** A level done! ******');
Add(Str);
Add('共减少了 '+IntToStr(DecCount)+' 个元素');
end
else
Add('****** Found nothing in this level! ******');
end;
if DecCount>0 then
begin
for i:=1 to RecCount-DecCount do
if RecArray.Number=0 then
begin //找到一个未用元素，补上
for j:=i+1 to RecCount do
if RecArray[j].Number>0 then
begin
RecArray.Grade:=RecArray[j].Grade;
RecArray.Number:=RecArray[j].Number;
RecArray[j].Number:=0;
break;
end;
end;
Dec(RecCount,DecCount);
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
i,n:Integer;
Str:String;
OldTime:DWord;
begin
Randomize;
n:=1;
Str:='';
for i:=1 to MaxGrade do
begin
Inc(n,Random(20)+1);
if n>MaxGrade then
begin
RecCount:=i-1; //数组中元素的个数
break;
end;
with RecArray do
begin
Grade:=n;
Number:=Random(10)+1; //1-3个成员
Str:=Str+Format('%d:%d ',[Grade,Number]);
end;
end;
with Memo1 do
begin
Text:='';
Lines.Add(Str);
Lines.Add('共 '+IntToStr(RecCount)+' 个元素.');
end;
Application.ProcessMessages;
Memo1.Lines.BeginUpdate;
OldTime:=GetTickCount;
for i:=2 to AimNumber do
begin
Add_Line('Level '+IntToStr(i)+' begin.');
n:=ValidArray(i); //验证是否可能找到解
if (n=3) or (n=2) then
break
else if n=1 then
continue;
PrepareArray;
CalLevel(i,AimNumber,1);
PackRecArray;
if RecCount=0 then
begin
Add_Line('数组元素已经耗尽。');
break;
end;
end;
Caption:='耗时：'+IntToStr(GetTickCount-OldTime)+' ms';
Memo1.Lines.EndUpdate;
end;

一般情况下耗时0-20ms，极少数情况下在200-500ms之间（PIII800）。比数据库操作不知要快多少倍。
如有错误之处，还请大家批评指正。
 
creation-zy:

你的方法是我看到的最快方法,若無其他更好的方法,(下週內)分就是你的了.
(我將另開一題給你其餘分)

由於實際應用中要求, 若有時間, 煩請回答:

1. 重復統計處理:
(請改 Number:=Random(1)+1; //1個成員)
可見有重復現象

2. 找出的記錄要做處理, 也就是說:
放入數組中的每一個值都須要與庫中記錄對應
如: 有2個18與2個482可組合,
但須要知道這4個數在原數據庫中的對應位置.

thanks
 
1.您的意思是不是：
若有100 120 160 240 280，则在找到100 120 280的组合之后就立即取出，不再会找到100 160 240的
组合，而若有两个100的成员，就可以全部找到？
if Yes ——我已经写了一个更加优秀的算法。(按此规则，将AimNumber改为1500，80%的情况下<=100ms)
else if '而若有...' 之前为真，之后为假 then ...

2.我说过了，在CalRec结构中增加一个指针，指向成员链表，在链表中存放它们在数据库中的位置。
 
您必须登录或注册才可回复。

Similar threads

杜
這條sql語句有什麼問題？請幫忙!(30分)
回复
8
查看
135
luky_99
L
S
在ADO主從明細表中﹐明細表中插入一條記錄﹐不能保存在原位置﹐總是跑到所有記錄后面﹐請問如何解決﹖(100分)
回复
4
查看
139
ysai
Y
W
各位大哥,query舊題重提(30分)
回复
7
查看
93
火麒麟
火
N
實現一對多窗體時遇到問題.....,急!(100分)
回复
3
查看
126
thgerman
T
H
一個關于多數據庫查詢的問題﹐高分請教(100分)
回复
5
查看
160
hongxinyan
H
后退
顶部