關於變數加減的問題(邏輯) |
答題得分者是:jow
|
UB
一般會員 發表:18 回覆:19 積分:7 註冊:2007-02-19 發送簡訊給我 |
各位大大,我想問一個邏輯問題!!
假設說我有 A,B,C,D 四個數字,我現在不曉得哪幾個是加的哪幾個是減的,而他們的總和則為第五個數字 ! 可否給我個方向,該從何處下手 例如說: A = 33 B = 54 C = 29 D = 18 E = 134 以這個例子來說 A B C D = E 電腦必須算出,A,B,C,D 都是正數 另一個例子: A = 34 B = 21 C = 77 D = 9 E = 81 這個例子來說 A-B C-D = E 電腦必須算出 A,C 是正數, B,D 是負數. 因為我的變數並不是一定四個,大部分是30個以上,而且一次要盤算約2500組以上,所以速度也要納入考量,再來就是,答案也有可能是無解,也就是說 A,B,C,D 不管如和加加減減有可能都不等於E,值得高興的是... 幸好沒有乘和除..... |
jow
尊榮會員 發表:66 回覆:751 積分:1253 註冊:2002-03-13 發送簡訊給我 |
在加減項元素個數不大的狀況下, 以下的測試程式碼應該可以
滿足需求, 這包括無解的部分, 因為是直接計算所有可能的組合... 在有解的假設下, 運算所有加減項可能組合的和, 符合條件即返回, 發現加減項數值的取樣空間,與取樣個數直接影響計算數度: 加減項取樣個數較少時, 迴圈相對較小, 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] |
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |