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.
|
4.6 Chuyển biTrên một bảng chia 2n+1 ô người ta đặt n viên bi xanh liền nhau, mỗi ô 1 viên, sau đó bỏ một ô trống và đặt tiếp n viên bi đỏ như hình a. Hãy tìm cách chuyển với số lần ít nhất để thu được hình b, trong đó các viên bi xanh được chuyển qua trái của ô trống, các viên bi đỏ được chuyển qua phải ô trống. Mỗi lần được phép chuyển một viên bi vào ô trống kề viên bi đó hoặc cách viên bi đó 1 ô.
Thuật toán Ta kí hiệu x(n) là dãy gồm n chữ cái x. Bài toán khi đó được phát biểu như sau: b(n)or(n) r(n)ob(n) Nếu chuyển dần từng viên bi xanh đến vị trí cần thiết ở bên phải thì mỗi lần chuyển một bi xanh qua phải một vị trí ta phải theo sơ đồ với 2 bước chuyển như sau: ...bor... ...obr... ...rbo... Để thực hiện phép chuyển một bi xanh về cuối dãy b(n)or(n) = b(n-1)bor(n) b(n-1)r(n)bo ta cần 2n bước chuyển. Sau đó ta lại phải thực hiện n+1 bước để chuyển ô trống về đầu trái của dãy r(n) theo sơ đồ: b(n-1)r(n)bo b(n-1)or(n)b Vậy để chuyển một bi xanh về cuối dãy sau đó đưa ô trống về đầu trái của dãy r(n) theo sơ đồ ...bor(n) ...r(n)bo ...or(n)b ta cần 3n+1 bước chuyển. Để chuyển n-1 bi xanh qua phải theo sơ đồ b(n)or(n) = bb(n-1)or(n) bor(n)b(n-1) ta cần (n-1)(3n+1) bước chuyển. Với viên bi xanh còn lại cuối cùng ta sẽ chuyển theo sơ đồ sau bor(n)b(n-1) r(n)bob(n-1) (2n bước chuyển) r(n)obb(n-1) (1 bước chuyển) = r(n)ob(n). Vậy tổng cộng ta cần (n-1)(3n+1)+2n+1 = 3n2+n-3n-1+2n+1 = 3n2 bước chuyển. Với n = 3 ta cần 3.32 = 27 bước chuyển cụ thể như sau:
bbrrorb bbrorrb bborrrb bobrrrb brborrb brobrrb brrborb brrobrb brrrbob brrrobb brrorbb brorrbb borrrbb obrrrbb rborrbb robrrbb rrborbb rrobrbb rrrbobb rrrobbb. Ta sẽ cải tiến thuật toán trên để thu được một thuật toán với số bước chuyển là n(n+2). Ta gọi thuật toán này là thuật toán quả lắc vì cơ chế hoạt động của nó rất giống với dao động của quả lắc. Trước hết ta đề xuất một số heuristics trợ giúp cho việc tối ưu hóa số lần chuyển:
Ta theo dõi sự di chuyển của ô trống. Ta kí hiệu 1 nếu ô trống được chuyển qua trái 1 vị trí, +1 nếu ô trống được chuyển qua phải 1 vị trí; +2(k) nếu ô trống được chuyển qua phải k lần, mỗi lần 2 vị trí và 2(k) nếu ô trống được chuyển qua trái k lần, mỗi lần 2 vị trí. Với n = 3 như thí dụ đã cho, ta có dãy gồm 15 phép chuyển ô trống như sau: Cấu hình ban đầu: bbborrr 1; +2(1): bbobrrr, bbrborr - dịch ô trống qua trái 1 ô sau đó dịch ô trống qua phải 1 lần nhảy 2 ô, +1; 2(2): bbrbror, bbrorbr, borbrbr - dịch ô trống qua phải 1 ô sau đó dịch ô trống qua trái 2 lần, mỗi lần 2 ô, 1; +2(3): obrbrbr, rbobrbr, rbrbobr, rbrbrbo - dịch ô trống qua trái 1 ô sau đó dịch ô trống qua phải 3 lần, mỗi lần 2 ô, 1; 2(2): rbrbrob, rbrorbb, rorbrbb - dịch ô trống qua trái 1 ô sau đó dịch tiếp ô trống qua trái 2 lần, mỗi lần 2 ô, +1; +2(1): rrobrbb, rrrbobb, - dịch ô trống qua phải 1 ô sau đó dịch tiếp ô trống qua phải 1 lần nhảy 2 ô, 1: rrrobbb - dịch ô trống qua trái 1 ô. Hoàn thành. Bạn dễ dàng phát hiện rằng thuật toán trên vận dụng tối đa 2 heuristics nói trên. Tổng quát, ta mô tả thuật toán theo sơ đồ sau: Pha 1: (1)i ; (1)i+1.2(i); i = 1, 2, ..., n - hai phép chuyển trái dấu nhau; Pha 2: (1)i+1 ; (1)i+1.2(i); i = n1, ..., 1 – hai phép chuyển cùng dấu. Cuối cùng thực hiện phép chuyển 1. Ta sử dụng thủ tục Move(h,k) : chuyển ô trống k lần, mỗi lần h ô, h = 1, 1, 2, 2. Nếu h > 0 thì chuyển qua phải, ngược lại, khi h < 0 thì chuyển qua trái. Khi đó sơ đồ hai pha nói trên được triển khai như sau: Pha 1: Move((1)i, 1); Move((1)i+1*2, i); i = 1, 2, ..., n. Pha 2: Move((1)i+1, 1); Move((1)i+1*2, i); i = n1, ..., 1. Nếu ta để ý rằng (1)i và (1)i+1 trái dấu nhau và (1)i+1 và (1)i+1 cùng dấu thì hai pha nói trên có thể cài đặt thông qua một biến nguyên sign quản lý dấu như sau: (* Pascal *) { Pha 1 } sign := -1; for i := 1 to n do begin Move(sign, 1); sign := -sign; Move(sign*2,i) end; { Pha 2 } sign := -sign; for i := n-1 downto 1 do begin Move(sign, 1); Move(sign*2,i); sign := -sign end; // Devcpp // Pha 1 sign = -1; for (i = 1; i <= n; ++i) { Move(sign, 1); sign = -sign; Move(sign*2,i); } // Pha 2 sign = -sign; for (i = n-1; i > 0; --i){ Move(sign, 1); Move(sign*2,i); sign = -sign; } Chương trình (* balls.pas *) uses crt; const fn = 'balls.inp'; gn = 'balls.out'; nl = #13#10; var n, v: integer; d: longint; (* n - so vien bi xanh = so vien bi do v - vi tri o trong d - tong so lan dich chuyen *) a: string; f,g: text; procedure Init; var i: integer; begin a := ''; for i := 1 to n do a := a + 'b'; a := a + 'o'; for i := 1 to n do a := a + 'r'; d := -1; v := n+1; { vi tri o trong o } end; procedure PP; begin writeln(g,a); inc(d) end; { Ghi file } procedure Swap(i,j: integer); var c: char; begin c := a[i]; a[i] := a[j]; a[j] := c; PP end; (* chuyen bi h > 0: qua phai h o h < 0: qua trai h o k: so lan *) procedure Move(h,k: integer); var i: integer; begin for i := 1 to k do begin Swap(v, v+h); v := v + h; end; end; procedure Balls; var i, sign: integer; begin assign(f,fn); reset(f); readln(f,n); close(f); assign(g,gn); rewrite(g); Init; writeln(n); PP; sign := -1; for i := 1 to n do begin Move(sign, 1); sign := -sign; Move(sign*2,i) end; sign := -sign; for i := n-1 downto 1 do begin Move(sign, 1); Move(sign*2,i); sign := -sign end; Move(-1,1); writeln(g,d); close(g); end; BEGIN Balls; writeln(nl,' Total ',d, ' move(s)',nl); write(nl,' Fini'); readln; END. // DEV-C++: balls.cpp #include #include #include using namespace std; // D A T A A N D V A R I A B L E const int mn = 202; char a[mn]; int n, v, n2, d; /* n - so vien bi xanh = so vien bi do v - vi tri o trong n2 = 2n+1 - tong so o d - tong so lan dich chuyen */ // P R O T O T Y P E S void Init(); void PP(); void Run(); void Balls(); void Swap(int, int); void Move(int, int); ofstream f("BALLS.OUT"); // I M P L E M E N T A T I O N int main(){ Balls(); f << d; f.close(); cout << endl << " Total " << d << " move(s)" << endl; cout << endl << " Fini"; system("PAUSE"); return EXIT_SUCCESS; } void Init() { int i; for (i = 1; i <= n; ++i) a[i] = 'b'; // blue a[n+1] = 'o'; n2 = n+n+1; for (i = n+2; i <= n2; ++i) a[i] = 'r'; // red d = -1; v = n+1; // vi tri o trong o } void PP() { // Ghi file for (int i = 1; i <= n2; ++i) f << a[i]; f << endl; ++d; } void Swap(int i, int j) { char c = a[i]; a[i] = a[j]; a[j] = c; PP(); } /* chuyen bi h > 0: qua phai h o; h < 0: qua trai h o; k: so lan */ void Move(int h, int k) { for (int i = 0; i < k; v += h, ++i) Swap(v, v+h); } void Balls() { ifstream inf("BALLS.INP"); inf >> n; inf.close(); Init(); cout << n ; PP(); cout << endl; int i, sign = -1; for (i = 1; i <= n; ++i) { Move(sign, 1); sign = -sign; Move(sign*2,i); } sign = -sign; for (i = n-1; i > 0; --i){ Move(sign, 1); Move(sign*2,i); sign = -sign; } Move(-1,1); } Độ phức tạp Tại pha 1 ta chuyển ô trống 1 vị trí n lần và 2 vị trí (1 + 2 +...+n) lần, tổng cộng n + n(n+1)/2 lần. Tại pha 2 ta chuyển tương tự như trên nhưng với n1 lần: Ta có tổng cộng (n1) + n(n1)/2. Lần cuối cùng ta chuyển 1 lần ô trống qua trái. Vậy tổng cộng số lần chuyển là: t = n + n(n+1)/2 + (n1) + n(n1)/2 + 1 = n(n+2). Với n = 3 ta cần 3.5 = 15 lần thay vì 27 lần như thuật toán thứ 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:
|