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.
|
- Điều hướng trang này:
- ViTri(k, i, j) = v
- ToaDo(2,8,i, j)
- ToaDo
- // P R O T O T Y P E S int ViTri(int, int, int); void ToaDo(int, int, int , int ); void Test(int);
- // Cho vi tri o tren cot v, tinh toa do (i,j). n = 2^k void ToaDo(int k, int v, int i, int j) { int n = 1, d = 1 d *= d;
- (* Pascal *) procedure Test(k: integer); var n, v, ii, jj : integer; begin n := 1 shl k; { n = 2^k }
5.3 Cắt hìnhViệt Nam, 2008 Một tấm bìa dạng lưới vuông cạnh dài n = 2k tạo bởi các ô vuông đơn vị đánh số theo dòng 1.. n tính từ trên xuống và theo cột 1..n tính từ trái sang. Người ta thực hiện lần lượt hai thao tác đan xen nhau sau đây cho đến khi nhận được một cột gồm n2 ô vuông đơn vị: 1. Cắt ngang hình theo đường kẻ giữa sau đó chồng nửa trên lên trên nửa dưới; 2. Cắt dọc hình theo đường kẻ giữa sau đó chồng nửa trái lên trên nửa phải. Tại cột cuối cùng người ta đánh số các ô vuông đơn vị 1, 2,..., n2 tính từ trên xuống. Hãy viết hai thủ tục sau đây a) ViTri(k, i, j) = v cho ra số thứ tự v của ô (i,j) trên cột cuối cùng. b) ToaDo(k, v, i, j) Cho trước k và vị trí v trên cột cuối cùng, tính tọa độ (i,j) của ô ban đầu. Thí dụ ViTri(2, 4, 3) = 8. ToaDo(2,8,i, j) cho kết quả i = 4, j = 3. Thuật toán Ta khảo sát bài toán với k = 2. Ta có n = 2k = 22 = 4. Ta kí hiệu ô nằm trên dòng i, cột j là [i,j].
Ta chọn cách mã số các mảnh A, B, C và D một cách khôn ngoan. Cụ thể là ta gán mã số cho các mảnh này theo số lần cộng thêm độ dày d sau mỗi lần ND, tức là ta đặt A = 0, B = 1, C = 2 và D = 3. Trong dạng nhị phân ta có A = 002, B = 012, C = 102 và D = 112.
function ViTri(k,i,j: integer): integer; var d, v, m, manh, n: integer; begin d := 1; { so tang } v := 1; { tang chua o [i,j] } n := 1 shl k; { n = 2^k } for m := 1 to k do begin n := n div 2; manh := 0; if (j > n) then begin manh := 2; j := j - n; end; if (i > n) then begin manh := manh + 1; i := i - n; end; v := v + manh*d; d := 4*d; end; ViTri := v; end; Thủ tục ToaDo là đối xứng với thủ tục ViTri. procedure ToaDo(k,v: integer; var i,j: integer); var n,nn,m,d, manh: integer; begin n := 1 shl k; d := n*n; n := 1 ; { kich thuoc 1 tang } i := 1; j := 1; for m := 1 to k do begin d := d div 4; manh := (v-1) div d; if (manh >= 2) then j := j+n; if odd(manh) then i := i+n; v := v - manh*d; n := n * 2; end; end; // DevC++ #include using namespace std; // P R O T O T Y P E S int ViTri(int, int, int); void ToaDo(int, int, int &, int &); void Test(int); // I M P L E M E N T A T I O N int main() { Test(2); cout << endl; system("PAUSE"); return EXIT_SUCCESS; } // Cho biet k va toa do (i,j). Tim vi tri tren cot int ViTri(int k, int i, int j) { int n = 1 << k; // kich thuoc hinh: n = 2^k int d = 1; // be day 1 tang int v = 1; // vi tri; int manh; for (int m = 0; m < k; ++m) { n >>=1; // n = n/2 manh = 0; if (j > n) { manh = 2; j -= n; } if (i > n) { manh += 1; i -= n; } v += manh * d; d *= 4; } return v; } // Cho vi tri o tren cot v, tinh toa do (i,j). n = 2^k void ToaDo(int k, int v, int &i, int &j) { int n = 1, d = 1 << k, manh = 0; d *= d; i = j = 1; for (int m = 0; m < k; ++m) { d >>= 2; // d /= 4; manh = (v - 1) / d; if (manh >= 2) j += n; if (manh % 2 == 1) i += n; v -= manh * d; n *= 2; } } Độ phức tạp Với n = 2k chương trình cần k lần lặp, mỗi lần lặp cần thực hiện không quá 10 phép toán số học trên các số nguyên. Thủ tục Test dưới đây hiển thị vị trí v của mọi ô (i,j), i = 1..n, j = 1..n sau đó xuất phát từ vị trí v để tính lại tọa độ i, j.
Каталог: 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:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||