CAU TRUC DU LIEU VA GIAI THUAT, TU THUAT TOAN DEN CT...

VAO DAY DE TRAO DOI THUAT TOAN CAC BAN

GIAI QUYET BAI TOAN QUY HOAT DONG
Cho một ma trận nguyên A cấp NxM. Tìm số lượng các ma trận con cấp KxL mà tổng các phần tử của nó là S.

Gọi G(x1,y1,x2,y2): tổng các phần tử của ma trận (x1,y1,x2,y2)
Khi đó nói chung: G(x1,y1,x2,y2) = A[x1,y1] + G(x1+1,y1,x2,y2) + G(x1,y1+1,x2,y2) - G(x1+1,y1+1,x2,y2)

Gọi F(x1,y1,x2,y2): số lượng các ma trận con của ma trận (x1,y1,x2,y2) có tổng các phần tử là S
Khi đó nói chung:
F(x1,y1,x2,y2) = F(x1+1,y1,x2,y2) + F(x1,y1,x2-1,y2) - F(x1+1,y1,x2-1,y2) + k
với
k=1 nếu G(x1,y1,x2,y2) bằng S
k=0 nếu G(x1,y1,x2,y2) khác S

Có 2 quan hệ truy hồi trên thì có thể cài đặt qui hoạch động được rồi

(có gì sai sót mong được góp ý, xin cám ơn)

CHUYEN DOI QUA LAI KY PHAP BALAN- CAU TRUC DU LIEU
ví dụ co biểu thức: (a+b)*c*d -e/f
chuyển sang kí pháp Ba Lan: ab+cd**ef/-
Ký pháp nghịch đảo Balan là một cách biểu diễn biểu thức toán học thông thường theo một dạng khác, khá thuận lợi cho việc tính toán một biểu thức trong máy tính

Một biểu thức toán học thông thường có thể được biến đổi thành dãy gồm các toán tử và toán hạng, trong đó một toán tử được dùng để tính toán với 1 hoặc 2 toán hạng đứng trước nó trong dãy đó.

Ví dụ (A+B)*C biến đổi thành AB+C*

A+B*C biến đổi thành ABC*+

Có hai dạng ký pháp nghịch đảo Balan, preffix và suffix. Dạng trên là suffix.

Các bác pro thì biết rồi, phần trên thì chỉ nói qua cho ai chưa biết thôi. Ai chưa biết thì có thể tìm đọc nó ở... đâu đó.

Thuật toán để biến đổi biểu thức toán học thành dạng ký pháp nghịch đảo Balan như sau (tôi sẽ dùng luôn một vài biến được sử dụng trong chươn trình dưới đây trong khi giải thích):

Ta sử dụng hai stack. Một dùng để lưu dạng Balan (nói tắt tho gọn), gọi là BalanExpr, một dùng để lưu các toán tử dùng trong quá trình chuyển biểu thức thành dạng Balan, gọi là opr. Kết quả được đưa vào BalanExpr. Chỉ việc đọc lần lượt từ đầu đến cuối của BalanExpr thì sẽ được dạng ký pháp nghịch đảo Balan của biểu thức đã cho.

Ta sẽ đọc lần lượt từ đầu đến cuối biểu thức đã cho để xử lý:

- Nếu gặp dấu mở ngoặc thì Push nó vào stack opr.

- Nếu gặp một toán hạng thì Push nó vào stack BalanExpr.

- Nếu gặp một toán tử thì:

+ Nếu các toán tử được lưu cuối cùng trong opr có mức ưu tiên cao hơn thì lần lượt Pop các toán tử đó ra khỏi opr, Push nó vào BalanExpr. Làm vậy cho đến khi gặp phải toán tử có mức ưu tiên bằng hoặc thấp hơn nó thì dừng.

+ Push toán tử đang xét vào opr.

+ Mức ưu tiên của các toán tử được quy định như sau: + -, sau đó là * /, cao hơn là ^. Dấu mở ngoặc được coi là có mức ưu tiên thấp nhất.

- Nếu gặp dấu đóng ngoặc thì Pop toàn bộ các toán tử được lưu trong opr, Push vào BalanExpr, cho đến khi gặp dấu mở ngoặc (được lưu trong opr). Sau đó Pop luôn dấu mở ngoặc đó ra, vứt đi.


Các bước làm cơ bản chỉ có thế. Bác nào chưa biết thì nên tìm tài liệu đọc, tôi cũng không thể giải thích kỹ được.


File dữ liệu vào quy ước như sau:

- dòng đầu là số tự nhiên N

- N dòng sau, mỗi dòng dùng để khai báo một biến, theo dạng . Các tên biến theo quy tắc đặt tên chuẩn của Pascal.

- Dòng cuối cùng là biểu thức cần tính toán.

