關於變數加減的問題（邏輯）

發表時間：2007-10-22 11:26:56

IP:210.66.xxx.xxx 訂閱

在加減項元素個數不大的狀況下, 以下的測試程式碼應該可以
滿足需求, 這包括無解的部分, 因為是直接計算所有可能的組合...

在有解的假設下, 運算所有加減項可能組合的和,
符合條件即返回,

發現加減項數值的取樣空間,與取樣個數直接影響計算數度:
加減項取樣個數較少時, 迴圈相對較小, 0~2^n-1;
加減項取樣數值較小, 則相同和的組合數較多, 相對計算時間較短

測試碼中, 在Button1Click()的測試動作:
A - 由亂數產生加減項數列, SumOf(A) 為其和.
T - 將 A 之加減項, 全部取為正數.
B - 由 A 將加項數列分離
C - 由 A 將減項數列分離
SignBits - 由 FindSignBits(T, SumOf(A), SignBits) 傳回 Boolean值.
P - 由 T 與 SignBits 取得加項數列
N - 由 T 與 SignBits 取得減項數列

當數值取樣空間相對較小時, 有相同和的不同數列機率相對較高

亦即: (不同數列 B, P 有相同的和) && (不同數列 C, N 有相同的和)

測試碼下載:
http://delphi.ktop.com.tw/download.php?download=upload/471c624506c0a_Test018.zip

[code delphi]
unit fMain;

interface
uses
Windows, Forms, StdCtrls, Classes, Controls;

type

TArrayOfInteger = array of Integer;

TForm1 = class(TForm)
Button1: TButton;
ListBox1: TListBox;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
protected
function GetSample(Range, Count: Int64): TArrayOfInteger;
function ABS_ARRAY(A: TArrayOfInteger): TArrayOfInteger;
function SumOf(A: TArrayOfInteger): Integer; overload;
function Show(A: TArrayOfInteger): string;
function Extract(A: TArrayOfInteger; NumType: Integer): TArrayOfInteger;
function Append(A: TArrayOfInteger; V: Integer): TArrayOfInteger;
function NumStr(V: Integer; Signed: Boolean=True): string;
function FindSignBits(T: TArrayOfInteger; Sum: Int64; var SignBits: Int64): Boolean;
function GetPNElements(T: TArrayOfInteger; SignBits: Int64; PN: Integer): TArrayOfInteger;
end;

var
Form1: TForm1;

implementation

uses SysUtils, Math;

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);
begin
Randomize;
end;

function TForm1.NumStr(V: Integer; Signed: Boolean): string;
begin
Result := IntToStr(V);
if Signed and (V >= 0) then
Result := ' ' Result;
end;

function TForm1.GetSample(Range, Count: Int64): TArrayOfInteger;
var
I: Integer;
begin
//亂數產生數列
SetLength(Result, Count);
for I := 0 to Count-1 do
begin
Result[I] := Random(Range);
if Random(1000) mod 2 = 0 then
Result[I] := Result[I] * -1;
end;
end;

function TForm1.SumOf(A: TArrayOfInteger): Integer;
var
I: Integer;
begin
Result := 0;
I := 0;
while I < Length(A) do
begin
Inc(Result, A[I]);
Inc(I);
end;
end;

function TForm1.Show(A: TArrayOfInteger): string;
var
S: string;
I: Integer;
begin
if Length(A) = 0 then Result := '{}'
else begin
S := '{ ';
for I := 0 to Length(A)-1 do
S := S NumStr(A[I]) ', ';
Result := Copy(S, 1, Length(S)-2) ' }';
end;
end;

function TForm1.Append(A: TArrayOfInteger; V: Integer): TArrayOfInteger;
begin
SetLength(Result, Length(A) 1);
Move(Pointer(A)^, Pointer(Result)^, Length(A) * SizeOf(Integer));
Result[Length(Result)-1] := V;
end;

function TForm1.ABS_ARRAY(A: TArrayOfInteger): TArrayOfInteger;
var
I: Integer;
begin
SetLength(Result, Length(A));
I := 0;
while I < Length(A) do
begin
Result[I] := ABS(A[I]);
Inc(I);
end;
end;

function TForm1.Extract(A: TArrayOfInteger; NumType: Integer): TArrayOfInteger;
var
I, J: Integer;
begin
//NumType = 0: 取負數數列, 1: 取正數數列
Result := nil;
if (NumType in [0,1]) and (Length(A)>0) then
begin
J := 0;
SetLength(Result, Length(A));//B:正數集合
try
for I := 0 to Length(A)-1 do
begin
if ((A[I]>=0) and (NumType=1)) or
((A[I]<0) and (NumType=0)) then
begin
Result[J] := A[I];
Inc(J);
end;
end;
finally
SetLength(Result, J);
end;
end;
end;

function TForm1.FindSignBits(T: TArrayOfInteger; Sum: Int64;
var SignBits: Int64): Boolean;
var
I, J, Count: Integer;
K, CheckSum: Int64;
begin
SignBits := 0;//SignBits 亦為計算的次數
Result := False;
T := ABS_ARRAY(T); //取正值數列
Count := Round(Power(2, Length(T))); //可能組合數目
for I := 0 to Count-1 do
begin
K := I;
CheckSum := 0;
for J := 0 to Length(T)-1 do//Iterate All Element
begin
if K and $1 = 0 then CheckSum := CheckSum - ABS(T[J])
else CheckSum := CheckSum ABS(T[J]);
K := K shr 1;
end;
if CheckSum = Sum then
begin
SignBits := I;
Result := True;
Break;
end;

end;
end;

function TForm1.GetPNElements(T: TArrayOfInteger; SignBits: Int64; PN: Integer): TArrayOfInteger;
var
I, J, Sign: Integer;
begin
//PN= 0:正數, 1: 負數
Result := nil;
if (PN in [0,1]) and (Length(T)>0) then
begin
J := 0;
T := ABS_ARRAY(T);
SetLength(Result, Length(T));
try
if PN = 1 then Sign := 1 else Sign := -1;
for I := 0 to Length(T)-1 do
begin
if SignBits and $01 = PN then
begin
Result[J] := T[I] * Sign;
Inc(J);
end;
SignBits := SignBits shr 1;
end;
finally
SetLength(Result, J);
end;
end;
end;
//------------------------------------------------------------------------------
procedure TForm1.Button1Click(Sender: TObject);
var
StartTick: Cardinal;
SignBits: Int64;
A, B, C, T, P, N: TArrayOfInteger;
begin
StartTick := GetTickCount;
B := nil; C := nil;
P := nil; N := nil;
A := GetSample(MaxInt div 8, 10); //(Range, Count)
T := ABS_ARRAY(A); //將數列中的原數, 全部取其正值.
try
ListBox1.Items.Add('========================================================');
ListBox1.Items.Add('數列取樣 A: ' Show(A) '=' IntToStr(SumOf(A)));
ListBox1.Items.Add('取數列正值T: ' Show(T) '=' IntToStr(SumOf(T)));
ListBox1.Items.Add('--------------------------------------------------------');
//由已知和, 與正值數列去計算所有可能數列的和, 傳回其數列元素 SignBits
if FindSignBits(T, SumOf(A), SignBits) then
begin
B := Extract(A, 1);//B:正數集合
C := Extract(A, 0);//C:負數集合
ListBox1.Items.Add('Done!');
ListBox1.Items.Add('加項數列B: ' Show(B) '=' IntToStr(SumOf(B)));
ListBox1.Items.Add('減項數列C: ' Show(C) '=' IntToStr(SumOf(C)));
ListBox1.Items.Add('--------------------------------------------------------');
P := GetPNElements(T, SignBits, 1);
N := GetPNElements(T, SignBits, 0);
ListBox1.Items.Add('取數列正值T: ' Show(T) '=' IntToStr(SumOf(T)));
ListBox1.Items.Add('運算之正負號 : ' Format('%8.8X', [SignBits]));
ListBox1.Items.Add('運算之加項數列P: ' Show(P) '=' IntToStr(SumOf(P)));
ListBox1.Items.Add('運算之減項數列N: ' Show(N) '=' IntToStr(SumOf(N)));
ListBox1.Items.Add('運算時間Tick(ms):' IntToStr(GetTickCount-StartTick));
ListBox1.Items.Add('========================================================');
end;
finally
A := nil; T := nil;
B := nil; C := nil;
P := nil; N := nil;
end;
end;

end.
[/code]

編輯記錄

jow 重新編輯於 2007-10-22 11:53:09，註解無‧
jow 重新編輯於 2007-10-22 16:17:21，註解無‧
jow 重新編輯於 2007-10-22 16:42:43，註解無‧
jow 重新編輯於 2007-10-22 17:57:40，註解無‧