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.
|
5.5 Lò còViệt Nam, 2008 Cho n vòng tròn, mỗi vòng tròn chứa một giá trị nguyên dương có thể trùng nhau. Gọi ai là giá trị chứa trong vòng tròn i. Nếu ba vòng tròn i. j, k khác nhau và thỏa đẳng thức ai+aj = ak thì ta vẽ 2 cung (có hướng) ik và jk. Cho biết đường đi dài nhất có thể qua bao nhiêu đỉnh.
Thuật toán Sau khi đọc dữ liệu vào mảng a và sắp tăng mảng a ta thấy rằng mỗi cung ik trong đồ thị có hướng G xây dựng theo yêu cầu của đầu bài luôn luôn kèm với một cung jk khi và chỉ khi a[i]+a[j] = a[k]; i ≠ j; i,j < k. G chính là đồ thị một chiều (có cung hướng từ đỉnh số hiệu nhỏ tới đỉnh số hiệu lớn), không chu trình. Ngoài ra, do dãy a chỉ gồm các giá trị nguyên dương và được sắp tăng nên với i, j cho trước thì đẳng thức a[i] + a[j] = a[k] chỉ có hy vọng đạt được với những k > max(i,j). Ta sử dụng một mảng d với các phần tử d[k] ghi nhận số đỉnh nằm trên đường dài nhất đi đến đỉnh k. Ta có d[k] = Max { Max(d[i]+1, d[j]+1) | 1 i < j < k, a[i] + a[j] = a[k] } Ta khởi trị cho d[k] = 1 với mọi k = 1..n với ý nghĩa là khi chỉ có 1 đỉnh độc lập thì đường dài nhất chỉ chứa 1 đỉnh đó. Mỗi khi đạt hệ thức a[i]+a[j] = a[k] ta chỉnh lại d[k] là giá trị max của 3 giá trị: d[k], d[i]+1 và d[j]+1, đồng thời ta cũng xác định giá trị dmax cho toàn bài. Do a là dãy sắp tăng nên với mỗi k ta chỉ duyệt các cặp đỉnh i, j thỏa 1 i < j < k. Ngoài ra, để tính d[k], với mỗi i đã chọn, tức là khi đã biết k và i, nếu tồn tại j để a[i] + a[j] = a[k] thì ta không cần xét tiếp các giá trị a[j] khác. Hàm chính của chương trình MaxPath hoạt động như sau: Với mỗi k = 2..n hàm tính giá trị d[k] là số đỉnh nhiều nhất trong số các đường đi kết thúc tại đỉnh k. Đồng thời hàm ghi nhận giá trị max của các d[k]. Hàm Tinhd(k) thực hiện chức năng tính giá trị d[k]. Hàm này hoạt động như sau:
Độ phức tạp Ta có 3 vòng lặp: theo k trong hàm MaxPath và 2 vòng lặp theo i và j trong hàm Tind(k) nên độ phức tạp cỡ n3. Chương trình (* Loco.cpp *) uses crt; const fn = 'loco.inp'; gn = 'loco.out'; mn = 10001; bl = #32; nl = #13#10; type mi1 = array[0..mn] of integer; var f,g: text; a,d: mi1; n: integer; procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n); for i := 1 to n do read(f,a[i]); close(f); end; procedure Sort(d,c: integer); var i, j, t, m: integer; begin i := d; j := c; m := a[(d+c) div 2]; while (i <= j) do begin while (a[i] < m) do inc(i); while (a[j] > m) do dec(j); if (i <= j) then begin t := a[i]; a[i] := a[j]; a[j] := t; inc(i); dec(j); end; end; if (d < j) then Sort(d,j); if (i < c) then Sort(i,c); end; { Max cua 3 so nguyen a, b, c } function Max(a, b, c: integer): integer; begin if a < b then a := b; if a < c then Max := c else Max := a; end; procedure Tinhd(k: integer); var i,j,t: integer; begin d[k] := 1; for i := 1 to k-1 do for j := i + 1 to k - 1 do begin t := a[i] + a[j]; if t > a[k] then break; if t = a[k] then begin d[k] := Max(d[k], d[i]+1, d[j]+1); break; end; end; end; function MaxPath: integer; var k, dmax: integer; begin MaxPath := 0; if (n = 0) then exit; d[1] := 1; dmax := 1; for k := 2 to n do begin Tinhd(k); if d[k] > dmax then dmax := d[k]; end; MaxPath := dmax; end; procedure Ghi(m: integer); begin assign(g,gn); rewrite(g); writeln(g,m); close(g); end; BEGIN Doc; Sort(1,n); Ghi(MaxPath); END. // DevC++: Loco.cpp #include #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = "loco.inp"; const char * gn = "loco.out"; const int mn = 10001; int a[mn], d[mn]; int n; // P R O T O T Y P E S void Doc(); void Sort(int, int); int Max(int, int, int); int MaxPath(); void Tinhd(int); void Ghi(int); // I M P L E M E N T A T I O N int main(){ Doc(); Sort(1,n); Ghi(MaxPath()); cout << endl; system("PAUSE"); return EXIT_SUCCESS; } void Ghi(int m){ ofstream g(gn); g << m; g.close(); } // Max cua 3 so nguyen a, b, c int Max(int a, int b, int c){ if (a < b) a = b; return (a > c) ? a : c; } int MaxPath(){ int k, dmax = 1; if (n == 0) return 0; d[1] = 1; for (k = 2; k <= n; ++k){ Tinhd(k); if (dmax < d[k]) dmax = d[k]; } return dmax; } void Tinhd(int k){ int i, j, t; d[k] = 1; for (i = 1; i < k ; ++i) for (j = i+1 ; j < k ; ++j){ t = a[i]+a[j]; if (t > a[k]) break; if (t == a[k]){ d[k] = Max(d[k],d[i]+1,d[j]+1); break; } } } void Doc(){ ifstream f(fn); f >> n; int i; for (i=1; i <= n; ++i) f >> a[i]; f.close(); } void Sort(int d, int c){ int i = d, j = c, m = a[(i+j)/2]; int t; while (i <= j){ while (a[i] < m) ++i; while (a[j] > m) --j; if (i <= j){ t = a[i]; a[i] = a[j]; a[j] = t; ++i; --j; } } if (d < j) Sort(d,j); if (i < c) Sort(i,c); } Cải tiến 1 Khi tính d[k] ta nên tìm kiếm nhị phân trên đoạn được sắp tăng a[i+1..k–1] như sau. Biết trước a[k], với mỗi i ta biết a[i] và cần tìm a[j] trong đoạn a[i+1..k1] thoả điều kiện a[i] + a[j] = a[k]. Đặt t = a[k] – a[i], bài toán quy về việc tìm phần tử a[j] = t trong đoạn sắp tăng a[i+1..k1]. Nếu tìm được thì ta cập nhật d[k]. Cải tiến này giảm độ phức tạp xuống còn (log n).n2. Hàm Binsearch(t,s,e) dưới đây thực hiện việc tìm kiếm nhị phân giá trị t trong đoạn sắp tăng a[s..e] của mảng a. Hàm cho ra chỉ số j trong khoảng s..e nếu a[j] = t; ngược lại, khi không tồn tại chỉ số j như vậy thì hàm cho ra giá trị 0. Hàm Binsearch hoạt động như sau:
(* Pascal: Loco, Cai tien 1 *) uses crt; const fn = 'loco.inp'; gn = 'loco.out'; mn = 10001; bl = #32; nl = #13#10; type mi1 = array[0..mn] of integer; var f,g: text; a,d: mi1; n: integer; procedure Doc; Tự viết procedure Sort(d,c: integer); Tự viết function Max(a, b, c: integer): integer; Tự viết { Tim j trong khoang s..e thoa: a[j] = t } function Binsearch(t,s,e: integer): integer; var m: integer; begin Binsearch := 0; if s > e then exit; while (s < e) do begin m := (s+e) div 2; if (a[m] < t) then s := m+1 else e := m; end; if (a[s] = t) then Binsearch := s else Binsearch := 0; end; procedure Tinhd(k: integer); var i,j,t: integer; begin d[k] := 1; for i := 1 to k-1 do begin t := a[k] – a[i]; if (t > 0) then begin j := Binsearch(t, i+1, k-1); if j > 0 then d[k] := Max(d[k], d[i]+1, d[j]+1); end; end; end; function MaxPath: integer; var k, dmax: integer; begin if (n = 0) then begin MaxPath := 0; exit end; if (n = 1) then begin MaxPath := 1; exit end; dmax := 1; d[1] := 1; d[2] := 1; for k := 3 to n do begin Tinhd(k); if d[k] > dmax then dmax := d[k]; end; MaxPath := dmax; end; procedure Ghi(m: integer); Tự viết BEGIN Doc; Sort(1,n); Ghi(MaxPath); END. // DevC++, Loco.cpp: Cai tien 1 #include #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = "loco.inp"; const char * gn = "loco.out"; const int mn = 10001; int a[mn], d[mn]; int n; // P R O T O T Y P E S void Doc(); void Sort(int, int); int Max(int, int, int); int Binsearch(int, int, int); int MaxPath(); void Tinhd(int); void Ghi(int); // I M P L E M E N T A T I O N int main(){ Doc(); Sort(1,n); Ghi(MaxPath()); return EXIT_SUCCESS; } void Ghi(int m) tự viết int Max(int a, int b, int c) tự viết // Tim nhi phan vi tri xua hien cua x trong a[s.e] int Binsearch(int t, int s, int e){ int m; if (s > e) return 0; while (s < e) { m = (s+e) / 2; if (a[m] < t) s = m + 1; else e = m; } return (a[s] == t) ? s : 0; } int MaxPath(){ if (n == 0) return 1; if (n == 1) return 1; d[1] = d[2] = 1; int k, dmax = 1; for (k = 3; k <= n; ++k){ Tinhd(k); if (dmax < d[k]) dmax = d[k]; } return dmax; } void Tinhd(int k){ int i, j, t; d[k] = 1; for (i = 1; i < k ; ++i) { t = a[k]-a[i]; if (t > 0){ j = Binsearch(t,i+1,k-1); if (j > 0) d[k] = Max(d[k],d[i]+1,d[j]+1); } } } void Doc() tự viết; void Sort(int d, int c) tự viết; Cải tiến 2 Để ý rằng nếu trong dãy a có hai phần tử a[i] = a[j], tức là có hai đỉnh chứa cùng một giá trị thì trong kết quả cuối cùng ta phải có d[i] = d[j], tức là số lượng đỉnh trên các đường đi dài nhất kết thúc tại i và j phải bằng nhau. Tuy nhiên ta phải xử lý trường hợp a[i] = a[j], i j và tồn tại k để a[i]+a[j] = 2a[i] = a[k]. Khi đó ta vẫn có 2 cung ik và jk; và d[k] dĩ nhiên cần được cập nhật. Nhận xét này cho phép ta lược bớt các gía trị trùng lặp chỉ giữ lại tối đa hai phần tử bằng nhau. Cải tiến 3 Nếu các giá trị của dãy a là đủ nhỏ, thí dụ nằm trong khoảng 1.. 20000 thì ta có thể dùng mảng để đánh dấu. Ta sẽ mã số đỉnh bằng chính giá trị chứa trong đỉnh. Ta đặt s[i] = 1 nếu i xuất hiện duy nhất 1 lần trong input file; s[i] = 2 nếu i xuất hiện nhiều lần trong input file; ngược lại, nếu i không xuất hiện trong dãy thì ta đặt s[i] = 0.
Sau đó, để tính d[k] ta chỉ xét những giá trị k xuất hiện trong dãy đã cho, nghĩa là s[k] > 0. Với mỗi i = 1..k/2 ta xét, nếu i và j = ki đều có trong dãy, tức là s[i] > 0 và s[ki] > 0 thì ta đặt d[k] = max(d[k], d[i] + 1, d[ki] + 1). Cuối cùng ta xét thêm trường hợp k là số chẵn và s[k/2] = 2, nghĩa là k là tổng của hai số bằng nhau và có mặt trong dãy.
Cải tiến này rút độ phức tạp tính toán xuống còn n2. Bạn lưu ý sử dụng Free Pascal để có đủ miền nhớ. (* Loco.pas: Cai tien 3 *) uses crt; const fn = 'loco.inp'; gn = 'loco.out'; mn = 20000; bl = #32; nl = #13#10; type mi1 = array[0..mn+1] of integer; var f,g: text; s,d: mi1; n: integer; maxv: integer; { Gia tri max trong input file } procedure Doc; var i,j: integer; begin assign(f,fn); reset(f); maxv := 0; readln(f,n); fillchar(s,sizeof(s),0); for i := 1 to n do begin read(f,j); if (maxv < j) then maxv := j; if s[j] > 0 then s[j] := 2 else s[j] := 1; end; close(f); end; function Max(a, b, c: integer): integer; tự viết procedure Tinhd(k: integer); var i,k2: integer; begin d[k] := 1; k2 := (k-1) div 2; for i := 1 to k2 do if (s[i] > 0) and (s[k-i] > 0) then d[k] := Max(d[k], d[i]+1, d[k-i]+1); if (not odd(k)) then begin inc(k2); if (s[k2] = 2) then d[k] := Max(d[k], d[k2]+1, d[k2]+1); end; end; function MaxPath: integer; var k, dmax: integer; begin fillchar(d,sizeof(d),0); dmax := 0; for k := 1 to maxv do if s[k] > 0 then begin Tinhd(k); if d[k] > dmax then dmax := d[k]; end; MaxPath := dmax; end; procedure Ghi(m: integer); tự viết BEGIN Doc; Ghi(MaxPath); END. // DevC++: Loco.cpp, Phuong an Cai tien 3 #include #include #include using namespace std; // D A T A A N D V A R I A B L const char * fn = "loco.inp"; const char * gn = "loco.out"; const int mn = 10001; int s[mn], d[mn]; int n; int maxv; // Gia tri max trong input file // P R O T O T Y P E S void Doc(); int Max(int, int, int); int MaxPath(); void Tinhd(int); void Ghi(int); // I M P L E M E N T A T I O N int main(){ Doc(); Ghi(MaxPath()); cout << endl; system("PAUSE"); return EXIT_SUCCESS; } void Ghi(int m) Tự viết int Max(int a, int b, int c) Tự viết int MaxPath(){ int k, dmax = 0; memset(d,0,sizeof(d)); for (k = 1; k <= maxv; ++k) if (s[k] > 0){ Tinhd(k); if (dmax < d[k]) dmax = d[k]; } return dmax; } void Tinhd(int k){ int i, k2 = (k-1)/2; d[k] = 1; for (i = 1; i <= k2 ; ++i) if (s[i] > 0 && s[k-i] > 0) d[k] = Max(d[k],d[i]+1,d[k-i]+1); k2 = k/2; if ((2*k2 == k) && (s[k2] > 1)) d[k] = Max(d[k],d[k2]+1,d[k2]+1); } void Doc(){ ifstream f(fn); f >> n; memset(s,0,sizeof(s)); int i, j; for (i=1; i <= n; ++i){ f >> j; if (maxv < j) maxv = j; if (s[j] > 0) s[j] = 2; else s[j] = 1; } f.close(); } Каталог: 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:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||