ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
PHẠM HẢI NINH
CÁC THUẬT TOÁN TÍNH DIỆN TÍCH VÀ
THỂ TÍCH VẬT THỂ KHÔNG GIAN VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
THÁI NGUYÊN - 2015
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
PHẠM HẢI NINH
CÁC THUẬT TOÁN TÍNH DIỆN TÍCH VÀ
THỂ TÍCH VẬT THỂ KHÔNG GIAN VÀ ỨNG DỤNG
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60 48 01 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƢỜI HƢỚNG DẪN KHOA HỌC
PGS TSKH NGUYỄN XUÂN HUY
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
THÁI NGUYÊN - 2015
i
LỜI CAM ĐOAN
Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng cá
nhân tôi, kết quả của luận văn hoàn toàn là kết quả của tự bản thân tôi tìm
hiểu, nghiên cứu dƣới sự hƣớng dẫn của giáo viên hƣớng dẫn PGS TSKH
Nguyễn Xuân Huy.
Tôi hoàn toàn chịu trách nhiệm về tính pháp lý quá trình nghiên cứu
khoa học của luận văn này.
Thái Nguyên, tháng 9 năm 2015
Học viên
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Phạm Hải Ninh
ii
LỜI CẢM ƠN
Lời đầu tiên, em xin gửi lời biết ơn sâu sắc đến PGS TSKH Nguyễn
Xuân Huy người đã tận tình hướng dẫn, chỉ bảo, giúp đỡ em trong suốt
quá trình làm luận văn.
Em cũng xin gửi lời cảm ơn đến các thầy cô giáo trường Đại học
Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên, các thầy cô
Viện Công nghệ thông tin đã truyền đạt những kiến thức và giúp đỡ em
trong suốt quá trình học của mình.
Học viên xin gửi lời cảm ơn tới Ban giám hiệu trường THPT Hồng
Bàng - Hải Phòng đã tạo điều kiện thuận lợi cho học viên tham gia khóa
học và quá trình hoàn thành luận văn.
Và học viên cũng xin gửi lời cảm ơn tới các đồng nghiệp, gia đình và
bạn bè những người đã ủng hộ, động viên tạo mọi điều kiện giúp đỡ để học
viên có được kết quả như ngày hôm nay.
Thái Nguyên, tháng 9 năm 2015
Học viên
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Phạm Hải Ninh
iii
MỤC LỤC
Trang
LỜI CAM ĐOAN ....................................................................................... i
LỜI CẢM ƠN ............................................................................................ ii
MỤC LỤC ................................................................................................ iii
DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT ................................. v
DANH MỤC CÁC HÌNH ......................................................................... vi
MỞ ĐẦU ................................................................................................... 1
Chƣơng 1: CÁC KHÁI NIỆM CƠ SỞ ....................................................... 2
1.1. Tổng quan về đề tài . ........................................................................ 2
1.1.1. Giới thiệu đề tài. ....................................................................... 2
1.1.2. Nội dung của đề tài, các vấn đề cần giải quyết. ........................ 2
1.1.3. Phƣơng pháp nghiên cứu. ......................................................... 3
1.1.4. Phạm vi ứng dụng. ................................................................... 3
1.1.5. Kết quả đạt đƣợc. ..................................................................... 3
1.1.6. Bố cục của luận văn.................................................................. 4
1.2. Khái niệm cơ sở . ............................................................................. 5
1.2.1. Khái quát cách tính diện tích các hình cơ bản. .......................... 5
1.2.2. Khái quát cách tính thể tích các hình cơ bản. .......................... 10
Chƣơng 2: MỘT SỐ THUẬT TOÁN TÍNH DIỆN TÍCH VÀ THỂ TÍCH
VẬT THỂ KHÔNG GIAN ...................................................................... 14
2.1. Thuâ ̣t toán tính diện tích của đa giác theo tọa độ đỉnh . .................. 14
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
2.2. Thuật toán tìm diện tích hình chữ nhật tối đại. .............................. 25
iv
2.3. Thuật toán tính thể tích vùng nƣớc đo ̣ng . ...................................... 33
Chƣơng 3: ỨNG DỤNG VÀ THỬ NGHIỆM .......................................... 45
3.1. Cơ sở lý thuyết và lựa chọn bài toán ứng dụng . ............................ 45
3.2. Bài toán: Dự án xây dựng sân bay. ................................................ 49
3.2.1. Phát biểu bài toán. .................................................................. 49
3.2.2. Mô tả dƣ̃ liê ̣u. ......................................................................... 49
3.2.3. Thiết kế các bƣớ c thƣ̣c hiê ̣n. ................................................... 50
3.3. Bài toán: Tính thể tích chứa nƣớc cho một lòng hồ . ...................... 54
3.3.1. Phát biểu bài toán. .................................................................. 54
3.2.2. Mô tả dữ liệu. ......................................................................... 55
3.3.3. Thiết kế các bƣớ c thƣ̣c hiê ̣n. ................................................... 56
3.4. Cài đặt chƣơng trình ...................................................................... 58
3.4.1. Chƣơng trình tính diê ̣n đa giác theo to ̣a đô ̣ đỉnh . .................... 58 3.4.2. Chƣơng trình tìm diện tích hình chữ nhật tối đại . ................... 59 3.4.3. Chƣơng trình tính thể tích vùng nƣớc đo ̣ng . ........................... 61
KẾT LUẬN ............................................................................................. 64
TÀI LIỆU THAM KHẢO ........................................................................ 65
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
PHỤ LỤC ................................................................................................ 66
v
DANH MỤC CÁC KÍ HIỆU, CHỮ CÁI VIẾT TẮT
Cơ sở dữ liệu CSDL:
Geographic Information System GIS:
(Hệ thống thông tin địa lý )
Hình chữ nhật HCN :
INP: Input (Dƣ̃ liê ̣u vào)
Nhà xuất bản NXB:
OUT: Output (Dƣ̃ liê ̣u ra)
S:
V:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Diê ̣n tích bề mă ̣t Thể tích (Dung tích) của vật thể Ví dụ VD:
vi
DANH MỤC CÁC HÌNH
Trang
Hình 1.1: Công thƣ́ c tính diê ̣n tích củ a mô ̣t số hình đă ̣c biê ̣t ...................... 7 Hình 1.2: Diện tích S của hình phẳng giới hạn bởi đồ thị các hàm số
liên tục trên đoạn [a, b] và hai đƣờng thẳng x = a, x = b .. 8
Hình 1.3: Công thƣ́ c tính thể tí ch củ a mô ̣t số khối hình đă ̣c biê ̣t .............. 12 Hình 1.4: Thể tích vật thể tròn xoay giớ i hạn bởi đồ thị hàm số y = f(x) ,
trục hoành và hai đƣờng thẳng x = a, x = b ............................................ 13
Hình 2.1: Hình chữ nhâ ̣t ABCD trong mă ̣t phẳng to ̣a đô ̣ Oxy .................. 16
Hình 2.2: Ngũ giác lõm ABCDE trong mặt phẳng tọa độ Oxy ................. 17
Hình 2.3: Ngũ giác lồi ABCDE trong mặt phẳng tọa độ Oxy ................... 18
Hình 2.4: Hình thang ABCD trong mặt phẳng tọa độ Oxy ....................... 19
Hình 2.5: Đa giác lồi, lõm trong mặt phẳng tọa độ Oxy ........................... 20
Hình 2.6: VD1 - Ma trâ ̣n chƣ́ a các kí tƣ̣ 0 và 1 ......................................... 25 Hình 2.7: VD2 - Ma trâ ̣n chƣ́ a các kí tƣ̣ 0 và 1 ......................................... 26 Hình 2.8: VD3 - Ma trâ ̣n chƣ́ a các kí tƣ̣ 0 và 1 ......................................... 27 Hình 2.9: VD1 - Ma trâ ̣n và cô ̣t thể hiện độ cao của các cột vuông cạnh 1
đơn vi ̣. ...................................................................................................... 34
Hình 2.10: VD2 - Ma trâ ̣n và cô ̣t thể hiê ̣n đô ̣ cao củ a các cô ̣t vuông ca ̣nh 1
đơn vi ̣. ...................................................................................................... 35
Hình 2.11: VD3 - Ma trâ ̣n và cô ̣t thể hiê ̣n đô ̣ cao củ a các cô ̣t vuông ca ̣nh 1
đơn vi ̣. ...................................................................................................... 35
Hình 3.1: Ma trận không gian của một file ảnh raster có cấu trúc pixel .... 46
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Hình 3.2: Các đối tƣợng không gian đƣợc mã hoá trong mô hình Raster . 47
vii
Hình 3.3: Các điểm ả nh đƣợc mã hoá trong mô hình Raster nhƣ mô ̣t ma
trâ ̣n số nguyên .......................................................................................... 49
Hình 3.4: Vùng địa hình khảo sát xây dựng sân bay ................................. 50
Hình 3.5: Ma trâ ̣n số nguyên thể hiê ̣n theo đô ̣ cao vù ng đi ̣a hình ............. 51 Hình 3.6: Vùng địa hình có một hồ chứa nƣớc ......................................... 56
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Hình 3.7: Ma trâ ̣n số nguyên theo đô ̣ cao vù ng có hồ ............................... 57
1
MỞ ĐẦU
Lịch sử của Toán học gắn liền với sự phát triển của loài ngƣời,
những khái niệm đƣợc hình thành hầu hết xuất phát từ đời sống thực tiễn,
từ nhu cầu tìm tòi và khám phá của con ngƣời. Một ví dụ kinh điển cho sự
ra đời ngành hình học thời Ai Cập cổ đại đấy là việc chia ruộng cho ngƣời
dân. Nếu không có sự ra đời các khác niệm chiều dài, chiều rộng, diện tích,
thể tích, và số đo góc, có lẽ những ngƣời Ai Cập khó có thể phân chia
ruộng một cách công bằng.
Thời xƣa khi con ngƣời chƣa có sự hỗ trợ của máy móc nên bản thân
các bài toán phát sinh chỉ là các bài đơn giản, số lƣợng tính toán là cỡ nhỏ,
việc tính diện tích và thể tích chỉ áp dụng đối với các hình đặc biệt. Với các
hình phức tạp ngƣời ta tính bằng phƣơng pháp gần đúng hoặc chia ra thành
các hình nhỏ. Vì vậy các công cụ toán để sử dụng cũng là những công thức
vô cùng đơn giản và sơ khai nhƣ phép cộng, phép chia, hay khai căn một
cách gần đúng.
Ngày nay, cùng với sự hỗ trợ của máy tính, các bài toán con ngƣời
có thể đặt ra là vô cùng trừu tƣợng và phức tạp, với số lƣợng phép tính lớn,
vƣợt xa ra khỏi khả năng tự nhiên của một con ngƣời. Vì vậy các công cụ
tính toán và các khái niệm mới cũng hết sức trừu tƣợng.
Trong khuôn khổ của mình, luận văn sẽ trình bày về một số thuật
toán tính diện tích và thể tích nhằm tính toán diện tích bề mặt cho các vật ,
cho các đi ̣a hình trong thƣ̣c tế . Đồng thời đề cập về ứng dụng của các thuật toán trên để từ đó cài đặt chƣơng trình thử nghiệm làm rõ hơn một số nội
dung về tính toán trừu tƣợng hoặc xử lí những khối lƣợng tính toán phức
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
tạp mà con ngƣời cần tính toán.
2
Chƣơng 1: CÁC KHÁI NIỆM CƠ SỞ
1.1. Tổ ng quan về đề tài
1.1.1. Giới thiệu đề tài
Việc tính diện tích và tính thể tích luôn đƣợc con ngƣời quan tâm và
ứng dụng trong thực tế. Để xác định, tính toán về mặt định lƣợng trên bề
mặt hay dung tích chúng ta cần phải dựa vào số đo là diện tích và thể tích.
Trong các lĩnh vực nhƣ xây dựng, thủy lợi, khai khoáng, ... con ngƣời cũng
cần phải dựa vào các con số tính toán nhiều chính là diện tích và thể tích
vật thể. Trong thƣ̣c tế nhƣ̃ng bài toán về tính diê ̣n tích và thể tích có thể có nhiều cách tính và phƣơng pháp tính khác nhau . Vớ i đề tài luận văn ”Các thuật toán tính diện tích và thể tích vật thể không gian và ứng dụng” nhằm
tìm hiểu các cách tiếp cận về cách tính diện tích và thể tích của các hình,
các vật thể đặc biệt. Đồng thời phân tích bài toán , hình thành ý tƣởng và xây dựng thuật toán về cách tính diện của một đa giác khi biết tọa độ đỉnh ,
tìm diện tích phẳng là hình chữ nhật tối đại và tính thể tích vùng nƣớc
đo ̣ng. Từ đó đề tài cũng nêu và giải quyết một số ứng dụng có trong thực tế
mà áp dụng từ các thuật toán đã trình bày.
1.1.2. Nội dung của đề tài, các vấn đề cần giải quyết
- Giới thiệu tổng quan việc tính diện tích, thể tích vật thể không gian.
- Tìm hiểu các thuật toán liên quan tính diện tích, thể tích vật thể
không gian.
- Cài đặt thử nghiệm các thuật toán đã xây dựng.
- Ứng dụng và xây dựng chƣơng trình bài toán ứng dụng trong một
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
số lĩnh vực có trong thực tế.
3
1.1.3. Phƣơng pháp nghiên cứu
- Phƣơng pháp nghiên cứu lý thuyết: Tìm hiểu, tổng hợp tài liệu,
phân tích, đánh giá các phƣơng pháp.
- Phƣơng pháp đối sánh .
- Phƣơng pháp trao đổi khoa học, lấy ý kiến chuyên gia.
- Phƣơng pháp thực nghiệm: xây dựng chƣơng trình cụ thể để thử
nghiệm, phân tích, đánh giá kết quả đạt đƣợc.
1.1.4. Phạm vi ứng dụng
Phạm vi nghiên cứu của đề tài đƣợc giới hạn trong việc xây dựng
các phƣơng pháp thực hiện, chú trọng vào mô hình tính toán, thuật toán và
chƣơng trình máy tính. Tính toán thực nghiệm cho một khu vực địa lý cụ
thể.
Ứng dụng tính diện tích phẳng tối đa cho phép trên một địa hình và
thể tích chứa nƣớc của một lòng hồ.
1.1.5. Kết quả đạt đƣợc
Tổng hợp mô ̣t số cách tiếp câ ̣n để tính diện tích, thể tích các hình,
khối hình học và các vật thể cơ bản.
Phân tích bài toán , hình thành ý tƣởng và xây dựng thuật toán cũng
nhƣ chƣơng trình cho các thuâ ̣t toán sau : Thuâ ̣t toán tính diện tích đa giác theo to ̣a đô ̣ đỉnh, thuật toán tìm diện tích hình chữ nhật tối đại và thuật toán tính thể tích vùng nƣớc đo ̣ng.
Thiết lập tƣơng quan giữa các thuật toán vào thực tế để tính toán
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
những khối lƣợng công việc tƣởng nhƣ trừu tƣợng, khó tính toán.
4
Nâng cao kĩ năng về phân tích dữ liệu thực tế với chƣơng trình chạy
thực nghiệm.
1.1.6. Bố cục của luận văn
Chƣơng 1: CÁC KHÁI NIỆM CƠ SỞ
Bố cục của luận văn bao gồm 3 chƣơng:
Chƣơng này học viên trình bày tổng quan về đề tài và tóm tắt các
cách tiếp cận để tính diện tích đối với các hình đặc biệt, tính thể tích đối
Chƣơng 2: MỘT SỐ THUẬT TOÁN TÍNH DIỆN TÍCH VÀ THỂ
với các khối hình đặc biệt.
TÍCH VẬT THỂ KHÔNG GIAN
Chƣơng này học viên trình bày các thuật toán sau: Thuâ ̣t toán tính diện tích đa giác theo to ̣a đô ̣ đỉnh, thuật toán tìm diện tích hình chữ nhật tối
Chƣơng 3: ỨNG DỤNG VÀ THỬ NGHIỆM
đại và thuật toán tính thể tích vùng nƣớc đo ̣ng.
thuật toán đƣợc trình bày ở Dựa vào cơ sở lý thuyết GIS và các
chƣơng 2, trong chƣơng này học viên trình bày cụ thể hơn về bài toán ứng
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
dụng trong thực tế trên mô ̣t vù ng đi ̣a hình .
5
1.2. Khái niệm cơ sở
1.2.1. Khái quát cách tính diện tích các hình cơ bản
Diện tích là độ đo dùng để đo độ lớn bề mặt của vật thể . Diện tích bề
mặt của một đối tƣợng là toàn bộ những gì ta có thể nhìn thấy của đối
tƣợng. Diện tích có đơn vị đo là bình phƣơng của khoảng cách (khoảng
cách mũ 2). Trong hệ đo lƣờng quốc tế, nếu đơn vị đo của khoảng cách là cm thì đơn vị đo của diện tích là cm2, nếu đơn vị đo của khoảng cách là km thì đơn vị đo của diện tích là km2, nếu đơn vị đo của khoảng cách là m thì đơn vị đo của diện tích là m2 [6].
Việc tính diện tích các khối hình chúng ta có thể có những cách tiếp
cận, những cách tính khác nhau. Đối với các hình đặc biệt ta thƣờng dựa
vào độ dài các thông số cơ bản của hình, có cách tính nhanh và dễ nhớ. Ví
nhƣ đoạn thơ sau có thể mô tả nhanh về công thức tính diện tích với một số
hình đặc biệt:
Muốn tính diện tích hình thang
Đáy lớn, đáy nhỏ ta mang cộng vào
Rồi đem nhân với đƣờng cao
Chia đôi kết quả thế nào cũng ra.
Chữ nhật ta đã học qua
Dài nhân với rộng thế là ra ngay
Hình vuông quả thật là hay
Cạnh nhân với cạnh ra ngay tức thì
Tam giác thì có khó chi
Cao nhân với đáy ta thì chia đôi
Hình tròn tính cũng dễ thôi
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Bán kính bán kính nhân pi là thành
6
Khối hộp làm cũng thật nhanh
Muốn tìm diện tích xung quanh khó gì
Sau đây là tổng quan về tính diện tích của các hình đặc biệt thông
Hình tam giác (Cách 1)
Hình tam giác (Cách 2)
Hình thoi
Hình tứ giác
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
qua các yếu tố hình học cơ bản và công thức tính [6], [7]:
Hình thang
Hình tròn
Hình 1.1: Công thứ c tính diê ̣n tích của một số hình đặc biê ̣t
7
Từ những công thức với các hình đặc biệt trên khi muốn tính diện tích
của các hình có hình thù phức tạp ngƣời ta có thể chia hình đó thành những
hình đặc biệt nhỏ khác nhau. Công việc tính diện tích lúc này trở nên đơn
giản hơn là tổng diện tích của các hình nhỏ đặc biệt, tuy nhiên không phải
hình nào cũng có thể chia về các hình đặc biệt và việc chia có thể cho ta kết
quả gần đúng chƣa kể chúng ta phải sử dụng tƣơng đối nhiều phép đo.
Trong toán học ngƣời ta ứng dụng tích phân để tính diện tích của các
hình, việc tính diện tích theo cách này chúng ta phải biết hoặc xác định
đƣợc hàm số giới hạn hình cần tính [5].
Ví dụ 1: Diện tích hình phẳng giới hạn bởi một đƣờng cong.
Nếu hàm số y = f(x) liên tục trên đoạn [a, b] thì diện tích S của hình
phẳng giới hạn bởi đồ thị hàm số y = f(x), trục hoành và hai đƣờng thẳng
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
x = a, x = b là:
8
Ví dụ 2: Diện tích hình phẳng giới hạn bởi hai đƣờng cong và hai
đƣờng thẳng x = a, x = b.
Diện tích S của hình phẳng giới hạn bởi đồ thị các hàm số
liên tục trên đoạn [a, b] và hai đƣờng thẳng x = a, x = b, ta
Hình 1.2: Diện tích S của hình phẳng giới hạn bởi đồ thị các hàm số
liên tục trên đoạn [a, b] và hai đường thẳng x = a, x = b
có công thức sau:
Trong công thức trên ta chia thành các trƣờ ng hơ ̣p cu ̣ thể (Hình1.2):
Trƣờng hợp 1: Ta có công thức khai triển của S
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
nếu
9
Trƣờng hợp 2: Ta có công thức khai triển của S
nếu
Trƣờng hợp 3: Ta có công thức khai triển của S
(trong đó c là hoành độ giao điểm của hai đồ thị hai hàm số
)
Có một cách tiếp cận khác về cách tính diện tích với một đa giác khi
đa giác đó đƣợc đặt trong hệ tọa độ Oxy và biết tọa độ (x,y) n đỉnh của đa
giác trong hệ tọa độ Oxy theo tuần tự (x1,y1), (x2,y2), …, (xn,yn). Bài toán
tính diện tích cho đa giác có tọa độ của các đỉnh đã biết trƣớc và các đỉnh
đƣợc sắp xếp theo thứ tự cùng chiều quay của kim đồng hồ hoặc ngƣợc
chiều quay của kim đồng hồ trên mặt phẳng tọa độ đƣợc tính theo công
thức tổng quát nhƣ sau [9]:
(Nguồn: http://en.wikipedia.org/wiki/Shoelace_formula)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Công thức trên viết lại tƣơng đƣơng với công thức sau:
10
Để cụ thể tính ta triển khai tính diện tích thành các bƣớc sau:
Bƣớc 1: Tính T1
T1 = x1y2 + x2y3 + ... + xn-1yn + xny1
Bƣớc 2: Tính T2
T2 = x2y1 + x3y2 + ... + xnyn-1 + x1yn
Bƣớc 3: Tính S
S = |T1-T2|/2
1.2.2. Khái quát cách tính thể tích các hình cơ bản
Thể tích hay dung tích của một vật là lƣợng không gian mà vật ấy
chiếm. Thể tích có đơn vị đo là lập phƣơng của khoảng cách (khoảng cách
mũ 3). Trong hệ đo lƣờng quốc tế, nếu đơn vị đo của khoảng cách là cm thì đơn vị đo của thể tích là cm3, nếu đơn vị đo của khoảng cách là km thì đơn vị đo của thể tích là km3, nếu đơn vị đo của khoảng cách là m thì đơn vị đo của thể tích là m3 [6].
Đối với các khối hình cơ bản trong toán học chúng ta có công thức
tính thể tích theo những thông số cơ bản của hình nhƣ bảng tóm tắt sau [6],
V = Sh
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
[7]:
Thể tích hình trụ
Thể tích hình lăng trụ đều
V = Sh Thể tích hình lăng trụ tam giác
Thể tích hình tứ diện
Thể tích hình chóp cầu
Thể tích hình cầu
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
11
Thể tích hình nón
Thể tích hình nón cụt
Thể tích hình chóp đều
Thể tích hình chóp cụt đều
Hình 1.3: Công thứ c tính thể tích của một số khối hình đặc biê ̣t
12
Trong toán học ngƣời ta cũng có thể ứng dụng tích phân để tính thể
tích. Ví dụ việc tính thể tích vật thể tròn xoay: Hình phẳng giới hạn bởi đồ
thị hàm số y = f(x), trục hoành và hai đƣờng thẳng x = a, x = b, trong đó
(a < b). Quay hình phẳng (Hình 1.4) quanh trục hoành ta đƣợc một vật thể
tròn xoay [5].
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Thể tích của vật thể này đƣợc tính theo công thức:
Hình 1.4: Thể tích vật thể tròn xoay giớ i hạn bởi đồ thị hàm số y = f(x), trục hoành và hai đường thẳng x = a, x = b
13
Kết luâ ̣n chƣơng 1:
Trong chƣơng này học viên trình bày tổng quan về đề tài, khái quát
tóm tắt các cách tiếp cận và tổng hợp công thức để tính diện tích đối với
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
các hình đặc biệt, tính thể tích đối với các khối hình đặc biệt.
14
Chƣơng 2: MỘT SỐ THUẬT TOÁN TÍNH DIỆN TÍCH VÀ THỂ
TÍCH VẬT THỂ KHÔNG GIAN
Chƣơng này học viên trình bày ba thuật toán sau : Thuâ ̣t toán tính
diện tích đa giác theo to ̣a đô ̣ đỉnh , thuật toán tìm diện tích hình chữ nhật tối đại và thuật toán tính thể tích vùng nƣớc đo ̣ng . Mỗi bài toán thuâ ̣t toán ho ̣c viên phân tích , lấy ví du ̣ để làm rõ yêu cầu củ a bài toán , qua đó hình thành ý tƣởng giải thuật và xây dựng thuật toán .
2.1. Thuâ ̣t toán tính diện tích của đa giác theo tọa độ đỉnh
Bài toán
Cho đa giác N đỉnh theo tuần tự A1 A2 A3 ... AN trong mặt phẳng tọa độ
Oxy, với các đỉnh Ai(xi,yi) có to ̣a độ nguyên và các đỉnh đƣợc sắp xếp theo
thứ tự cùng chiều quay của kim đồng hồ hoặc ngƣợc chiều quay của kim
đồng hồ trên mặt phẳng tọa độ. Hãy tính diện tích đa giác trên.
Phân tích bài toá n
Nhƣ đã trình bày trong mục 1.2.1 về cách tính diện tích với những đa
giác khác nhau khi đa giác đó nằm trong hệ tọa độ Oxy. Nếu ta biết tọa độ
(x,y) n đỉnh của đa giác trong hệ tọa độ Oxy theo tuần tự (x1,y1), (x2,y2),
…, (xn,yn). Bài toán tính diện tích cho đa giác có tọa độ của các đỉnh đã
biết trƣớc và các đỉnh đƣợc sắp xếp theo thứ tự cùng chiều quay của kim
đồng hồ hoặc ngƣợc chiều quay của kim đồng hồ trên mặt phẳng tọa độ.
Khi đó chúng ta tính theo công thức tổng quát nhƣ sau [9]:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
(Nguồn: http://en.wikipedia.org/wiki/Shoelace_formula)
15
Công thức trên đƣợc viết lại tƣơng đƣơng với công thức sau:
Với cách tiếp cận theo hƣớng tin học, ta đang xây dựng mọi thứ dựa
trên điểm và tọa độ của điểm. Để cụ thể việc tính diện tích đa giác theo
công thức trên ta triển khai thành các bƣớc sau:
Bƣớc 1: Tính T1
T1 = x1y2 + x2y3 + ... + xn-1yn + xny1
Bƣớc 2: Tính T2
T2 = x2y1 + x3y2 + ... + xnyn-1 + x1yn
Bƣớc 3: Tính S
S = |T1-T2|/2
Sau đây ta xét một số ví dụ minh họa:
Ví dụ 1: Tứ giác ABCD là hình chữ nhật với tọa độ các đỉnh nhƣ sau
(Hình 2.1): A(4,4), B(12,4), C(12,8), D(4,8)
Áp dụng các bƣớc trên ta lần lƣợt tính đƣợc
T1 = xAyB + xByC + xCyD + xDyA
=4 x 4 + 12 x 8 + 12 x 8 + 4 x 4
= 16 + 96 + 96 + 16 = 224
T2 = xByA + xCyB + xDyC + xAyD
= 12 x 4 + 12 x 4 + 4 x 8 + 4 x 8
= 48 + 48 + 32 + 32 = 160
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
S = |T1-T2|/2 = |224-160|/2 = 64/2 = 32
D
16
y
12
10
D C 8
6
4 A B
2
Hình 2.1: Hình chữ nhật ABCD trong mặt phẳng tọa độ Oxy
0 4 x 10 14 12 8 6 2 16
Cũng dễ dàng nhận thấy vùng diện tích trên chính là vùng diện tích của
hình chữ nhật có cạnh dài là 8 đơn vị và cạnh nhỏ là 4 đơn vị, nhƣ vậy diện
tích của hình chữ nhật là 8 x 4 = 32 ứng với diện tích của 32 ô vuông nhận
đƣợc.
Ví dụ 2: Có ngũ giác ABCDE, đỉnh C lõm với tọa độ các đỉnh nhƣ sau
(Hình 2.2): A(4,4), B(12,4),C(10,6), D(12,8), E(4,8)
Từ các cặp tọa độ trên áp dụng công thức và các bƣớc ta lần lƣợt tính
T1, T2 và S nhƣ sau:
T1 = xAyB + xByC + xCyD + xDyE + xEyA
= 4 x 4 + 12 x 6 + 10 x 8 + 12 x 8 + 4 x 4
= 16 + 72 + 80 + 96 + 16 = 280
T2 = xByA + xCyB + xDyC + xEyD + xAyE
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
= 12 x 4 + 10 x 4 + 12 x 6 + 8 x 4 + 4 x 4
17
= 48 + 40 + 72 + 32 + 32 = 224
S = |T1-T2|/2 = |280-224|/2 = 56/2 = 28
y
12
10
D E 8
6 C
4 A B
2
Hình 2.2: Ngũ giác lõm ABCDE trong mặt phẳng tọa độ Oxy
x 0 4 2 6 8 10 12 14 16
Ở ví dụ 2 công thức đƣợc tính với đa giác lõm, dễ nhận thấy diện tích
của đa giác này bằng diện tích của hình chữ nhật trong ví dụ 1 trừ đi 4 đơn
vị ô vuông theo hình minh họa và bằng 28 đơn vị ô vuông.
Ví dụ 3: Với ngũ giác ABCDE, đỉnh C lồi có tọa độ các đỉnh nhƣ sau
(Hình 2.3):
A(4,4), B(12,4), C(14,6), D(12,8), E(4,8)
Với ví dụ này công thức đƣợc áp dụng là đa giác lồi. Áp dụng công
thức và các bƣớc ta tính đƣợc :
T1 = xAyB + xByC + xCyD + xDyE + xEyA
= 4 x 4 + 12 x 6 + 14 x 8 + 12 x 8 + 4 x 4
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
= 16 + 72 + 112 + 96 + 16 = 312
18
T2 = xByA + xCyB + xDyC + xEyD + xAyE
= 12 x 4 + 14 x 4 + 12 x 6 + 4 x 8 + 8 x 4
= 48 + 56 + 72 + 32 + 32 = 240
= |T1-T2|/2 = |312-240|/2 = 72/2 = 36 S
y
12
10 D E 8
C 6
4 A B
2
Hình 2.3: Ngũ giác lồi ABCDE trong mặt phẳng tọa độ Oxy
x 0 4 2 6 8 10 12 14 16
Dễ nhận thấy diện tích của đa giác này bằng diện tích của hình chữ
nhật trong ví dụ 1 cộng thêm 4 đơn vị ô vuông theo hình minh họa và bằng
36 đơn vị ô vuông.
Ví dụ 4: Tứ giác ABCD là một hình thang với tọa độ các đỉnh nhƣ sau
(Hình 2.4): A(4,4), B (12,4), C (11,8), D (7,8)
Áp dụng các bƣớc trên ta có:
T1 = xAyB + xByC + xCyD + xDyA
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
= 4 x 4 + 12 x 8 + 11 x 8 + 8 x 4
19
= 16 + 96 + 88 + 28 = 228
T2 = xByA+ xCyB+ xDyC+ xAyD
= 12 x 4 + 11 x 4 + 7 x 8 + 4 x 8
= 48 + 44 + 56 + 32 = 180
S = |T1-T2|/2 = |228-180|/2 = 48/2 = 24
y
12
10
D C 8
6
4 A B
2
Hình 2.4: Hình thang ABCD trong mặt phẳng tọa độ Oxy
x 0 4 2 6 8 10 12 14 16
Ở ví dụ này chính bài toán tính diện hình thang có đáy nhỏ là 4 đơn vị,
đáy lớn là 8 đơn vị và chiều cao là 4 đơn vị áp dụng công thức có kết quả
sau:
S = ((4+8) * 4)/2 = 48/2 = 24
Nhƣ vậy kết quả tính đƣợc cũng khớp với cách tính ở trên.
Ví dụ 5: Xét một đa giác vừa có tính chất lồi, vừa có tính chất lõm với
tọa độ các đỉnh nhƣ sau (Hình 2.5):
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
A(4,4), B(12,4), C(10,6), D(12,8), E(8,8), F(6,10), G(4,8)
20
Áp dụng công thức và các bƣớc ta tính đƣợc:
T1 = xAyB + xByC + xCyD + xDyE + xEyF + xFyG + xGyA
= 4 x 4 + 12 x 6 + 10 x 8 + 12 x 8 + 8 x 10 + 6 x 8 + 4 x 4
= 16 + 72 + 80 + 96 + 80 + 48 + 16 = 408
T2 = xByA + xCyB + xDyC + xEyD + xFyE + xGyF + xAyG
= 12 x 4 + 10 x 4 + 12 x 6 + 8 x 8 + 6 x 8 + 4 x 10 + 4 x 8
= 48 + 40 + 72 + 64 + 48 + 40 + 32 = 344
S = |T1-T2|/2 = |408 - 344|/2 = 64/2 = 32
y
12
F 10
E G D 8
6 C
4 B A
2
x 0 4 2 6 8 10 12 14 16
Hình 2.5: Đa giá c lồi, lõm trong mặt phẳng tọa độ Oxy
Ở hình trên nếu lấy phần lồi bù cho phần lõm thì ta thu đƣợc diện tích
của hình chính là diện tích của hình chữ nhật có chiều dài là 8 đơn vị và
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
chiều rộng là 4 đơn vị nhƣ vậy S = 8 x 4 = 32 đơn vị ô vuông khớ p vớ i kết quả tính ở trên.
21
Qua một số ví dụ nhằm thể hiện về cách tính diện tích của đa giác theo
công tổng quát đã nêu ở trên. Với những đa giác có nhiều đỉnh, tọa độ các
đỉnh không đơn giản chỉ là các số chẵn thì việc tính toán không đơn giản
chỉ là nhìn nhận qua hình và tính toán đơn giản nhƣ minh họa mà đòi hỏi
việc tính toán ở nhiều phép tính toán hoặc tính toán với số lƣợng lớn, lúc
đó đòi hỏi rất cần từ công cụ là máy tính với việc lập trình bằng một
chƣơng trình cụ thể mà Input chính là tọa độ của các đỉnh của đa giác trong
mặt phẳng tọa độ Oxy còn Output là diện tích của đa giác đó.
Ta đƣa bài toán trên vớ i dƣ̃ liê ̣u vào và ra nhƣ sau :
- Input: Cho trong tê ̣p DAGIAC.INP gồm ít nhất 2 dòng
+ Dòng 1: Chứa số nguyên dƣơng N tƣơng ứng với N đỉnh của đa giác
+ Dòng 2 và các dòng tiếp theo: Chứa 2 x N số nguyên tƣơng ứng với
x1y1 x2y2 ... xNyN là toạ độ các đỉnh của đa giác. Mỗi số ghi cách nhau một
dấu cách.
- Output: Ghi kết quả là diện tích đa giác ra file DAGIAC.OUT
Ví dụ:
DAGIAC.INP DAGIAC.OUT
4 32
4 4 12 4 12 8 4 8
Ý tưở ng thuật toá n [2], [3], [4], [8].
Để giải bài toán trên theo dƣ̃ liê ̣u vào nhƣ ví du ̣ ta l ƣu toạ độ các đỉnh đa giác vào các mảng: Vì mỗi đỉnh có 2 giá trị ứng với 2 tọa độ x,y nên để
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
đọc dữ liệu từ tệp DAGIAC.INP các cặp tọa độ ta dùng 2 mảng một chiều.
22
Mảng thứ nhất (Mảng X) lƣu các tọa độ xi, i = 1 .. N
Mảng thứ hai (Mảng Y) lƣu các tọa độ yi, i = 1 .. N
Sau đó tính diện tích đa giác theo các bƣớ c:
Bƣớc 1: Tính T1
T1 = x1y2 + x2y3 + ... + xN-1yN + xNy1
Ban đầu gán T1 = xNy1 chính là T1 = X[N] * Y[1]
Sử dụng vòng lặp cho i chạy từ 1 đến N-1 tính
T1=T1+ x1y2 + x2y3 +.... + xN-1yN tƣơng đƣơng với công thức trong
vòng lặp nhƣ sau : T1 = T1 + X[i] * Y[i+1]
Bƣớc 2: Tính T2
T2 = x2y1 + x3y2 + ... + xNyN-1 + x1yN
Ban đầu gán T2 = x1yN chính là T2 = X[1] * Y[N]
Sử dụng vòng lặp cho i chạy từ 1 đến N-1 tính
T2 = T2 + x2y1 + x3y2 + ... + xNyN-1 tƣơng đƣơng với công thức trong
vòng lặp nhƣ sau : T2=T2+ X[i+1] * Y[i]
Bƣớc 3: Tính S
S = |T1-T2|/2
Nội dung tính T1 và T2 ở trên là sử dụng hai vòng lặp For riêng biệt
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
tuy nhiên cả hai vòng lặp tách biệt có biến đếm i chạy từ 1 đến N-1 vì vậy
23
khi mô tả thuật toán và trong lập trình ta có thể dùng gộp bằng một vòng lặp For.
Thuật toán
Algorithm DT_ DAGIAC
Chức năng: Tính diện tích đa giác theo to ̣a đô ̣ đỉnh. Input: Số nguyên dƣơng N tƣơng ứng với N đỉnh của đa giác và 2 x N
số nguyên tƣơng ứng với x1y1 x2y2 ... xNyN là toạ độ các đỉnh của đa giác.
Output: Diện tích (S) của đa giác.
Method
1. Đo ̣c dữ liệu tƣ̀ tê ̣p DAGIAC.INP
1.1 Đọc giá trị số nguyên dòng 1 vào biến N
1.2 Lƣu tọa độ các đỉnh đa giác vào các mảng: Vì mỗi đỉnh có 2 giá
trị ứng với 2 tọa độ x,y nên để đọc dữ liệu từ tệp DAGIAC.INP
các cặp tọa độ ta dùng 2 mảng một chiều.
Mảng thứ nhất (Mảng X) lƣu các tọa độ xi, i = 1 .. N
Mảng thứ hai (Mảng Y) lƣu các tọa độ yi, i = 1 .. N
2. Khởi tri ̣ cho T1, T2:
T1:=x[n]*y[1];
T2:=y[n]*x[1];
3. Tính T1 và T2:
For i:=1 to n-1 do
begin
T1:= T1+x[i]*y[i+1];
T2:= T2+y[i]*x[i+1];
end;
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
4. Tính S:
24
S:=ABS(T1-T2)/2;
5. Ghi kết quả S ra tệp DAGIAC.OUT
Nhập: Số lượng điểm N; Tọa độ X[1..N]; Tọa độ Y[1..N];
T1:=x[n]*y[1];
T2:=y[n]*x[1];
i:=1;
T
i > N-1
F
T1:= T1+x[i]*y[i+1];
T2:= T2+y[i]*x[i+1];
S:=ABS(T1-T2)/2;
i: = i + 1;
Đưa ra kết quả S
Các bƣớc thuật toán trên có thể đƣợc mô tả bằng sơ đồ sau:
Độ phức tạp tính toán
Trong tệp DAGIAC.INP chứa 2 x N phần tử, khi xử lí tính toán
đƣợc dựa trên 2 mảng X, Y mỗi mảng gồm N phần tử. Thuật toán có tối đa
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
N phép duyệt khi cho i chạy từ 1 tới N-1 nhƣ vậy có tối đa N phép duyệt.
25
Vâ ̣y độ phức tạp tính toán là O(n).
2.2. Thuật toán tìm diện tích hình chữ nhật tối đại
Bài toán
Cho một ma trận biểu diễn bằng một mảng hai chiều kích thƣớc N x M
ô và chỉ chứa các kí tự 0 và 1. Tìm hình chữ nhật chứa toàn kí tự 1 và có
diện tích lớn nhất (gọi là hình chữ nhật tối đại) [2].
Phân tích bài toán
Tƣ̀ yêu cầu củ a bài toán ta xét mô ̣t số ví dụ sau:
Ví dụ 1: Cho ma trâ ̣n 7 x 8 (Hình 2.6)
Hình 2.6: VD1 - Ma trận chứa các kí tự 0 và 1
0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0
1 có
Vớ i ma trâ ̣n t rên ta tìm đƣơ ̣c hình chƣ̃ nhâ ̣t tối đa ̣i chƣ́ a các kí tƣ̣ diện tích là 10 ô vuông và có toạ độ đỉnh trên - trái là (Cô ̣t 2, dòng 4) và đỉnh dƣớ i – phải là (cô ̣t 6, dòng 5)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0
26
0 0 1 0 0 1 1 0
Ví dụ 2:
Dƣ̣a vào ma trâ ̣n trên ta thay đổi giá tri ̣ 1 bằng giá tri ̣ 0 tại cột 4, dòng 4
(Hình 2.7).
Hình 2.7: VD2 - Ma trận chứa các kí tự 0 và 1
0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0
Lúc này ma trâ ̣n trên ta tìm đƣơ ̣c hình chƣ̃ nhâ ̣t tối đa ̣i chƣ́ a các kí tƣ̣ 1 có diện tích là 8 ô vuông và có toạ độ đỉnh trên - trái là (Cô ̣t 2, dòng 2) và đỉnh dƣớ i – phải là (cô ̣t 3, dòng 5)
0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0
Ví dụ 3:
Tƣ̀ ma trâ ̣n củ a ví du ̣ 2 ta thay đổi giá tri ̣ 1 bằng giá tri ̣ 0 tại cột 3, dòng
4 (Hình 2.8)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0
27
Hình 2.8: VD3 - Ma trận chứa các kí tự 0 và 1
0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0
1
Khi đó ma trâ ̣n trên ta tìm đƣơ ̣c hình chƣ̃ nhâ ̣t tối đa ̣i chƣ́ a các kí tƣ̣ có diện tích là 7 ô vuông và có toạ độ đỉnh trên - trái là (Cô ̣t 1, dòng 5) và đỉnh dƣớ i – phải là (cô ̣t 7, dòng 5).
0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0
Tƣ̀ yêu cầu củ a bài toán và qua các ví dụ minh ho ̣a ta đƣa bài toán trên
vớ i dƣ̃ liê ̣u vào và ra nhƣ s au :
- Input: Tệp văn bản CNMAX.INP:
+ Dòng đầu tiên chƣ́ a 2 số tự nhiên N và M,
+ N dòng sau, mỗi dòng chƣ́ a M số 0/1.
3 ≤ M ≤ 70
3 ≤ N ≤ 10000
- Output: Tệp văn bản CNMAX.OUT:
+ Dòng đầu tiên: Diện tích của hình chữ nhật tối đại chứa toàn kí tự 1.
+ Dòng thứ hai: Tọa độ cô ̣t và dòng của đỉnh trên - trái.
+ Dòng thứ ba: Toạ độ cô ̣t và dòng của đỉnh dƣớ i - phải. Ví dụ: Với ma trận 7 x 8 chứa dữ liệu nhƣ hình 2.6 thì hình chữ nhật tối
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
đại có diện tích là 10 ô vuông, có toạ độ đỉnh trên - trái là (Cô ̣t 2, dòng 4) và
28
đỉnh dƣớ i – phải là (cô ̣t 6, dòng 5)
CNMAX.INP CNMAX.OUT
10 2 4 6 5
7 8 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0
Ý tưở ng thuật toá n [2], [3], [4], [8]
Để tìm đƣợc hình chữ nhật toàn 1 có diện tích lớn nhất, ta sẽ khởi tạo
các mảng sau:
- Mảng H : H[i,j]: số ô 1 liên tiếp từ ô [i,j] trở lên = chiều rộng lớn
nhất của HCN đáy dƣới qua ô [i,j].
- Mảng L : L[i,j]: số cột toàn 1 liên tiếp có chiều cao lớn hơn hoặc
bằng H[i,j] tính từ cột j sang bên trái.
- Mảng R : R[i,j]: số cột toàn 1 liên tiếp có chiều cao lớn hơn hoặc
bằng H[i,j] tính từ cột j sang bên phải.
Từ đó diện tích hình chữ nhật toàn 1 mà chiều rộng = H[i,j] và đáy
dƣới ở hàng i là H*(L+R-1)
Vậy kết quả bài toán tìm diện tích hình chữ nhật lớ n nhất toàn 1 là
MAX(H*(L+R-1))
* Xét theo ví dụ trên:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
1 1 1 1 1 1 1
29
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
- Tính mảng H : H[i,j] = 0 nếu A[i,j] = 0
Và = H[i-1,j]+1 nếu A[i,j]=1
0 0 0 0 1 0 0 1 0 1 1 0 2 1 0 2 0 2 2 0 0 2 0 3 0 3 3 1 1 3 0 4 1 4 4 2 2 4 1 0 0 0 5 0 0 0 0 0 0 0 6 0 0 1 1 0
- Tính mảng L : Duyê ̣t tất cả nhƣ̃ng phần tƣ̉ đƣ́ ng trƣớ c ô A [i,j] đang
xét (tính theo chiều từ trái sang phải ), nếu thỏa mãn điều kiê ̣n liên
tiếp = 1 và có độ cao >= H[i,j] thì L[i,j]=L[i,j-1]+1.
1 1 2 1 2 1 2 1 1 2 3 4 1 1 1 2 3 4 1 7 1 2 1 1 1 1 1 1
- Tính mảng R : Duyê ̣t tất cả nhƣ̃ng phần tƣ̉ đƣ́ ng sau ô A [i,j] đang xét
(tính theo chiều từ phải qua trái ), nếu thỏa mãn điều kiê ̣n liên tiếp
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
=1 và có chiều cao >= H[i,j] thì R[i,j]=R[i,j+1]+1
30
1 1 1 2 1 2 1 1 2 1 3 2 1 7 2 1 3 2 1 1 2 1 1 1 1 1 1 1
Xét ô đƣơ ̣c đánh dấu, ta có: H = 2; L = 4; R = 2 Vậy diện tích hình chữ nhật chứa toàn 1 là: 2 x (4 +2 – 1) = 10 (đơn
vị ô vuông)
Thuật toán
Algorithm CNMAX
Chức năng: Tìm diện tích hình chữ nhật tối đại chƣ́ a toàn kí tƣ̣ 1.
Input: Ma trận biểu diễn bằng một mảng hai chiều kích thƣớc N x M và
chỉ chứa các kí tự 0 và 1.
Output: Tìm hình chữ nhật chứa toàn kí tự 1 và có diện tích lớn nhất
(gọi là hình chữ nhật tối đại).
Method
1. Đo ̣c dƣ̃ liê ̣u tƣ̀ tê ̣p CNMAX.INP
1.1 Đo ̣c 2 số nguyên ở dòng đầu của tệp vào 2 biến tƣơng ƣ́ ng N ,
M
1.2 Đọc các số nguyên tƣơng ứng vào mảng A [i,j]
for i:=1 to n do
begin
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
for j:=1 to m do read(fi,a[i,j]);
31
end;
2. Tính độ dài các cạnh:
2.1 Tính chiều cao hay chiều rô ̣ng củ a HCN thông qua mảng H
for i:=1 to n do
for j:=1 to m do
if a[i,j]=0 then h[i,j]:=0
else h[i,j]:=h[i-1,j]+1;
2.2 Tính mảng L duyệt từ trái qua phải .
for i:= 1 to n do
for j:=1 to m do
if a[i,j]=0 then l[i,j]:=0
else
begin
d:=0;
for k:=1 to j do
if (a[i,k]=1) and (h[i,k]>=h[i,j]) then inc(d)
else d:=0;
l[i,j]:=d;
end;
2.2 Tính mảng R duyê ̣t tƣ̀ phải qua trái.
for i:=1 to n do
for j:=m downto 1 do
if a[i,j]=0 then l[i,j]:=0
else
begin
d:=0;
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
for k:=m downto j do
32
if (a[i,k]=1) and (h[i,k]>=h[i,j]) then inc(d)
else d:=0;
r[i,j]:=d;
end;
3. Tính các diện tích t ạo bởi các hình chữ nhật chƣ́ a 1 và tìm diện tích
lớ n nhất chƣ́ a toàn 1.
3.1 Khở i ta ̣o
Smax:=0;
3.2 Tính diện tích các hì nh chƣ̃ nhâ ̣t; So sánh diê ̣n tích và gán giá tri ̣ diê ̣n tích lớ n nhất tìm đƣơ ̣c vào biến S max; Xác định tọa độ các đỉnh trên – trái và dƣới – phải của HCN theo cột, dòng
for i:=1 to n do
for j:=1 to m do
begin
S:=h[i,j]*(l[i,j]+r[i,j]-1);
if S> smax then
begin
smax:=s;
yt:=i+1-h[i,j];
xtr:=j+1-l[i,j];
yd:=i;
xph:=xtr+(l[i,j]+r[i,j]-1)-1;
end;
end;
4. Đƣa ra kết quả gồm HCN tối đa ̣i chƣ́ a toàn1, tọa độ đỉnh trên – trái và đỉnh dƣới – phải. (Ghi kết quả ra tệp CNMAX.OUT)
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Độ phức tạp tính toán
33
Tệp CNMAX.INP chứa n dòng, mỗi dòng chứa m kí tự. Khi xử lí
để tính mảng H ta duyệt bằng hai vòng lặp for lồng nhau . Để tính mảng L và R ta duyệt bằng ba vòng lặp trong đó duyệt số phần tử m trên mỗi hàng
là 2 lần. Viê ̣c tính giá trị của ba mảng H , L, R là đô ̣c lâ ̣p nên đô ̣ phƣ́ c ta ̣p là: (n x m ) + ( n x m x m ) + ( n x m x m ). Khi n, m là rất lớ n thì đô ̣ phƣ́ c tạp là: n x m x m
Vậy độ phức tạp tính toán là O(n x m2).
2.3. Thuật toán tính thể tích vùng nƣớc đo ̣ng
Bài toán
Trên một mô hình có hình chữ nhật chia lƣới kích thƣớc n x m đơn vị
tại một số ô của bảng gắn một cột nhựa vuông cạnh đáy 1 đơn vị, chiều
cao là một số nguyên. Các cột kề nhau cũng đƣợc gắn keo giữa hai mặt và
hai cạnh tiếp giáp. Sau đó nhúng mô hình ngập vào nƣớc rồi cẩn thận nhấc
lên. Tính thể tích của khối nƣớc đọng trong mô hình.
Phân tích bài toán
Để làm rõ yêu cầu củ a bài toán ta tìm hiểu mô ̣t số ví du ̣ vớ i các cô ̣t vuông ca ̣nh đáy 1 đơn vi ̣. Số cô ̣t và đô ̣ cao củ a các cô ̣t đƣơ ̣c thể hiê ̣ n bằng
ma trâ ̣n m x n , phần tử thứ j trên dòng i trong số m dòng tiếp theo là chiều
cao của cột đặt tại ô (i, j).
Ví dụ 1: Cho ma trâ ̣n 4 x 5 thể hiê ̣n số cô ̣t và đô ̣ cao củ a các cô ̣t nhƣ sau
(Hình 2.9):
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
3 2 1 1 2
34
Hình 2.9: VD1 - Ma trận và cột thể hiê ̣n độ cao của cá c cột vuông cạnh 1 đơn vi ̣.
4 3 2 3 3 5 4 3 4 5 5 5 4 5 4
Hình minh họa trên các cột chƣa đƣợc ghép thành một khối liền nhau ,
theo bài toán ta ghép và gắn thành mô ̣t khối nhƣ sau:
Nếu nhú ng mô hình trên vào nƣớ c và nhấc lên thì lƣơ ̣ng nƣớ c đo ̣ng trong mô hình sẽ bằng 0 vì các cột trên ghép với nhau nhƣng không tạo ra ô nào chứa nƣớc đọng nhƣ hình minh ho ̣a .
Ví dụ 2: Cho ma trâ ̣n 4 x 5 thể hiê ̣n số cô ̣t và đô ̣ cao củ a các cô ̣t nhƣ sau
(Hình 2.10):
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
4 4 3 4 3 5 5 5 5 4 5 4 4 4 5 5 5 5 5 5
Hình 2.10: VD2 - Ma trận và cột thể hiê ̣n độ cao của cá c cột vuông cạnh 1 đơn vi ̣.
35
Ta ghép và gắn các cột thành một khối liền nhau nhƣ sau:
dễ nhâ ̣n thấy các cô ̣t Nếu nhú ng mô hình trên vào nƣớ c và nhấc lên
thuô ̣c hàng 1 nƣớ c sẽ không đo ̣ng , các cột thuộc hàng 2, 3, 4 sẽ tạo ra 3 ô chƣ́ a nƣớ c đo ̣ng và có đô ̣ cao bằng 1 tại lớp trên cù ng nhƣ vâ ̣y tổng ô chƣ́ a nƣớ c đo ̣ng sẽ bằng 3.
Ví dụ 3: Ma trâ ̣n 4 x 5 thể hiê ̣n số cô ̣t và đô ̣ cao củ a các cô ̣t nhƣ sau
(Hình 2.11):
Hình 2.11: VD3 - Ma trận và cột thể hiê ̣n độ cao của cá c cột vuông cạnh 1 đơn vi ̣.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
5 5 4 5 5 5 4 0 3 0 5 0 5 2 5 5 5 4 5 5
36
Ta ghép và gắn các cột thành một khối liền nhau nhƣ sau:
Đem mô hình trên nhú ng nƣớ c và nhấc lên , dễ thấy nƣớ c sẽ đo ̣ng tại vị trí các cột vị trí (2,3) là 3 ô, nƣớc đọng tại vị trí cột (3,2) là 4 ô, nƣớ c đo ̣ng tại vị trí cột (3,4) là 1 ô. Nhƣ vâ ̣y tổng nƣớ c đo ̣ng trong mô hình trên là 8.
Tƣ̀ yêu cầu củ a bài toán và qua các ví du ̣ minh ho ̣a t a đƣa bài toán trên
vớ i dƣ̃ liê ̣u vào và ra n hƣ sau:
- Input: Tệp văn bản THETICH.INP
+ Dòng đầu chƣ́ a 2 số nguyên dƣơng m và n. (3 ≤ M, N ≤ 100)
+ Phần tử thứ j trên dòng i trong số m dòng tiếp theo là chiều
cao của cột đặt tại ô (i, j).
- Out put: Tệp văn bản THETICH.OUT
Thể tích nƣớc đọng trong mô hình
Ví dụ:
THETICH.INP THETICH.OUT
8
4 5 5 5 4 5 5 5 4 0 3 0 5 0 5 2 5 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
37
5 5 4 5 5
Ý tưở ng thuật toá n [2], [3], [4], [8]
Gọi a là tấm bảng nền mô hình với kích thƣớc mn và h(i,j) là chiều
cao của cột nhựa vuông đặt trên ô (i,j). Thoạt tiên ta giả sử chiều cao tối đa
của các cột là 1, nhƣ vậy các ô trên nền nhà chỉ chứa các giá trị 0 hoặc 1.
Nền tầng 1 với các ô đặc mang giá trị 1, ô chứa nƣớc đọng màu trắng
(0) và ô thoát nƣớc màu xám (0).
Ô thoát nƣớc
1 1 1 1 1 1 1
0 1 1 0 0 0 0 0
1 1 1 1 0 1 1
1 0 1 1 0 1 1 0 Ô nƣớc đọng
1 0 1 1 1 1 1
.
1 0 1 0 0 1 1 Ô đặc 1 1 1 1 1 1 1 1
Ô mang giá trị 0 chính là mặt sàn, còn ô mang giá trị 1 chính là cột.
Bây giờ bạn thử rót nƣớc vào mô hình đơn giản này cho ngập các ô và
quan sát điều gì sẽ xảy ra. Dễ thấy là chỉ có các ô trống bị giam tại giữa mô
hình là còn chứa nƣớc. Có 5 ô trống bị giam nên thể tích nƣớc đọng sẽ là
5. Các ô trống (mang giá trị 0) liên thông cạnh với một ô trống trên biên sẽ
tạo thành một cống thoát nƣởc ra ngoài mô hình. Nhận xét này cho ta thuật
toán tính lƣợng nƣớc đọng tại tầng nền (tầng 0) của mô hình nhƣ sau:
Duỵệt đƣờng biên, nếu gặp ô trống (trên biên và chứa trị 0) thì gọi thủ
tục loang đánh dấu các ô này bằng giá trị 1.
Duyệt các ô lọt trong mô hình, đếm các ô trống (chứa giá trị 0) và đồng
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
thời đánh dấu các ô này bằng giá trị 1. Đó là thể tich nƣớc đọng.
38
Tiếp theo, sau khi đã duyệt và tính lƣợng nƣớc đọng tại tầng nền
(tầng 0), ta dễ dàng suy ra cách tính lƣợng nƣớc đọng tại tầng 1 nếu nhƣ
coi các ô trống đã duyệt tại tầng 0 đã đƣợc lấp bằng các khối nhựa chiều
cao 1. Ta gọi phƣơng thức này là đóng băng các ô đã xử lí. Tổng quát, tại
tầng h ta thực hiện thủ tục tƣơng tự nhƣ tại tầng nền với chút điều chỉnh là
thay giá trị đánh dấu bằng h+1 thay vì bằng 1. Gọi chiều cao tối đa của
các cột là hmax, cho h biến thiên từ 0 đến hmax1 ta tính đƣợc tổng khối
nƣớc đọng của mô hình.
Xét theo ví dụ trên ta có:
5 5 4 5 5 5 4 0 3 0 5 0 5 2 5 5 5 4 5 5
Loang lớp 0:
Duyệt các ô biên, ta tìm đƣợc ô [2,5] có chiều cao = 0
5 5 4 5 5 5 4 0 3 0 5 0 5 2 5 5 5 4 5 5
Loang từ ô [2,5], các ô cạnh bên đều cao hơn.
5 5 4 5 5 5 4 0 3 0 5 0 5 2 5 5 5 4 5 5
Số ô còn lại trong bảng có chiều cao <1 là thể tích nƣớc đọng tầng 1:
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
(ô đƣơ ̣c đánh dấu)
39
5 5 4 5 5 5 4 0 3 0 5 0 5 2 5 5 5 4 5 5
V0 = 2
Giờ ta lấp các ô tầng 0, ta đƣợc:
5 5 4 5 5 5 4 1 3 1 5 1 5 2 5 5 5 4 5 5
Loang lớp 1:
Duyệt các ô biên, ta tìm đƣợc ô [2,5] có chiều cao =1
5 5 4 5 5 5 4 1 3 1 5 1 5 2 5 5 5 4 5 5
Loang từ ô [2,5]:
5 5 4 5 5 5 4 1 3 1 5 1 5 2 5 5 5 4 5 5
Các ô nƣớc đọng: (ô đƣơ ̣c đánh dấu)
5 5 4 5 5 5 4 1 3 1 5 1 5 2 5 5 5 4 5 5
V1 = 2
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Giờ lấp các ô tầng 1, ta đƣợc:
40
5 5 4 5 5 5 4 2 3 2 5 2 5 2 5 5 5 4 5 5
Loang lớp 2:
Duyệt đƣờng biên, đƣợc ô [2,5]:
5 5 4 5 5 5 4 2 3 2 5 2 5 2 5 5 5 4 5 5
Loang từ ô [2,5] và tìm ra các ô nƣớc đọng:
5 5 4 5 5 5 4 2 3 2 5 2 5 2 5 5 5 4 5 5
V2 = 3
Lấp đầy các ô tầng 2:
5 5 4 5 5 5 4 3 3 3 5 3 5 3 5 5 5 4 5 5
Loang lớp 3:
Duyệt biên ta đƣợc ô [2,5]:
5 5 4 5 5 5 4 3 3 3 5 3 5 3 5 5 5 4 5 5
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
Loang từ ô [2,5] và tìm ra ô nƣớc đọng:
41
5 5 4 5 5 5 4 3 3 3 5 3 5 3 5 5 5 4 5 5
V3 = 1
Lấp đầy các ô tầng 3:
5 5 4 5 5 5 4 4 4 4 5 4 5 4 5 5 5 4 5 5
Loang tầng 4:
Duyệt biên ta đƣợc các ô chiều cao =4: [1,3] [2,5] [4,3]
5 5 4 5 5 5 4 4 4 4 5 4 5 4 5 5 5 4 5 5
Loang từ các ô đó:
5 5 4 5 5 5 4 4 4 4 5 4 5 4 5 5 5 4 5 5
Không có ô nào nƣớc đọng
V4 = 0
Vâ ̣y thể tích nƣớ c các ô đo ̣ng là : V = V1 + V2 + V3 + V4 = 8
Để giảm bớt phức tạp cho bài toán, ta bỏ qua phần lấp đầy các ô ở
mỗi tầng bằng cách: Khi xét tầng H, ta sẽ tìm các ô ở biên có chiều cao nhỏ
hơn hoặc bằng H, nhƣ vậy ta ngầm coi rằng các ô này đƣợc lấp đầy từ
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
trƣớc, khi loang ta cũng loang ra các ô chiều cao <=H.
42
Thuật toán
Algorithm THETICH
Chức năng: Tính thể tích (dung tích) nƣớc đo ̣ng.
Input: Ma trận độ cao h kích thƣớc m × n chia theo lƣới vuông đơn vị
i = 1,2, …,m xác định chỉ số hàng; chỉ số j = 1, 2, …, n xác định chỉ số cô ̣t.
h[i,j] là những số nguyên là chiều cao củ a cô ̣t ta ̣i ô (i,j)
Output: Thể tích nƣớ c bị giam (Thể tích nƣớ c đo ̣ng).
Method
1. Đo ̣c dƣ̃ liê ̣u tƣ̀ tê ̣p THETICH .INP
1.1 Đo ̣c dòng đầu 2 số nguyên tƣơng ƣ́ ng vào 2 biến m và
1.2 Khở i ta ̣o đô ̣ cao hmax và hmin .
hmin:=1000000;
hmax:=0;
1.3 Đo ̣c các số nguyên tƣơng ứng vào mảng A [i,j]; Xác định độ cao
nhỏ nhất và lớn nhất có trong ma trận
for i:=1 to m do
for j:=1 to n do
begin
read(fi,a[i,j]);
hmin:=min(hmin,a[i,j]);
hmax:=max(hmax,a[i,j]);
end;
2. Thủ tục Loang:
Ta dùng đệ quy Loang(x,y):
Từ ô [x,y] ta loang sang 4 phía nếu các ô đó có chiều cao <=H, loang
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
tới ô nào thì đánh dấu đã Loang vào ô đó để tránh Loang lại lặp vô hạn.
43
Procedure LOANG(x,y: longint);
begin
free[x,y]:=count;
if (x>1) and (free[x-1,y] LOANG(x-1,y); if (y>1) and (free[x,y-1] LOANG(x,y-1); if (x LOANG(x+1,y); if (y LOANG(x,y+1); end; Ở đây dùng mảng Free[x,y] để đánh dấu, Free=count là đã Loang, Free 3. Duyệt lần lƣợt từ chiều cao Hmin -> Hmax-1, với mỗi chiều cao ta tìm ô biên thỏa mãn và gọi thủ tục Loang(x,y), sau khi Loang hết ô biên ta đếm số ô chiều cao <=H mà chƣa bị Loang tới (tức là Free chính là thể tích nƣớc đọng. res:=0; for h:=hmin to hmax-1 do begin inc(count); // Các ô có chiều cao for i:=1 to m do begin if (a[i,1]<=h)and(free[i,1] Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn if (a[i,n]<=h)and(free[i,n] 44 end; for j:=2 to n-1 do begin if (a[1,j]<=h)and(free[1,j] if (a[m,j]<=h)and(free[m,j] end; // Loang xong, tính tổng thể tích nƣớc đọng đến thời diểm đang xét . for i:=1 to m do for j:=1 to n do if (free[i,j] end; ọng (Ghi kết quả ra tê ̣p 4. Đƣa ra kết quả thể tích nƣớ c đ THETICH.OUT). Độ phức tạp tính toán Ta có ma trận độ cao h kích thƣớc m × n chia theo lƣới vuông đơn vị, hmax là chiều cao lớn nhất, hmin là chiều cao nhỏ nhất. Tại mỗi lớ p chỉ đếm những ô bị giam tại lớp đó. Bƣớc 3 của thuật toán THETICH thực hiện hmax- hmin lần. Mỗi lần lần thủ tục duyệt ma trận hai lần, một lần qua thủ tục Loang và một lần đếm số ô bị giam. Vậy tổng cộng thuật toán THETICH thực hiện 2 x m x n x (hmax – Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn hmin) thao tác, do đó độ phức tạp tính toán là O(m x n x (hmax – hmin)). 45 Chƣơng 3: ỨNG DỤNG VÀ THỬ NGHIỆM Chƣơng 3 học viên d ựa vào cơ sở lý thuyết GIS và các thuật toán
đƣợc trình bày ở chƣơng 2 để tìm hiểu , phân tích và trình bày các bƣớ c cài
đă ̣t bài toán ứng dụng trong thực tế trên mô ̣t vù ng đ ịa hình . Bài toán dụng thƣ́ nhất là tìm vùng diện tích phẳng hình chữ nhật lớn nhất trên mô ̣t vù ng đi ̣a hình (Bài toán : Dƣ̣ án x ây dƣ̣ng sân bay ), bài toán ứng dụng thứ 2 là
tính thể tích chứa nƣớc cho một lòng hồ . Trong chƣơng này ho ̣c viên cũng
trình bày về cài đặt chƣơng trình cho các thuật toán trình bày ở chƣơng 2. 3.1. Cơ sở lý thuyết và lựa chọn bài toán ứng dụng Hệ thống thông tin địa lý - Geographic Information System (GIS) là một nhánh của công nghệ thông tin, đã hình thành từ những năm 60 của thế kỷ trƣớc và phát triển rất mạnh trong những năm gần đây. GIS đƣợc sử dụng nhằm xử lý đồng bộ các lớp thông tin không gian (bản đồ) gắn với các thông tin thuộc tính, phục vụ nghiên cứu, quy hoạch và quản lý các hoạt động theo lãnh thổ [2]. Hệ thống thông tin địa lý làm việc với hai dạng mô hình dữ liệu địa lý khác nhau về cơ bản là mô hình vector và mô hình raster. Trong mô hình vector, thông tin về điểm, đƣờng và vùng đƣợc mã hoá và lƣu dƣới dạng tập hợp các toạ độ x,y. Vị trí của đối tƣợng điểm, nhƣ lỗ khoan, có thể đƣợc biểu diễn bởi một toạ độ đơn x,y. Ðối tƣợng dạng đƣờng, nhƣ đƣờng giao thông, sông suối, có thể đƣợc lƣu dƣới dạng tập hợp các toạ độ điểm. Ðối tƣợng dạng vùng, nhƣ khu vực buôn bán hay vùng lƣu vực sông, đƣợc lƣu nhƣ một vòng khép kín của các điểm toạ độ. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Mô hình vector rất hữu ích đối với việc mô tả các đối tƣợng riêng biệt, 46 nhƣng kém hiệu quả hơn trong miêu tả các đối tƣợng có sự chuyển đổi liên tục nhƣ kiểu đất. Trong mô hình dữ liệu Raster trƣớ c hết ta có k hái niệm ảnh Raster, một file ảnh chụp về một đối tƣợng không gian qua máy ảnh photo hoặc một ảnh số chụp từ máy chụp số (digital camera) hoặc ảnh số thu nhận từ các đầu ghi phổ trên các vệ tinh là các ảnh có cấu trúc raster. Một ảnh raster là một tập hợp các ô lƣới. Với dữ liệu raster thì các tệp thuộc tính thông thƣờng chứa dữ liệu liên quan đến lớp hiện tƣợng tự nhiên thay cho các đối tƣợng rời rạc. Raster đƣợc định nghĩa nhƣ là ma trận không gian của các đơn vị ảnh (picture element) còn gọi là các pixel. Các pixel có kích thƣớc đồng nhất về mặt hình học, chúng là các ô vuông nhỏ và đƣợc xếp theo các dòng và Hình 3.1: Ma trận không gian của một file ảnh raster có cấu trúc pixel các cột giống nhƣ một lƣới ô vuông (Hình 3.1). Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Cấu trúc raster là một trong những cấu trúc dữ liệu đơn giản nhất 47 trong GIS. Nó còn đƣợc gọi là “tổ chức theo ô vuông của dữ liệu không gian” (cellular organization of spatial data). Pixel là phần tử cơ sở của cấu trúc dữ liệu Raster để biểu diễn một đặc trƣng địa lý f(x,y) nào đó, giá trị của pixel chỉ tính chất của đối tƣợng không gian. Giá trị số của pixel chính là mã đƣợc gắn cho đối tƣợng không gian (tức là mỗi đối tƣợng không gian có một mã nhất định). Giá trị bằng không thƣờng là những pixel chỉ vùng ngoài khu vực nghiên cứu. Ví dụ các đối tƣợng đất trồng bắp có mã bằng 1, đất trồng cam có mã bằng 2, đất trồng điều có mã bằng 3, đất trồng mía có Hình 3.2: Các đối tượng không gian được mã hoá trong mô hình Raster mã bằng 4…(hình 3.2). Thuộc tính gán cho ô sẽ định nghĩa phân lớp, nhóm, chủ đề hoặc giá trị đo đƣợc ở tại vị trí của ô. Ô có thể có giá trị là số nguyên hoặc số thập phân. Khi một giá trị số nguyên đƣợc sử dụng cho ô ảnh, nó có thể đƣợc Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn dùng làm mã nhận dạng. Hình 3.3: Các điểm ả nh được mã hoá trong mô hình Raster như một ma trận số nguyên 48 Nhƣ vậy, mô hình Raster biểu diễn không gian nhƣ là một ma trận số nguyên, mỗi một giá trị số nguyên đại diện cho một thuộc tính, vị trí của số nguyên chính là vị trí của đối tƣợng. Ma trận không gian từ các ô ảnh này đƣợc mã hoá và lƣu trữ trong máy tính theo quy luật nhất định thông qua vị trí của từng ô. Viê ̣c lƣ̣a cho ̣n bài toán ƣ́ ng du ̣ng đƣơ ̣c dƣ̣a trên hai yếu tố cơ bản , thƣ́
nhất là cách biểu diễn mô hình Raster không gian nhƣ là một ma trận số nguyên và thứ hai là hai thuâ ̣t toán đƣơ ̣c đề câ ̣p chƣơng 2 là thuật toán tìm
hình nhật tối đại và thuật toá n tính thể tích nƣớ c đọng. Bài toán ứng dụng 1: Ứng dụng thuâ ̣t toán tìm hình chữ nhật tối đại đƣợc áp dụng thƣ̣c tế trong lớ p các bài toán nhƣ: quy hoạch xây dựng, tìm vùng lớn nhất để xây xƣởng công nghiệp, xây dựng một sân vận động, …. Trong luâ ̣n văn cho ̣n bài toán ứng dụng lƣ̣a cho ̣n là xác định một vùng hình chữ nhật có diện tích lớn nhất và bằng phẳng trên một vùng địa hình để xây dƣ̣ng sân bay – Bài toán: Dự án xây dựng sân bay. Bài toán ứng dụng 2: Thuâ ̣t toán tính thể tích nƣớc đo ̣ng đƣơ ̣c ứng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn dụng trong mô ̣t số lĩnh vƣ̣c thƣ̣c tế nhƣ : Trong đi ̣a chất tính thể tích khối
địa hình, trong y học với công nghệ chụp cắt lớp con ngƣời có thể xác định 49 đƣợc khối u lớn hay nhỏ nhƣng với cách tiếp cận theo thuật toán trên chúng ta cũng hoàn toàn tin tƣởng ứng dụng và đem lại hiê ̣u quả tƣơng tự. Trong khảo sát địa chất việc tính toán khối lƣợng, trữ lƣợng một khối quặng đƣợc giam trong lòng đất luôn là bài toán phức tạp tuy nhiên bài toán phức tạp này cũng có thể giải quyết bằng thuật toán trên nếu chúng ta gắn số đo khảo sát địa hình vào một hệ quy chiếu phù hợp. Luâ ̣n văn cho ̣n bài toán ứng dụng trong lĩnh vực thủy lợi là bài toán tính thể tích chƣ́ a nƣớ c cho mô ̣t lòng hồ. 3.2. Bài toán: Dự án xây dựng sân bay 3.2.1. Phát biểu bài toán Tại Thành phố Hải Phòng, trong năm 2015 có đƣa ra đề án xây dựng sân bay tại Huyện Thủy Nguyên nhằm phát triển hệ thống giao thông hàng không và phát triển nền kinh tế Thành Phố, đặc biệt là phát triển kinh tế của Huyện. Sau khi thống nhất quyết định thực hiện đề án và mời thầu. Để thắng thầu thì nhà thầu phải đƣa ra một phƣơng án khoa học với giá trị gói thầu dự án thích hợp. Một trong những yếu tố quyết định tính khoa học và giá trị của gói thầu đó là chọn địa điểm xây dựng sân bay sao cho trên vù ng đi ̣a hình cho sẵn củ a Huyê ̣n hãy tìm ra vùng diện tích lớn
nhất, bằng phẳng là hình chữ nhật để tiết kiệm chi phí san lấp mặt bằng. 3.2.2. Mô tả dƣ̃ liê ̣u Bài toán đƣợc ra trên vùng địa hình có những vùng bằng phẳng khác phí cho công việc xây dựng nhau nếu ta tìm đƣơ ̣c mô ̣ t vù ng có diê ̣n tích lớ n nhất và bằng phẳng nhất
theo hình chƣ̃ nhâ ̣t để xây dƣ̣ng s ân bay thì bài toán đƣợc đáp ứng sẽ giảm
đáng kể nhƣ̃ng chi
. Đồng thời không ảnh Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn hƣở ng nhiều đến nhƣ̃ng quy hoa ̣ch vù ng lân câ ̣n , không tốn kém cho viê ̣c
san lấp mă ̣t bằng . 50 Sau khi khảo sát bằng các biện pháp nghiệp vụ thực nghiệm đo đạc độ cao bài toán đƣa về có đ ầu vào là một ma trận A kích thƣớc n x m, giá
trị trong ô A[i,j] (với i = 1 .. n, j = 1 .. m) là độ cao tƣơng ứng với vị trí đo đƣợc trên địa hình. Đầu ra là một ma trận con lớn nhất có độ cao bằng nhau. - Input: Tệp SANBAY.INT gồm: + Dòng đầu chứa 2 số nguyên n và m
+ n dòng sau, mỗi dòng chứa m số nguyên cách nhau dấu cách. - Output: Tệp SANBAY.OUT gồm: + Dòng đầu là diện tích hình chữ nhật lớn nhất bằng phẳng + Dòng 2 tọa độ đỉnh trên bên trái của hình chữ nhật. + Dòng 3 là tọa độ đỉnh dƣới bên phải của hình chữ nhật tìm đƣợc. 3.2.3. Thiết kế cá c bƣớ c thƣ̣c hiê ̣n Bước 1: Khảo sát địa h ình lấy giá tri ̣ thực địa số liệu thể hiện là ma trận mà giá trị các ô trong ma trận thể hiện độ cao tƣơng ứng đo đƣợc tại vị trí đó. Ví dụ từ một vùng địa hình khảo sát Hình 3.4: Vùng địa hình khảo sát xây dựng sân bay (Hình 3.4) Ta có ma trận thể hiện độ cao tƣơng ứng nhƣ sau: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 51 Bước 2: Lƣu toàn bộ các giá trị khác nhau trong ma trận (các độ cao đo đƣợc tại địa hình) vào mảng một chiều (mảng B), ta đƣợc: So với bài toán tìm hình chữ nhật tối đại chứa toàn số 1 trong ma trận chỉ chứa hai giá trị 0 và 1 ở chƣơng 2 thì bài toán này đầu vào là một ma trận chứa nhiều giá trị hơn. Vấn đề đặt ra là tìm cách đƣa bài toán về bài toán đầu vào là một ma trận chỉ chứa 2 loại giá trị 0 và 1 để tìm ra diện tích hình chữ nhật lớn nhất chứa toàn 1? Bước 3: Xét giá trị đầu tiên trong mảng chứa độ cao B là B[1] = 1 (độ cao đầu tiên = 1). Ta thay hết các ô trên ma trận A đầu vào có giá trị bằng độ cao đang xét là 1, ngƣợc lại các ô có giá trị không bằng độ cao đang xét ta thay giá trị là 0. Lúc này đầu vào của bài toán trở về dạng ma trận chỉ chứa 2 giá trị 0 và 1. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 52 Gọi chƣơng trình tính diện tích hình chữ nhật tối đại chứa toàn số 1 ở chƣơng 2 để thực hiện. Ta sẽ thu đƣợc hình chữ nhật tối đại của độ cao đang xét. Lúc này quy về bài toán ban đầu ta tìm đƣợc hình chữ nhật tối đại của độ cao đang xét (độ cao = 1). Tạm thời coi diện tích tối đại này là diện tích hình chữ nhật lớn nhất có địa hình bằng phẳng cần tìm của bài toán. Smax = Smax(B[1]) = 4 Tọa độ đỉnh trên – trái là (1,7) và đỉnh dƣới – phải là (2,8). Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Bước 4: 53 Tƣơng tự, lần lƣợt xét tiếp các độ cao tiếp theo trong mảng B cho đến hết. Ta sẽ thu đƣợc hình chữ nhật tối đại của các độ cao tƣơng ứng: Với độ cao B[2] = 2 ta đƣợc Smax(B[2]) = 5 Ta so sánh với Smax(B[2]) với Smax, nếu Smax(B[2]) > Smax thì ta thay giá trị Smax = Smax(B[2]) và lƣu lại đỉnh trên - trái mới (5,4) và đỉnh dƣới - phải (5,8), trong trƣờng hợp ngƣợc lại Smax(B[2]) <= Smax ta sẽ giữ không thay đổi gì. Với độ cao B[3] = 3 ta đƣợc Smax(B[3]) = 4 So sánh Smax(B[3]) với Smax ta thấy Smax(B[3]) < Smax nên Smax giữ nguyên. Với độ cao B[4] = 4 ta đƣợc Smax(B[4]) = 9: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 54 Ta so sánh với Smax(B[4]) với Smax, ta thấy Smax(B[4]) > Smax vậy thay giá trị Smax = Smax(B[4]) = 9 và lƣu lại đỉnh trên - trái là (2,3) và đỉnh dƣới - phải là (4,5). Với độ cao B[5] = 6 ta đƣợc Smax(B[5]) = 2: So sánh Smax(B[5]) với Smax ta thấy Smax(B[5]) < Smax nên Smax giữ nguyên. Bƣớc 5: Ghi nhận kết quả diện tích hình chữ nhật bằng phẳng lớn nhất là Smax = 9 và đỉnh trên - trái (2,3), đỉnh dƣới - phải (4,5). Tƣ̀ kết quả tìm
đƣơ ̣c ta quy đổi thành diê ̣n tích lớ n nhất trên vù ng đi ̣a hình ƣ́ ng vớ i tỉ lê ̣
bản đồ cụ thể. 3.3. Bài toán: Tính thể tích chứ a nƣớ c cho mô ̣t lòng hồ 3.3.1. Phát biểu bài toán Xuất phát từ bài toán xả lũ của các nhà máy thủy điện do không tính
đƣơ ̣c lƣơ ̣ng nƣớ c chƣ́ a củ a các hồ vù ng ha ̣ lƣu nên đã xảy ra rất nhiều nhà máy thủy điện xả lũ gây thiệt hại cho bà con sinh sống ở vùng hạ lƣu. Vậy Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn vấn đề đặt ra là phải xả lũ có lƣợng nƣớc thế nào để đảm bảo đú ng tính
chất điề u tiết lƣơ ̣ng nƣớ c phù hơ ̣p không gây thiệt hại cho ngƣời dân sống 55 ở vùng hạ lƣu, không ảnh hƣở ng đến viê ̣c tƣớ i tiêu cây trồng và đảm bảo
. Để giải quyết vấn cung cấp nƣớ c cho sinh hoa ̣t cũng nhƣ công tác thủ y lơ ̣i
đề trên con ngƣờ i cầ n phải tính chính là bài toán tính đƣơ ̣c lƣơ ̣ng nƣớ c
(tƣơng đối ) chƣ́ a củ a lòng hồ phía dƣới đập xả lũ . Trong bài toán này cần
lƣu ý đến khả năng gây loang , các vị trí loang của nƣớc là vùng mà nƣớc chảy qua để thoát ra ngoài vùng địa hình đang xét, nếu lƣợng nƣớc quá lớn sẽ dẫn đến lũ lụt tức thời (tại một thời điểm do lƣợng nƣớc quá lớn tràn qua lối thoát hẹp thì mực nƣớc dâng lên gây lũ lụt tức thời). Từ đó đƣa phƣơng án xả nƣớc trong hồ hợp lí tránh gây thiệt hại cho ngƣời dân trong vùng. 3.2.2. Mô tả dƣ̃ liê ̣u Bài toán đƣợc đặt ra trên một vùng diện tích nhất định nơi xây dựng đập thủy điện, trong đó gồm các dãy núi có nƣớc đổ dồn về hồ chứa nƣớc thủy điện và hồ tự nhiên trong vùng. Ta sẽ quy bài toán này về bài toán tính thể tích vùng nƣớc đo ̣ng tƣơng ƣ́ ng vớ i bài toán chƣ́ a nƣớ c củ a mô ̣t lòng hồ . Bằng các biện pháp nghiệp vụ sau khi thực nghiệm đo đạc độ cao các ngọn núi , quả đồi và những đảo nhỏ trong khu vƣ̣c hồ nƣớc . Ta sẽ biểu diễn đƣợc nó trên mô hình của bài toán tính thể tích vùng nƣớc ngập bằng cách chia thành từng lƣới ô vuông bằng nhau tƣơng ứng với một ma trận , . Chiều cao mỗi ô trong ma trận biểu diễn một đô ̣ cao có vị trí tƣơng ứng các ngọn núi, quả đồi, đảo nhỏ đƣợc biểu diễn bằng độ cao khác nhau, khi đó bài toán trở về bài toán tính thể tích vùng nƣớc đo ̣ng. Đầu vào là một ma trận A kích thƣớc m x n tƣơng ú ng vớ i ma trâ ̣n lƣớ i ô vuông vù ng đi ̣a hình có hồ , giá trị trong ô A[i,j] (với i=1..m, j = 1..n)
là độ cao tƣơng ứng với vị trí đo đƣợc trên địa hình. Đầu ra là thể tích chứa nƣớc trong lòng hồ. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn - Input: Ma trận số nguyên m x n. 56 (Phần tử thứ j trên dòng i trong số m dòng tiếp theo là chiều cao của cột đặt tại ô (i, j). - Output: Thể tích chứa nƣớ c trong lòng hồ . 3.3.3. Thiết kế cá c bƣớ c thƣ̣c hiê ̣n Bước 1: Khảo sát địa hình lấy giá trị thực địa số liệu thể hiện là ma trận mà giá trị các ô trong ma trận thể hiện độ cao tƣơng ứng đo đƣợc trên địa hình. Chiều cao các ngọn núi , quả đồi, đảo nhỏ đƣợc biểu diễn bằng độ cao khác
nhau. Hình 3.6: Vùng địa hình có một hồ chứa nước Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Ví dụ từ một vùng địa hình khảo sát (Hình3.6): 57 6
0 35 33 32 29 28 32 33 35
0
0 26 31
25 28 12 6
0
0 22 32
0
20 30 0
0 12 29
0
12 29 0
0
0 18 0
28 27 0
6 29
0 22 0 12 31
0
35 0
0 15 32
35 0
0
6
37 16 12 8
0 17 35
36 19 11 7 15 0 19 33
37 28 5
3 11 5 31 34
38 36 35 32 33 34 35 37
Hình 3.7: Ma trận số nguyên theo độ cao vù ng có hồ Ta có ma trận thể hiện độ cao tƣơng ứng nhƣ sau: Bước 2: Tƣ̀ số liê ̣u ma trâ ̣n (các độ cao đo đƣợc tại địa hình) chuyển vào tê ̣p dƣ̃ liê ̣u vào (tê ̣p: THETICH1.INP): + Dòng đầu chƣ́ a 2 số nguyên dƣơng m và n. + Phần tử thứ j trên dòng i trong số m dòng tiếp theo là chiều cao của cột đặt tại ô (i, j). Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Bước 3: 58 Chạy thực nghiệm bằng chƣơng trình THETICH .PAS Bước 4: Ghi nhâ ̣n kết quả lƣu ra tê ̣p THETICH 1.OUT Tƣ̀ kết quả trên ta tính đƣợc thể tích chứa nƣớc trong lòng hồ tƣơng ứng với tỉ lệ đƣơ ̣c quy đổi. 3.4. Cài đặt chƣơng trình (Cài đặt chương trình cho một số bài toán bằng ngôn ngữ Turbo pascal 7.0; Free pascal:) 3.4.1. Chƣơng trình tính diện đa giác theo tọa độ đỉnh Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 59 3.4.2. Chƣơng trình tìm diện tích hình chữ nhật tối đại Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 60 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 61 3.4.3. Chƣơng trình tính thể tích vùng nƣớc đo ̣ng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 62 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 63 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 64 KẾT LUẬN Trong luận văn học viên đã tập trung nghiên cứu, trình bày những kiến thức cơ bản về ba thuâ ̣t toán cơ bản và ứng dụng của các thuật toán vào việc giải một số bài toán trong thƣ̣c tế . Qua đó luận văn đã đạt đƣợc một số kết quả nhƣ sau: Về lý thuyết: Luâ ̣n văn đã khái quát về mô ̣t số cách tiếp câ ̣n để tính diê ̣n tích và
thể tích vâ ̣t thể vớ i các hình đă ̣c biê ̣t . Trong đó l uận văn tập trung nghiên
cứu ba thuâ ̣t toán cơ bản : Thƣ́ nhất là thuâ ̣t toán tính diện tích đa giác theo tọa độ đỉnh , thƣ́ hai là thuật toán tìm hình chữ nhật tối đại trong ma trận
chƣ́ a các kí tƣ̣ 0 và 1và thứ ba là thuâ ̣t toán tính thể tích nƣớ c đo ̣ng. Về ứng dụng Luận văn đã phân tích và cài đặt các bƣ ớc cho bài toán ứng dụng (Bài toán : trong thực tế trên mô ̣t vù ng đi ̣a hình . Bài toán dụng thứ nhất là tìm vùng
diê ̣n tích phẳng hình chƣ̃ nhâ ̣t lớ n nhất trên mô ̣t vù ng đi ̣a hình
Dƣ̣ án xây dƣ̣ng sân bay ), bài toán ứng dụng thứ hai là tính thể tích chứa nƣớ c cho mô ̣t lòng hồ . Phạm vi và khả năng áp dụng , đi ̣a Luận văn là một tài liệu tham khảo tốt cho lớ p các bài toán về tính
diê ̣n tích và thể tích . Luâ ̣n văn cũng rất hƣ̃u ích cho lĩnh vƣ̣c xây dƣ̣ng cần
xác đị nh mô ̣t miền diê ̣n tích phẳng lớ n nhất và cho lĩnh vƣ̣c thủ y lơ ̣i
chất khi cần xác đi ̣nh thể tích khối đi ̣a hình . Hướng nghiên cứu tiếp theo Nghiên cƣ́ u và t ối ƣu hóa các thuật toán để giảm bớt độ phức tạp tính toán cho các thuâ ̣t toán nêu trên . Đồng thời bổ sung và mở rộng kh ả năng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn . áp dụng các bài toán thƣờ ng gă ̣p trong thƣ̣c tế nhƣ trong lĩnh vƣ̣c y tế 65 TÀI LIỆU THAM KHẢO Tiếng Việt [1] Đặng văn Đức (2001), Hệ thống thông tin địa lý, NXB Khoa học và kỹ thuật, Hà Nội. [2] Nguyễn Xuân Huy (2010), Sáng tạo trong thuật toán và lập trình với C#, Pascal, NXB Khoa học tự nhiên và Công nghệ, Tập 1, 2, 3. [3] Lê Minh Hoàng (2002), Giải thuật và lập trình, Đa ̣i ho ̣c sƣ pha ̣m Hà Nô ̣i. [4] Đỗ Xuân Lôi (2006), Cấu trúc dữ liệu và giải thuật, NXB Đại học quốc gia Hà Nội. [5] Murray Bourne, Biên dịch: Võ Hoàng Trọng (2014), Đạo hà m tích phân ứ ng dụng được gì, Đại học Quốc gia TP. Hồ Chí Minh. [6] https://vi.wikipedia.org/wiki Tiếng Anh [7] Carola Giedion-Welcker (2006), An Evolution in Volume and Space, Wittenborn. of Computer Science State University of New York. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn [9] http://en.wikipedia.org/wiki/Shoelace_formula 66 PHỤ LỤC Mô ̣t số test (kiểm thƣ̉ ) cho các thuật toán chƣơng 2 1. Test cho chƣơng trình tính diê ̣n tí ch đa giá c theo to ̣a đô ̣ đỉnh Test 1 – Dƣ̃ liê ̣u vào Test 1 – Dƣ̃ liê ̣u ra Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Test 2 – Dƣ̃ liê ̣u vào 67 Test 2 – Dƣ̃ liê ̣u ra Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn 2. Test cho chƣơng trình tìm hình chữ nhật tối đạ i 68 Test 1 – Dƣ̃ liê ̣u vào Test 1 – Dƣ̃ liê ̣u ra Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Test 2 – Dƣ̃ liê ̣u vào 69 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Test 2 – Dƣ̃ liê ̣u ra 70 3. Test cho chƣơng trình tính thể tích nƣớc đọng Test 1 – Dƣ̃ liê ̣u vào Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Test 1 – Dƣ̃ liê ̣u ra 71 Test 2 – Dƣ̃ liê ̣u vào Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn Test 2 – Dƣ̃ liê ̣u ra1 2 2 2 2 3
1 2 2 4 3 3
1 4 4 4 3 3
2 4 4 4 3 3
2 4 4 4 2 2
2 3 2 3 2 1
1 1 2 2 2 5
1 1 2 3 2 5
Hình 3.5: Ma trận số nguyên thể hiê ̣n theo độ cao vù ng đi ̣a hình
1
2
3
4
6
B
1
2
3
4
5
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
1 1 0 0 0 0
1 1 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
1 1 0 0 0 0
1 1 0 0 0 0
1 2 2 2 2 3
1 2 2 4 3 3
1 4 4 4 3 3
2 4 4 4 3 3
2 4 4 4 2 2
2 3 2 3 2 1
1 1 2 2 2 6
1 1 2 3 2 6
1 2 2 2 2 3
1 2 2 4 3 3
1 4 4 4 3 3
2 4 4 4 2 3
2 4 4 4 2 2
2 3 2 3 2 1
1 1 2 2 2 6
1 1 2 3 2 6
1 2 2 2 2 3
1 2 2 4 3 3
1 4 4 4 3 3
2 4 4 4 2 3
2 4 4 4 2 2
2 3 2 3 2 1
1 1 2 2 2 6
1 1 2 3 2 6
1 2 2 2 2 3
1 2 2 4 3 3
1 4 4 4 3 3
2 4 4 4 2 3
2 4 4 4 2 2
2 3 2 3 2 1
1 1 2 2 2 6
1 1 2 3 2 6
1 2 2 2 2 3
1 2 2 4 3 3
1 4 4 4 3 3
2 4 4 4 2 3
2 4 4 4 2 2
2 3 2 3 2 1
1 1 2 2 2 6
1 1 2 3 2 6
Uses math;
Const finp='dagiac.inp';
fout='dagiac.out';
var fi,fo:text;
x,y:array[1..1000] of longint;
n,i:integer;
t1,t2:longint;
s:real;
procedure docdl;
begin
assign(fi,finp);
reset(fi);
read(fi,n);
for i:=1 to n do read(fi,x[i],y[i]);
close(fi);
end;
procedure xuli;
begin
t1:=x[n]*y[1];
t2:=y[n]*x[1];
for i:=1 to n-1 do
begin
t1:=t1+x[i]*y[i+1];
t2:=t2+y[i]*x[i+1];
end;
s:=abs(t1-t2)/2;
end;
procedure ghikq;
begin
assign(fo,fout);
rewrite(fo);
write(fo,s:8:2);
close(fo);
end;
begin
docdl;
xuli;
ghikq;
end.
Uses math;
Const finp='cnmax.inp';//cnmax.inp';
fout='cnmax.out';//cnmax.out';
Var fi,fo:text;
m,n,d :longint;
l,r,h,a :array[0..1001,0..70] of longint;
s,smax,yt,yd,xtr,xph:longint;
Procedure docdl;
var i,j:longint;
begin
assign(fi,finp);reset(fi);
readln(fi,n,m);
for i:=1 to n do
begin
for j:=1 to m do read(fi,a[i,j]);
readln(fi);
end;
close(fi);
end;
Procedure xulicanh;
var i,j,k:longint;
begin
for i:=1 to n do
for j:=1 to m do
if a[i,j]=0 then h[i,j]:=0
else h[i,j]:=h[i-1,j]+1;
for i:= 1 to n do
for j:=1 to m do
if a[i,j]=0 then l[i,j]:=0
else
begin
d:=0;
for k:=1 to j do
if (a[i,k]=1) and
(h[i,k]>=h[i,j]) then inc(d)
else d:=0;
l[i,j]:=d;
end;
for i:=1 to n do
for j:=m downto 1 do
if a[i,j]=0 then l[i,j]:=0
else
begin
d:=0;
for k:=m downto j do
if (a[i,k]=1) and
(h[i,k]>=h[i,j]) then inc(d)
else d:=0;
r[i,j]:=d;
end;
end;
procedure xuli;
var i,j:longint;
begin
Smax:=0;
for i:=1 to n do
for j:=1 to m do
begin
S:=h[i,j]*(l[i,j]+r[i,j]-1);
if s> smax then
begin
smax:=s;
yt:=i+1-h[i,j];
xtr:=j+1-l[i,j];
yd:=i;
xph:=xtr+(l[i,j]+r[i,j]-1)-1;
end;
end;
end;
procedure ghikq;
begin
assign(fo,fout);
rewrite(fo);
writeln(fo,smax);
writeln(fo,xtr,' ',yt);
writeln(fo,xph,' ',yd);
close(fo);
end;
Begin
docdl;
xulicanh;
xuli;
ghikq;
end.
Program MODEL;
Uses math;
Const finp='thetich.inp';
fout='thetich.out';
Var fi,fo:text;
m,n,res,hmin,hmax,h,count :longint;
a,free :array[0..1001,0..1001] of longint;
Procedure Docdl;
var i,j :longint;
begin
assign(fi,finp);
reset(fi);
read(fi,m,n);
hmin:=100000000;
hmax:=0;
for i:=1 to m do
for j:=1 to n do
begin
read(fi,a[i,j]);
hmin:=min(hmin,a[i,j]);
hmax:=max(hmax,a[i,j]);
end;
close(fi);
end;
Procedure LOANG(x,y: longint); //Loang
begin
free[x,y]:=count;
if (x>1)and(free[x-1,y]
// Cac o co chieu cao
[8] Steve S.Skiena (2008), The Algorithm Design Manual, Department
