TỦ SÁch tri thức duy tân nguyễn xuân huy sáng tạo trong thuật toán và LẬp trìNH
tải về 2.51 Mb.
|
2.4 Hàm nhiều biếnMột số hàm có số tham biến không hạn chế,Thí dụ 1: Hàm ucln – tính ước chung lớn nhất của các số nguyên được định nghĩa như sau:ucln( ) = 0, không có tham biến, qui ước = 0ucln(x) = |x|, ucln của số x là giá trị tuyệt đối của chính số đóucln(a,b) = ucln(b,a),ucln(a,0) = a,ucln(a,b) = ucln(a mod b, b)ucln(x1, x2,...,xn) = ucln (ucln(x1, x2,...,xn-1), |xn|), n 2.Thí dụ 2: Hàm sum – tính tổng của các số nguyên:sum( ) = 0,sum(x) = x,sum(x1, x2,...,xn) = sum(sum(x1, x2,...,xn-1), xn), n 2.Ngoài ra còn các hàm lấy min, max của dãy phần tử...Cho một biểu thức được viết đúng cú pháp, chứa các hằng nguyên, các biến a, b,... được gán sẵn các trị a = 0, b = 1,..., các phép toán số học +, –, *, / (chia nguyên), % (chia dư), các cặp ngoặc và các lời gọi hàm nhiều biến @. Hãy tính giá trị của biểu thức nếu @ là hàm ucln.Thí dụ, 16 sẽ là giá trị của biểu thức (10+@(12,30+@(6,8))+17*@( )+2)*@(1,3). Thật vậy, ta có @( ) = 0; @(6,8) = 2; @(12,30+@(6,8)) = @(12,30+2) = @(12,32) = 4; @(1,3) = 1; (10+@(12,30+@(6,8))+17*@( )+2)*@(1,3) = (10+4 + 17*0 +2)*1 = 16*1 = 16.Thuật toán Ta mở rộng thuật toán của bài Val để có thể xử lý thêm các trường hợp sau. Thứ nhất, chương trình phải nhận biết được phép toán đảo dấu. Đây là phép toán 1 ngôi khác với phép trừ là phép toán 2 ngôi. Thí dụ, biểu thức –a + b có phép toán đảo dấu. Phép này cũng khá dễ nhận biết. Nếu gặp dấu – và trong ngọn của ngăn xếp c không chứa phép toán nào thì phép – này sẽ là phép toán đổi dấu. Ta nạp vào ngăn xếp c kí hiệu ! cho phép đổi dấu nhằm phân biệt tường minh với với phép toán trừ. Kỹ thuật này có thể gây nhập nhằng, thí dụ, khi xử lí biểu thức a–b thì dấu – gặp đầu tiên nên trong ngăn xếp c không chứa phép toán nào. Hệ thống sẽ coi là phép toán đổi dấu. Ta khắc phục tình huống này bằng cách sau. Sau khi thực hiện hết các phép toán trong ngăn xếp c, nếu trong ngăn xếp tính toán t còn hơn 1 phần tử thì ta cộng dồn kết quả vào t[1]. Như vậy ta đã giả thiết a – b = a+(–b) trong đó – là phép đổi dấu. Thứ hai, chương trình phải xử li được các tình huống gọi hàm @ với các tham biến khác nhau. Khi gặp kí hiệu @ ta xác định xem giữa cặp ngoặc ( ) có đối tượng nào không. Nếu không có, ta ghi nhận một lời gọi hàm rỗng trong ngăn xếp c. Trong danh sách tham biến của lời gọi hàm có thể chứa dấu phảy dùng để ngăn cách các tham biến. Ta cũng nạp dần các dấu ngăn này vào ngăn xếp c. Thủ tục Cach bỏ qua các dấu cách trong xâu input s, tìm đến kí tự có nghĩa s[v] tiếp theo. Với hai ngăn xếp c dùng để ghi nhận các dấu phép toán và t dùng để chứa các giá trị cần tính toán ta tổ chức đọc duyệt xâu input s và xử lí như sau. 1. Khởi trị các ngăn xếp, 2. Với mỗi kí tự s[v] ta xét 2.1 s[v] = '@': Nạp @ vào c; đọc tiếp s để xác định xem giữa cặp ngoặc ( ) có kí hiệu nào không. Nếu không có: nạp thêm $ vào c để ghi nhận lời gọi hàm rỗng; 2.2 s[v] = '(': Nạp ( vào c; 2.3 s[v] là chữ số '0'..'9': Đọc số này và nạp vào ngăn xếp t; 2.4 s[v] là tên biến (chữ cái 'a'..'z'): Nạp trị của các biến này vào ngăn xếp t. Trị của biến x được tính theo công thức x – 'a'; 2.5 s[v] là dấu phảy: Thực hiện các phép toán (nếu có) trên ngọn ngăn xếp c để tính trị của biểu thức ứng với tham số này. Thí dụ, s = "@(a+1,..." thì ta phải tính trị của a + 1 trước khi gọi hàm; 2.5 s[v] = ')': Ta cần xác định xem dấu ')' đóng một biểu thức con hay đóng danh sách tham biến của một lời gọi hàm. Trước hết ta thực hiện các phép toán (nếu có) trên ngọn ngăn xếp c để tính trị của biểu thức kết thúc bằng dấu ')'. Kế đến ta duyệt ngược ngăn xếp c để xác định vị trí của dấu '('. Sát trước vị trí này có thể có dấu @ hoặc không. Nếu có ta tính hàm. Nếu sát sau '(' là kí hiệu '$' thì ta hiểu là hàm rỗng, ta sinh trị 0 cho ngăn xếp t. 2.6 s[v] là dấu các phép toán +, –, *, /, %: Ta thực hiện các phép toán bậc cao trên ngọn ngăn xếp c rồi nạp phép toán s[v] này vào c. Riêng với phép – ta cần xác định xem có phải là phép đảo dấu hay không. (* Func.pas *) uses crt; const bl = #13#10; nl = #32; mn = 500; var c: array[0..mn] of char; { ngan xep phep toan } ic: integer; { ngon ngan xep c } t: array[0..mn] of integer; { ngan xep tinh toan } it: integer; { ngon ngan xep t } s: string; { input } v: integer; { duyet s } function Ucln(a,b: integer): integer; var r: integer; begin a := abs(a); b := abs(b); while b > 0 do begin r := a mod b; a := b; b := r; end; Ucln := a; end; procedure Cach; begin while s[v] = bl do inc(v) end; function LaBien(c: char): Boolean; begin LaBien := (c in ['a'..'z']); end; function LaChuSo(c: char): Boolean; begin LaChuSo := (c in ['0'..'9']); end; function LaPhepToan(c: char): Boolean; begin LaPhepToan := (c in ['+','-','*','/','%','!']) end; function Val(c: char): integer; begin Val := Ord(c)-ord('a'); end; function Bac(p: char): integer; begin if (p in ['+','-']) then Bac := 1 else if (p in ['*','/', '%']) then Bac := 2 else if (p = '!') then Bac := 3 else Bac := 0; end; function DocSo: integer; var so: integer; begin so := 0; while LaChuSo(s[v]) do begin so := so*10 + Ord(s[v])-ord('0'); inc(v); end; DocSo := so; end; procedure Tinh(p: char); begin case p of '+': begin t[it-1] := t[it-1] + t[it]; dec(it) end; '-': begin t[it-1] := t[it-1] - t[it]; dec(it) end; '*': begin t[it-1] := t[it-1] * t[it]; dec(it) end; '/': begin t[it-1] := t[it-1] div t[it]; dec(it) end; '%': begin t[it-1] := t[it-1] mod t[it]; dec(it) end; '!': begin t[it] := -t[it] end; { phép đảo dấu } end end; procedure Napc(ch: char); begin inc(ic); c[ic] := ch end; procedure NapBien(x: char); begin inc(v); inc(it); t[it] := Val(x); end; procedure NapSo; var so: integer; begin inc(it); t[it] := DocSo; end; procedure NapPhepToan(p: char); begin inc(v); if p = '-' then if Not LaPhepToan(c[ic]) then begin Napc('!'); exit end; while (Bac(c[ic]) >= Bac(p)) do begin Tinh(c[ic]); dec(ic) end; Napc(p); end; procedure NapPhay; begin inc(v); while LaPhepToan(c[ic]) do begin Tinh(c[ic]); dec(ic) end; Napc(','); end; procedure NapNgoac; begin inc(v); Napc('('); end; procedure NapHam; begin inc(v); Napc('@'); Cach; NapNgoac; { bo qua ( } Cach; if s[v] = ')' then { Ham rong } Napc('$'); end; procedure XuLiHam(i: integer); var j,kq: integer; begin if c[i+1] = '$' then begin inc(it); t[it] := 0; ic := i - 2; exit end; kq := 0; for j := it-ic+i to it do kq := Ucln(kq,t[j]); it := it-ic+i; t[it] := kq; ic := i - 2; end; procedure XuLiNgoac; { gap ) } var i: integer; begin inc(v); while LaPhepToan(c[ic]) do begin Tinh(c[ic]); dec(ic) end; i := ic; while (c[i] <> '(') do dec(i); { Tim ngoac ( } if c[i-1] = '@' then XuLiHam(i) else dec(ic); { Bo ( } end; function BieuThuc(var s: string): integer; var i: integer; begin s := s + '#'; ic := 1; c[ic] := '#'; it := 0; v := 1; while (s[v] <> '#') do if LaBien(s[v]) then NapBien(s[v]) else if LaChuSo(s[v]) then NapSo else if LaPhepToan(s[v]) then NapPhepToan(s[v]) else if s[v] = ',' then NapPhay else if s[v] = '(' then NapNgoac else if s[v] = '@' then NapHam else if s[v] = ')' then XuLiNgoac else inc(v); while (LaPhepToan(c[ic])) do begin Tinh(c[ic]); dec(ic) end; for i := 2 to it do t[1] := t[1]+t[i]; BieuThuc := t[1]; end; BEGIN s := '@(-70,12+10-b,@(y+5,10)*c+12)'; writeln(nl,s, ' = ',BieuThuc(s)); { 7 } readln; END. // Dev-C++: Func #include #include #include using namespace std; // D A T A A N D V A R I A B L E const int mn = 500; const char BL = ' ';//32; char c[mn]; // stack lenh int ic; // ngon stack c int t[mn]; // stack tinh toan int it; // ngon stac v int v; // duyet s char s[mn]; // xau input // P R O T O T Y P E S int BieuThuc(char *); int DocSo(); void Cach(); bool LaPhepToan(char); bool LaChuSo(char); bool LaBien(char); int Val(char); int Bac(char); void NapHam(); void NapNgoac(); void NapSo(); void NapPhay(); void XuLiNgoac(); void XuLiHam(int); void Tinh(char); void XuLiToan(char); int Ucln(int , int); // I M P L E M E N T A T I O N int main(){ strcpy(s,"(10+@(12,30+@(6,8))+17*@()+2)*@(1,3)"); cout << endl << "Ket qua: " << BieuThuc(s); // 16 cout << endl; system("PAUSE"); return EXIT_SUCCESS; } int Ucln(int a, int b) { int r; a = abs(a); b = abs(b); while (b) { r = a % b; a = b; b = r; } return a; } int Bac(char p) { if (p == '+' || p == '-') return 1; else if (p == '*' || p == '/' || p == '%') return 2; else if (p == '!') return 3; else return 0; } bool LaChuSo(char c) { return (c >= '0') && (c <= '9'); } bool LaPhepToan(char c) { return (c=='!' || c=='+'||c=='-'||c=='*'||c=='/'||c=='%'); } // ! phep dao dau bool LaBien(char c) { return (c >= 'a') && (c <= 'z'); } int Val(char x) { return int(v-'0'); } void Cach() { while (s[v] == BL) ++v; } int DocSo() { int so = 0; Cach(); if (!LaChuSo(s[v])) return 1; while (LaChuSo(s[v])) { so = so*10 + int(s[v]-'0'); ++v; } return so; } void NapNgoac() { c[++ic] = '('; ++v; } void NapHam() { c[++ic] = '@'; ++v; // bo qua dau @ trong s Cach(); // tim dau ( c[++ic] = s[v]; // Nap ( ++v; // bo qua dau ( tring s Cach(); if (s[v]==')') c[++ic] = '$';// ham rong } void NapSo() { t[++it] = DocSo();} void NapVal(char x) { t[++it] = Val(x); ++v;} void Tinh(char p) { switch(p) { case '+': t[it-1] += t[it]; --it; break; case '-': t[it-1] -= t[it]; --it; break; case '*': t[it-1] *= t[it]; --it; break; case '/': t[it-1] /= t[it]; --it; break; case '%': t[it-1] %= t[it]; --it; break; case '!': t[it] = -t[it]; break; } } void XuLiHam(int i) { // c[i-1..i] = @( int kq = 0 ; // ket qua if (c[i+1]=='$') { // ham rong ic = i-2; t[++it] = 0; return; } int k = ic - i + 1; // so tham bien int jj = it; it = it - k + 1; for(int j = it; j <= jj; ++j) kq = Ucln(kq, t[j]); t[it] = kq; ic = i-2; } void XuLiNgoac() { // Gap dau ): s[v] = ')' int i; ++v; // bo qua ) trong s while (LaPhepToan(c[ic])) { // Thuc hien cac phep toan tren ngon Tinh(c[ic]); --ic; } i = ic; while (c[i] != '(') --i;// tim dau ( trong c // c[i] = '(' if (c[i-1] == '@') XuLiHam(i); // gap ham @ else --ic; // ko gap ham } void NapPhay() { ++v; // bo qua dau , trong s while (LaPhepToan(c[ic])) { Tinh(c[ic]); --ic; } c[++ic] = ','; } void XuLiToan(char p) { ++v; // bo qua ki tu trong s if (p=='-') if (!LaPhepToan(c[ic])) { c[++ic] = '!'; return; } while (Bac(c[ic]) >= Bac(p)) { Tinh(c[ic]); --ic; } c[++ic] = p; } int BieuThuc(char *s ) { cout << endl << "input: " << s << endl; // init ic = it = 0; c[++ic] = '#'; for (v = 0; s[v];) { if (s[v] == '@') NapHam(); else if (s[v] == '(') NapNgoac(); else if (LaChuSo(s[v])) NapSo(); else if (LaBien(s[v])) NapVal(s[v]); else if (s[v] == ',') NapPhay(); else if (s[v] == ')') XuLiNgoac(); else if (LaPhepToan(s[v])) XuLiToan(s[v]); else ++v; } while (LaPhepToan(c[ic])) { Tinh(c[ic]); --ic; } for (;it > 1; --it) t[1] += t[it]; return t[1]; } 2.5 Files
Trước hết ta xét một thí dụ minh họa. Giả sử lúc đầu mỗi file có chỉ số i chứa một số nguyên dương i+10, i = 1, 2, ..., 48. Thao tác MODI lật các chữ số trong RAM, tức là viết dãy số theo thứ tự ngược lại. Thao tác INS i đọc số trong file i rồi xen vào sau chữ số đầu tiên của file hiện lưu trên RAM.
Khí đó trình tự thực hiện hai chương trình ghi trong input file FILES.INP và output file FILES.OUT được giải trình chi tiết trong bảng. Nội dung ghi trong 4 file mang mã số 1, 2, 3 và 4 đầu tiên lần lượt là 11, 12, 13 và 14. Kết quả cuối cùng của cả hai chương trình đều giống nhau và bằng 11143211. Chương trình ghi trên file inp chứa 4 lệnh SAVE trong khi chương trình ghi trên file out chứa 3 lệnh SAVE. Bạn cũng cần lưu ý rằng phép xen file INS nói chung không thỏa tính giao hoán và kết hợp. Để minh họa ta tạm qui ước nội dung ghi trong file được đặt giữa cặp ngoặc []. Khi đó, [12] INS [13] = [1132], trong khi [13] INS [12] = [1123], ngoài ra ([12] INS [13]) INS [14] = [1132] INS [14] = [114132], trong khi [12] INS ([13] INS [14]) = [12] INS [1143] = [111432]. Thuật toán 
Thuật toán được triển khai theo 2 pha: Pha Đọc và Pha Ghi. Pha thứ nhất, Pha Đọc sẽ đọc từng dòng lệnh của chương trình nguồn P từ input file và tạo thành một cây t. Pha thứ hai, Pha Ghi chỉ đơn thuần ghi lại cây t vào output file theo nguyên tắc ưu tiên lệnh SAVE cho cây con phải. Ta trình bày chi tiết các kỹ thuật tại hai pha. Mỗi nút của cây t có 4 thành phần (C, f , L, R) trong đó C là chữ cái đầu của lệnh LOAD, SAVE, MODI, END, f là số hiệu file (tên) trong dòng lệnh, L và R lần lượt là con trỏ trái và phải tới nút tiếp theo trên cây. Ta tạm kí hiệu 0 là con trỏ NULL trong C++ và NIL trong Pascal.
LOAD f : Nếu file f chưa xuất hiện thì tạo một nút mới v = (C, f, 0, 0) và đánh dấu f là file đã xuất hiện. Việc đánh dấu được thực hiện thông qua phép gán p[f] = v trong đó p là mảng các con trỏ tới các nút, f là số hiệu (tên) file, v là giá trị của con trỏ được cấp phát cho nút được khởi tạo cho file f, p[f] = 0 (NULL/nil) cho biết file f chưa xuất hiện trong chương trình P. Nếu f đã xuất hiện thì ta gán v là con trỏ tới nút đã khởi tạo cho file f, v = p[f]; SAVE f: Không tạo nút mới, chỉ ghi nhận f vào biến lastsave để biết phép SAVE cuối cùng của chương trình P sẽ ghi kết quả vào file nào. Đồng thời ta cũng cần đánh dấu p[f] = v để biết rằng file hiện có trên RAM là v đã được ghi vào file f; MODI: Tạo nút mới v = NewElem('M',–1,v,0) đặt trên nút v hiện hành. Giá trị của trường fnum được đặt là –1 cho biết lệnh này không quan tâm đến tên file vì nó chỉ MODIFY nội dung của file hiện có trên RAM; INS f: Nếu file f chưa xuất hiện thì tạo nút mới v = NewElem('I',f,v,0), ngược lại, nếu file f đã xuất hiện thì tạo nút mới v = NewElem('I',-1,v,p[f]).
2.1 Cây t chỉ có cây con trái L, t = (L,0): Ta chỉ việc gọi thủ tục ToFile(L). 2.2 Cây t có cả hai cây con trái L và phải R, t = (L,R) và hai cây con này được gắn với nhau bằng lệnh INS: Trước hết phải gọi thủ tục ToFile(R) và ghi kết quả trung gian vào một file tạm m, sau đó gọi thủ tục ToFile(L) rồi thêm vào cuối dòng lệnh INS m. Độ phức tạp Cỡ n – số dòng lệnh trong input file. Bình luận Thuật toán trên cũng bỏ qua trường hợp dãy lệnh SAVE f giống nhau liên tiếp cũng như trường hợp hai lệnh liên tiếp là LOAD f và SAVE f với cùng một tên file. Bạn có thể cải tiến thêm bằng cách đọc input file một lần vào miền nhớ và loại bỏ các lệnh này trước khi tổ chức cây t. (* Files.pas *) uses crt; const fn = 'files.inp'; gn = 'files.out'; mn = 400; nl = #13#10; bl = #32; chuso = ['0'..'9']; type pelem = ^elem; elem = record com: char; { lenh } fnum: integer; { so hieu file } L,R: pelem; { tro trai, phai } end; var f,g: text; { f: input file; g: output file } p: array[1..mn] of pelem; { danh dau cac file } s: string; { dong lenh } t: pelem; { cay nhi phan chuong trinh } lastSave: integer; tmp: integer; { file trung gian } function DocSo: integer; { doc so tu dong lenh s } var i, so: integer; begin so := 0; i := 1; while not (s[i] in chuso) do inc(i); while (s[i] in chuso) do begin so := so*10 + ord(s[i]) - ord('0'); inc(i); end; DocSo := so; end; function NewElem(c: char; fno: integer; Lp,Rp: pelem): pelem; var e: pelem; begin new(e); e^.com := c; e^.fnum := fno; e^.L := Lp; e^.R := Rp; NewElem := e; end; function Load(fno: integer): pelem; begin if p[fno] = nil then p[fno] := NewElem('L',fno,nil,nil); Load := p[fno]; end; procedure Save(v: pelem; fno: integer); begin lastSave := fno; p[fno] := v; end; function Ins(v: pelem; fno: integer): pelem; begin if p[fno] = nil then Ins := NewElem('I',fno,v,nil) else Ins := NewElem('I',-1,v,p[fno]); end; function Doc: pelem; var i: integer; v: pelem; { RAM } begin for i := 1 to mn do p[i] := nil; assign(f,fn); reset(f); while not seekeof(f) do begin readln(f,s); s := s + '#'; case s[1] of 'L': v := Load(DocSo); 'S': Save(v,DocSo); 'M': v := NewElem('M',-1,v,nil); 'I': v := Ins(v,DocSo); 'E': begin close(f); Doc := v; exit end; end; end; end; procedure ToFile(t: pelem); var sav: integer; begin sav := 0; if (t = nil) then exit; if (t^.R <> nil) then begin inc(tmp); sav := tmp; ToFile(t^.R); writeln(g,'SAVE',bl,sav); end; ToFile(t^.L); case(t^.com) of 'I': if (t^.R = nil) then writeln(g,'INS',bl,t^.fnum) else if (sav > 0) then writeln(g,'INS',bl,sav); 'L': writeln(g,'LOAD',bl,t^.fnum); 'M': writeln(g,'MODI'); end; end; procedure Ghi(t: pelem); begin assign(g,gn); rewrite(g); tmp := 49; ToFile(t); writeln(g,'SAVE',bl,lastsave,nl,'END'); close(g); end; BEGIN t := Doc; Ghi(t); writeln(nl,' Fini');readln; END. // Dev-C++: Files #include #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = "files.inp"; const char * gn = "files.out"; const char * LOAD = "LOAD"; const char * MODI = "MODI"; const char * INS = "INS"; const char * SAVE = "SAVE"; const char * END = "END"; const char star = '*'; // Node const int mn = 400; struct elem { char com; int fnum; // com: lenh, fnum: file number elem * L; elem * R; // tro trai, tro phai }; elem* p[mn]; int tmp; int lastsave; // P R O T O T Y P E S elem * Doc(); elem * Load(int); elem *NewNode(char, int, elem*, elem*); elem * Ins(elem *, int); void Ghi(elem *t); void ToFile(elem*); ofstream g(gn); // I M P L E M E N T A T I O N int main() { elem * t = Doc(); Ghi(t); cout << endl; system("PAUSE"); return EXIT_SUCCESS; } void Ghi(elem *t) { tmp = 49; ToFile(t); g << "SAVE " << lastsave << endl; g << "END" << endl; g.close(); } void ToFile(elem *t) { int sav = 0; if (t == NULL) return; if (t->R != NULL) { ++tmp; sav = tmp; ToFile(t->R); g << "SAVE " << sav << endl; } ToFile(t->L); switch(t->com) { case 'I': if (t->R == NULL) g << "INS " << t->fnum << endl; else if (sav > 0) g << "INS " << sav << endl; break; case 'L': g << "LOAD " << t->fnum << endl; break; case 'M': g << "MODI" << endl; break; } } elem * Ins(elem *v, int fno) { // Tao node INS elem * e = NewNode('I', -1, v, NULL); if (p[fno] != NULL) e->R = p[fno]; else e->fnum = fno; return e; } elem * Load(int fno) { // Tao node LOAD if (p[fno] == NULL) p[fno] = NewNode('L', fno, NULL, NULL); return p[fno]; } elem * NewNode(char cm, int i, elem * lp, elem * rp) { elem * pt = new elem; // Tao node moi pt->com = cm; pt->fnum = i; pt->L = lp; pt->R = rp; return pt; } elem * Doc() {// Doc vhuong trinh, tao cay char s[10]; ifstream f(fn); elem * v = NULL; // RAM int i, fno; for (i = 0; i < mn; ++i) p[i] = NULL; while (1) { f >> s; fno = 0; switch(s[0]) { case 'E': f.close(); return v; // END case 'L': f >> fno; v = Load(fno); break; // LOAD case 'S': f >> fno; lastsave = fno; p[fno]= v; break; // SAVE case 'I': f >> fno; v = Ins(v,fno); break; // INS case 'M': v = NewNode('M',-1,v,NULL); break; // MODIFY } } } 2.6 Gen(Bài tương tự) Trong phòng thí nghiệm sinh học phân tử người ta bảo quản các đoạn mã di truyền, tạm gọi là các đoạn gen trong các tủ chứa đặc biệt được mã số 1, 2,...,98. Các gen được chỉnh sửa và cấy ghép với nhau trên bàn thí nghiệm T để tạo ra một gen cuối cùng đặt trong tủ chứa số 99 theo một chương trình máy tính tự động bao gồm các thao tác sau: TAKE i : lấy một gen từ tủ chứa i đặt lên bàn thí nghiệm T, MODI: làm sạch, sửa chữa các thông tin di truyền trong gen hiện có trên bàn thí nghiệm T, INS j: cấy ghép gen hiện có trên T với gen trong tủ chứa j, kết quả thu đượ một gen trên T, STORE k: cất gen trên T vào tủ chứa k, END : kết thúc chương trình. Việc lấy và cất giữ gen đòi hỏi các thủ tục rất phức tạp nên người ta cần hạn chế đến mức tối đa các thao tác này. Ngoài ra, lưu ý rằng việc cấy ghép gen i vào gen j cho kết quả khác với việc cấy ghép gen j vào gen i. Hãy thay chương trình cho trước bằng một chương trình tương đương với ít lệnh STORE nhất theo nghĩa cho cùng kết quả thu được trong tủ chứa 99 như chương trình ban đầu. Trong quá trình thao tác được phép sử dụng các tủ chứa tạm từ 100 trở đi . 2.7 Tối ưu hóa chương trình(Bài tương tự)
Thí dụ, file prog.inp là chương trình tính z := (x+y)*(x-y) với 3 lệnh SAVE, file prog.out là chương trình tương đương với 2 lệnh SAVE. 2.8 Mức của biểu thứcTrong các biểu thức tính toán người ta thường dùng các cặp ngoặc (...) để nhóm thành các biểu thức con. Mức của biểu thức được hiểu là số lượng tối đa các cặp ngoặc lồng nhau trong biểu thức, thí dụ biểu thức (a+(b–c)*d)–(a–b) có mức 2. Cho trước k cặp ngoặc và mức h. Hãy cho biết có thể xây dựng được bao nhiêu biểu thức mức h và sử dụng đúng k cặp ngoặc. Thí dụ, ta có 3 biểu thức mức h = 2 sử dụng đúng k = 3 cặp ngoặc như sau:(()()) (())() ()(()) Dạng hàm: Level(k,h)Test 1. Level(3,2) = 3;Test 2. Level(19,18) = 35.Thuật toán Gọi s(k,h) là hàm 2 biến cho ra số lượng các biểu thức khác nhau có mức h và chứa đúng k cặp ngoặc. Xét cặp ngoặc thứ k. Ta thấy, - Nếu gọi A là biểu thức mức h–1 chứa đúng k–1 cặp ngoặc thì (A) sẽ là biểu thức độ sâu h và chứa đúng k cặp ngoặc. - Nếu gọi B là biểu thức mức h chứa đúng k–1 cặp ngoặc thì ( ) B và B ( ) sẽ là hai biểu thức mức h và chứa đúng k cặp ngoặc. Tuy nhiên trong trường hợp này ta phải loại đi tình huống ( ) B = B ( ). Tình huống này chỉ xảy ra duy nhất khi B có dạng dãy các cặp ngoặc mức 1: B = ( )…( ). Khi đó ( ) B = ( ) ( ) … ( ) = B ( ). Tóm lại, ta có s(k,h) = s(k–1,h–1) + 2s(k–1,h) với h > 1, và s(k,1) = 1, k = 1, 2, …, với k 1cặp ngoặc chỉ có thể viết được 1 biểu thức mức 1 gồm dãy liên tiếp k cặp ngoặc ()()...(). Ngoài ra ta có s(0,h) = 0, h > 0, với 0 cặp ngoặc không thể xây dựng được biểu thức mức h > 0; s(0,0) = 1, với 0 cặp ngoặc có duy nhất 1 biểu thức mức 0 (qui ước). Cài đặt: Ta có thể cài đặt hàm s(k,h) với k lần lặp và 2 mảng 1 chiều a và b, trong đó a[j] là giá trị của hàm s(k1,j), b[j] là giá trị của hàm s(k,j), j = 1..h. Trước hết ta khởi trị ứng với k = 1: a[1] = b[1] = 1; a[i] = 0, i = 2..h với ý nghĩa sau: có 1 cặp ngoặc thì viết được 1 biểu thức mức 1, không có các biểu thức mức trên 1. Giả sử tại bước lặp thứ k1 ta đã tính được các giá trị của hàm s(k1,j) và lưu trong mảng a như sau: a[j] = s(k1,j), j = 1..h. Khi đó các giá trị của hàm s(k,j) sẽ được tính và lưu trong mảng b như sau: b[1] = s(k,1) = 1 b[j] = s(k,j) = s(k–1,j–1) + 2s(k–1,j) = a[j1] + 2a[j], j = 2..h Độ phức tạp: k.h. (* Level.pas *) uses crt; const bl = #32; nl = #13#10; mn = 1000; function Level(k,h: integer): longint; var a,b: array[0..mn] of longint; i,j: integer; begin fillchar(a, sizeof(a),0); a[1] := 1; b[1] := 1; for i := 2 to k do { i cap ngoac } begin for j := 2 to h do { i cap ngoac, muc j } b[j] := a[j-1] + 2*a[j]; a := b; end; Level := a[h]; end; BEGIN writeln(nl, level(3,2), nl, level(19,18)); readln; END. // Dev-C++: Level #include #include #include using namespace std; // P R O T O T Y P E S int Level(int, int); // I M P L E M E N T A T I O N int main() { cout << endl << endl << Level(19,18); // 35 cout << endl << endl << Level(3,2); // 3 cout << endl << endl << " Fini" << endl; cin.get(); return 0; } int Level(int k, int h){ int h1 = h+1; int *a = new int[h1]; int *b = new int[h1]; memset(a,0,d1*sizeof(int)); a[1] = b[1] = 1; for (int i = 2; i <= k; ++i) { a[1] = 1; for (int j = 2; j <= h; ++j) b[j] = a[j-1] + 2*a[j]; memmove(a,b,h1*sizeof(int)); } delete a; delete b; return a[h]; } 2.9 Tháp(Bài tương tự)Các em nhỏ dùng các khối gỗ hình chữ nhật to nhỏ khác nhau và có bề dày 1 đơn vị đặt chồng lên nhau để tạo thành một công trình kiến trúc gồm nhiều tòa tháp. Khối đặt trên phải nhỏ hơn khối dưới, số lượng khối các loại là không hạn chế. Độ cao của công trình được tính theo chiều cao của tháp cao nhất trong công trình. Với k khối gỗ có thể xây được bao nhiêu kiểu công trình độ cao h.
2.10 Mi trangTrong một file văn bản có n từ. Với mỗi từ thứ i ta biết chiều dài vi tính bằng số kí tự có trong từ đó. Người ta cần căn lề trái cho file với độ rộng m kí tự trên mỗi dòng. Mỗi từ cần được xếp trọn trên một dòng, mỗi dòng có thể chứa nhiều từ và trật tự các từ cần được tôn trọng. Hãy tìm một phương án căn lề sao cho phần hụt lớn nhất ở bên phải các dòng là nhỏ nhất. Giả thiết rằng mỗi từ đều có 1 dấu cách ở cuối, dĩ nhiên dấu cách này được tính vào chiều dài từ.Dữ liệu vào: file văn bản PAGES.INP. Dòng đầu tiên chứa hai số n và m.Tiếp đến là n chiều dài từ với các giá trị nằm trong khoảng từ 2 đến m.Dữ liệu ra: file văn bản PAGES.OUT. Dòng đầu tiên chứa hai số h và k, trong đó h là phần thừa lớn nhất (tính theo số kí tự) của phương án tìm được, k là số dòng của văn bản đã được căn lề. Tiếp đến là k số cho biết trên dòng đó phải xếp bao nhiêu từ.Các số trên cùng dòng cách nhau qua dấu cách.
Thuật toán Gọi d(i) là đáp số của bài toán với i từ đầu tiên. Ta xét cách xếp từ w[i]. Đầu tiên ta xếp w[i] riêng 1 dòng, độ hụt khi đó sẽ là h = mv[i]. Nếu chỗ hụt còn đủ ta lại kéo từ i1 từ dòng trên xuống, độ hụt khi đó sẽ là h = hv[i1],... Tiếp tục làm như vậy đến khi độ hụt h không đủ chứa thêm từ kéo từ dòng trên xuống. Mỗi lần kéo thêm một từ j từ dòng trên vào dòng mới này ta có một phương án. Độ hụt của phương án này sẽ là max (hv[j],d(j1)). Ta sẽ chọn phương án nào đạt trị min trong số đó.Để cài đặt ta sử dụng mảng một chiều d chứa các giá trị của hàm d(i). Ta khởi trị cho v[0] = m+1 làm lính canh, d[1] = mv[1], vì khi chỉ có 1 từ thì ta xếp trên 1 dòng duy nhất và độ hụt là m v[1].Để xác định sự phân bố số lượng từ trên mỗi dòng ta dùng mảng trỏ ngược t[1..n] trong đó t[i] = j cho ta biết các từ j, j+1,...,i cùng nằm trên một dòng theo phương án tối ưu. Sau đó ta gọi đệ qui muộn mảng t để tính ra số lượng các từ trên mỗi dòng, ghi vào mảng sl theo trật tự ngược.Độ phức tạp: Cỡ n2 vì với mỗi từ i ta phải duyệt ngược i lần. Tổng cộng có n từ nên số lần duyệt sẽ là n.n.(* Pages.pas *) uses crt; const mn = 200; bl = #32; nl = #13#10; fn = 'pages.inp'; gn = 'pages.out'; type mi1 = array[0..mn] of integer; var n,m,k,h: integer; f,g: text; v, d, t, sl: mi1; (* -------------------------------------- n - number of words; m - width of page; k - number of lines; h - maximum of white character of all lines; v[i] - length of i-th word; d[i] - solution result of input data v[1..i]; t[i] = j: all words j, j+1,...,i are in one line; sl[i] - number of words in i-th line ------------------------------------------*) procedure PP(var x: mi1; d,c: integer); var i: integer; begin for i := d to c do write(bl,x[i]); end; function Min(a,b: integer): integer; begin if a < b then Min := a else Min := b end; function Max(a,b: integer): integer; begin if a > b then Max := a else Max := b end; procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n,m); writeln(n,bl,m); for i := 1 to n do read(f,v[i]); close(f); end; procedure Tinhd(i: integer); var j,h, hmax: integer; begin h := m; j := i; d[i] := m+1; while h >= v[j] do begin h := h - v[j]; hmax := Max(d[j-1],h); if d[i] > hmax then begin d[i] := hmax; t[i] := j; end; dec(j); end; end; function XuLi: integer; var i: integer; begin t[0] := 0; v[0] := m+1; d[0] := 0; for i := 1 to n do Tinhd(i); XuLi := d[n]; end; procedure Xep(i: integer); begin if (i = 0) then exit; inc(k); sl[k] := i-t[i]+1; Xep(t[i]-1); end; procedure Ghi; var i: integer; begin assign(g,gn); rewrite(g); writeln(g,h,bl,k); for i := k downto 1 do write(g,sl[i],bl); close(g); end; procedure Run; var i: integer; begin Doc; PP(v,1,n); h := XuLi; k := 0; Xep(n); writeln(nl, h, bl, k, nl); for i := k downto 1 do write(bl, sl[i]); Ghi; end; BEGIN Run; write(nl, ' Fini ');readln; END. // DevC++: Pages.cpp #include #include #include using namespace std; // Data and variables const char * fn = "pages.inp"; const char * gn = "pages.out"; const int mn = 200; int n; // so luong tu int m; // len dong int k; // so dong can viet int h; // do hut toi uu int v[mn]; // len cac tu int d[mn]; // int t[mn]; // con tro nguoc int sl[mn]; // Interface void Doc(); void PP(int [], int , int); int XuLi(); void Tinhd(int); void Xep(int); void Ghi(); // Implementation main () { Doc(); h = XuLi(); k = 0; Xep(n); Ghi(); cout << endl << h << " " << k << endl; for (int i = k; i > 0; --i) cout << " " << sl[i]; cout << endl << " Fini"; cin.get(); return 0; } void Ghi() { ofstream g(gn); g << h << " " << k << endl; for (int i = k; i > 0; --i) g << sl[i] << " "; g.close(); } void Tinhd(int i) { int h = m-v[i]; // cho hut d[i] = max(h,d[i-1]); t[i] = i; int hmax; for (int j = i-1; h >= v[j]; --j) { h = h - v[j]; hmax = max(h,d[j-1]); if (d[i] > hmax) { d[i] = hmax; t[i] = j; } } } void Xep(int i) { // xep cac tu tren moi dong if (t[i] == 0) return; sl[++k] = i-t[i]+1; Xep(t[i]-1); } int XuLi() { v[0] = m+1; d[0] = 0; d[1] = m-v[1]; t[1] = 1; for (int i = 2; i <= n; ++i) Tinhd(i); return d[n]; } void Doc() { ifstream f(fn); f >> n >> m; cout << n << " " << m; for (int i = 1; i <= n; ++i) f >> v[i]; f.close(); PP(v,1,n); } void PP(int a[], int d, int c) { cout << endl; for (int i = d; i <= c; ++i) cout << a[i] << " "; } 2.11 Xếp thẻ(Bài tương tự)
2.12 Xếp xe(Bài tương tự)Tại Hội thi Tin học trẻ có n đoàn học sinh đã xếp hàng đầy đủ tại địa điểm tập trung để chờ Ban tổ chức đưa xe ô tô đến chở các em đi tham quan thủ đô. Mỗi xe có m ghế dành cho mỗi em một ghế. Các đoàn được bố trí lên xe theo đúng trật tự từ đoàn số 1 đến đoàn số n. Mỗi xe có thể xếp vài đoàn liên tiếp nhau nhưng mỗi đoàn cần được xếp gọn trên 1 xe. Sau khi xếp đầy đủ các đoàn, người ta đếm số ghế trống trên mỗi xe và công bố số ghế trống lớn nhất h đã đếm được. Biết số học sinh trong mỗi đoàn, hãy tim một cách xếp xe để giá trị h là nhỏ nhất.Каталог: tailieu tailieu -> MỘt số thủ thuật khi sử DỤng phần mềm adobe presenter tạo bài giảng e-learning tailieu -> Trung tâM ĐÀo tạo mạng máy tính nhất nghệ 105 Bà Huyện Thanh Quan – 205 Võ Thị Sáu, Q3, tp. Hcm tailieu -> Céng hßa x· héi chñ nghÜa viÖt nam Độc lập tự do hạnh phúc tailieu -> Lê Xuân Biểu giao thông vận tảI ĐẮk lắK 110 NĂm xây dựng và phát triểN (1904 2014) nhà xuất bảN giao thông vận tảI tailieu -> ĐỀ thi học sinh giỏi tỉnh hải dưƠng môn Toán lớp 9 (2003 2004) (Thời gian : 150 phút) Bài 1 tailieu -> A. ĐẠi số TỔ HỢp I. Kiến thức cơ bản quy tắc cộng tailieu -> Wikipedia luôn có mặt mỗi khi bạn cần giờ đây Wikipedia cần bạn giúp tailieu -> CHÍnh phủ CỘng hòa xã HỘi chủ nghĩa việt nam độc lập Tự do Hạnh phúc tailieu -> VĂn phòng cộng hoà XÃ HỘi chủ nghĩa việt nam tải về 2.51 Mb. Chia sẻ với bạn bè của bạn:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||