CHUYEN DOI QUA LAI KY PHAP BALAN- CAU TRUC DU LIEU TIEP..

Một cách tính giá trị của biểu thức PosFix trong ký pháp Balan :

Sau khi đã chuyển biểu thức InFix (E) ban đầu thành biểu thức PosFix (EP) ta cần phải đi tính giá trị biểu thức EP với các giá trị nhập từ bàn phím.
Sau đây tôi xin nhắc lại giải thuật tính giá trị EP :

+ Duyệt từ đầu xâu EP đến cuối xâu :
- Nếu là toán hạng thì đẩy vào Stack
- Nếu là toán từ ( Giả sử là toán tử x ) thì lấy 2 giá trị trong Stack ra (giả sử là y1 và y2 ) và tính y=y1xy2 sau đó lại đẩy y vào Stack
- Tiếp tục như vậy cho đến hết xâu EP thì ta thu được giá trị của biểu thức chính là y ( phần tử còn lại trong Stack ).

Lý thuyết là như vậy nhưng làm sao để biểu diễn được Cấu trúc dữ liệu, sau đây tôi đưa ra một phương pháp để giải quyết (theo tôi là rất đơn giản) và có thể tính được cho biểu thức có chứa các số thực.

Cách của tôi là dùng một mảng Value['a'..'z'] of Real để nhập giá trị cho các biến trong EP và dùng luôn chỉ số của mảng để biểu diễn các giá trị các phần tử trong Stack.

Sau đây là vd :


Var Value:arrray['a'..'z'] of Real; ch:char; // Nhập giá trị cho các toán hạng trong EP for ch:'a' to 'z' do if Pos(ch,EP)>0 then begin write('Nhap gia tri cho ',ch,'=');readln(value[ch]); end;

// Tính giá trị EP

value['y']:=0; for i:=1 to length(EP) do if not (EP[i] in ['+','-','*','/']) then Push(E[i],S); { Đẩy E[i] vào Stack } if (EP[i] in ['+','-','*','/']) then begin case EP[i] of '+': value['y']:=value[Pop(S)]+value[Pop(S)]; '-': value['y']:=value[Pop(S)]-value[Pop(S)]; '*': value['y']:=value[Pop(S)]*value[Pop(S)]; '/': value['y']:=value[Pop(S)]/value[Pop(S)]; end; Push('y'); end; wirteln('Gia tri cua bieu thuc = ', value['y']); readln;

DAY LA CHUONG TRINH CU THE CUA BAI TOAN KY PHAP BALNĐây là chương trình chuyển từ ký pháp thông thường sang ký pháp Ba lan:

program ConvertInfixToRPN;
const
Opt = ['(', ')', '+', '-', '*', '/'];
var
T, Infix, Stack: String;
p: Integer;

procedure StackInit;
begin
Stack := '';
end;

procedure Push(V: Char);
begin
Stack := Stack + V;
end;

function Pop: Char;
begin
Pop := Stack[Length(Stack)];
Dec(Stack[0]);
end;

function Get: Char;
begin
Get := Stack[Length(Stack)];
end;

procedure Refine(var S: String);
var
i: Integer;
begin
S := S + ' ';
for i := Length(S) - 1 downto 1 do
if (S[i] in Opt) or (S[i + 1] in Opt) then
Insert(' ', S, i + 1);
for i := Length(S) - 1 downto 1 do
if (S[i] = ' ') and (S[i + 1] = ' ') then Delete(S, i + 1, 1);
end;

function Priority(Ch: Char): Integer;
begin
case ch of
'*', '/': Priority := 2;
'+', '-': Priority := 1;
'(': Priority := 0;
end;
end;

procedure Process(T: String);
var
c, x: Char;
begin
c := T[1];
if not (c in Opt) then Write(T, ' ')
else
case c of
'(': Push(c);
')': repeat
x := Pop;
if x <> '(' then Write(x, ' ');
until x = '(';
'+', '-', '*', '/':
begin
while (Stack <> '') and (Priority(c) <= Priority(Get)) do
Write(Pop, ' ');
Push(c);
end;
end;
end;

begin
Write('Infix = '); Readln(Infix);
Refine(Infix);
Writeln('Refined: ', Infix);
Write('RPN : ');
T := '';
for p := 1 to Length(Infix) do
if Infix[p] <> ' ' then T := T + Infix[p]
else
begin
Process(T);
T := '';
end;
while Stack <> '' do Write(Pop, ' ');
Writeln;
end.

Chương trình này được lấy từ cuốn sách về thuật toán của thầy Lê Minh Hoàng. Bạn có thể tham khảo đầy đủ cuốn sách tại đây:
http://www.jaist.ac.jp/~hoangle/ssi/