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.4 Tổng nhỏ nhấtViệt Nam, 2008 Cho hai dãy số nguyên ai và bi, i = 1, 2, ..., n chứa các gía trị trong khoảng -1 tỷ đên 1 tỷ, 1 n 1000. Tìm giá trị nhỏ nhất của ||ai+bj||, 1 i, j n.
Thuật toán Trước hết ta sắp tăng hai dãy a và b. Sau đó, với mảng a ta duyệt xuôi theo chỉ số i biến thiên từ 1..n, với mảng b ta duyệt ngược theo chỉ số j biến thiên từ n về 1. Đặt t(i,j) = ai + bj ta có nhận xét sau: 1. t là một hàm 2 biến theo i và j, 2. Nếu cố định i, cho j giảm dần thì t là hàm đồng biến theo j, nghĩa là t(i,j) t(i,j') nếu j > j'. 3. Nếu cố định j thì t là hàm đồng biến theo i, nghĩa là t(i,j) t(i',j) nếu i < i'. Từ nhận xét trên ta suy ra chiến lược tìm kiếm trị nhỏ nhất của ||t(i,j)|| trong hàm XuLi như sau: - Nếu t(i,j) = 0 ta nhận giá trị này và kết thúc thuật toán. - Nếu t(i,j) < 0 ta cần tăng giá trị của hàm này bằng cách tăng i thêm 1 đơn vị. - Nếu t(i,j) > 0 ta cần giảm giá trị của hàm này bằng cách giảm j bớt 1 đơn vị. Sau một số bước lặp ta gặp tình huống, hoặc i = n hoặc j = 1. Ta xử lý tiếp như sau: - Nếu i = n, ta cần duyệt nốt phần còn lại b[j..1], nghĩa là tính t(n,k) với k = j..1. Vì đây là hàm đồng biến nên khi t(n,k) 0 ta dừng thuật toán. - Tương tự, nếu j = 1, ta cần duyệt nốt phần còn lại của a[j..n], nghĩa là tính t(k,1) với k = i..n. Vì đây là hàm đồng biến nên khi t(k,1) 0 ta cũng dừng thuật toán. Tại mỗi bước lặp ta tính và cập nhật giá trị min m của || t ||.
Thuật toán sắp xếp nhanh cần n.log2(n) phép so sánh. Khi tính giá trị min, mỗi bước lặp ta thay đổi đúng 1 trong 2 chỉ số i hoặc j do đó số phép so sánh là 2n. Tổng hợp lại ta cần cỡ n.log2(n) phép so sánh. Chương trình (* Pascal *) const bl = #32; nl = #13#10; fn = 'minsum.inp'; gn = 'minsum.out'; mn = 1001; type ml1 = array[1..mn] of longint; var a,b: ml1; n: integer; f,g: text; procedure Print(var a: ml1; d,c: integer); var i: integer; begin writeln; for i:= d to c do write(a[i],bl); end; procedure Sort(var a: ml1; d, c: integer); var i,j: integer; t,m: longint; 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(a,d,j); if (i < c) then Sort(a,i,c); end; procedure Ghi(m: longint); begin assign(g,gn); rewrite(g); writeln(g,m); close(g); end; function XuLi: longint; var i,j,v: integer; t,m: longint; begin XuLi := 0; Sort(a,1,n); Sort(b,1,n); writeln(nl,'Sau khi sap tang '); Print(a,1,n); Print(b,1,n); i := 1; j := n; m := MaxLongInt; while (i <= n) and (j >= 1) do begin t := a[i]+b[j]; v := abs(t); if (m > v) then m := v; if t = 0 then exit; if (t < 0) then inc(i) else dec(j); end; { i = n+1 or j = 0 } for i := i to n do begin t := a[i]+b[1]; v := abs(t); if (m > v) then m := v; if (t >= 0) then begin XuLi := m; exit end; end; for j := j downto 1 do begin t := a[n]+b[j]; v := abs(t); if (m > v) then m := v; if (t <= 0) then begin XuLi := m; exit end; end; XuLi := m; end; procedure Doc; var i: integer; begin assign(f,fn); reset(f); readln(f,n); for i := 1 to n do read(f,a[i]); for i := 1 to n do read(f,b[i]); close(f); end; procedure Run; begin Doc; writeln(nl,n); Print(a,1,n); Print(b,1,n); Ghi(XuLi); end; BEGIN Run; readln; END. // DevC++ #include #include #include #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = "minsum.inp"; const char * gn = "minsum.out"; const int mn = 1001; int a[mn], b[mn]; int n; // P R O T O T Y P E S void Doc(); void Print(int [], int , int); int XuLi(); void Ghi(int); void Sort(int [], int, int); void Run(); // I M P L E M E N T A T I O N int main(){ Run(); cout << endl; system("PAUSE"); return EXIT_SUCCESS; } void Run(){ Doc(); cout << endl << n; Print(a,1,n); Print(b,1,n); Ghi(XuLi()); } void Ghi(int m){ ofstream g(gn); g << m; g.close(); } int XuLi(){ Sort(a,1,n); Sort(b,1,n); cout << endl << "Sau khi sap tang "; Print(a,1,n); Print(b,1,n); int i = 1, j = n, m = 0x7fffffff, t, v; while (i <= n && j >= 1){ t = a[i]+b[j]; v = abs(t); if (m > v) m = v; if (t == 0) return 0; if (t < 0) ++i; else --j; } // i = n+1 || j = 0 for (;i <= n; ++i){ t = a[i]+b[1]; v = abs(t); if (m > v) m = v; if (t >= 0) return m; } for (;j >= 1;--j){ t = a[n]+b[j]; v = abs(t); if (m > v) m = v; if (t <= 0) return m; } return m; } void Sort(int a[], int d, int c){ int i = d, j = c, m = a[(d+c)/2], 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(a,d,j); if (i < c) Sort(a,i,c); } void Doc(){ ifstream f(fn); f >> n; int i; for (i = 1; i <= n; ++i) f >> a[i]; for (i = 1; i <= n; ++i) f >> b[i]; f.close(); } void Print(int a[], int d, int c){ int i; cout << endl; for (i = d; i <= c; ++i) cout << a[i] << " "; } Каталог: 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:
|