Cong ty Cong Nghe Tin hoc Nha truong http://www.vnschool.net

PHƯƠNG PHÁP GIẢI TOÁN HÌNH HỌC BẰNG NGÔN NGỮ LẬP TRÌNH PASCAL
06/10/2010

Qua quá trình tham gia giảng dạy và bồi dưỡng học sinh giỏi chúng tôi thấy nhiều bài toán đòi hỏi học sinh phải tìm ra mô hình toán học cụ thể từ yêu cầu phức tạp của bài toán.


Thực tế cho thấy những học sinh có khả năng vận dụng kiến thức toán học vào quá trình phân tích đề bài sẽ nhanh chóng phát hiện được mô hình toán học của bài toán và đưa ra lời giải hợp lý. Việc hướng cho học sinh phát hiện ra những mối liên hệ của bài toán cần giải quyết với các kiến thức toán thông dụng qua quá trình tìm hiểu nội dung bài toán là không dễ dàng gì. Với mong muốn phần nào giúp học sinh cũng như giáo viên trong việc tìm ra lời giải cho một số dạng bài toán thường gặp trong chương trình THPT cần giải quyết lập trình đó là các bài toán hình học, chúng tôi xin giới thiệu phương pháp giải toán hình học bằng ngôn ngữ lập trình Pascal mà chúng tôi đã áp dụng trong quá trình giảng dạy.

I. KHÁI NIỆM HÌNH HỌC VÀ CÁC ĐỐI TƯỢNG HÌNH HỌC CƠ BẢN

1. Khái niệm hình học.

Đa số các thuật toán đều tập trung vào văn bản và các con số, chúng được thiết kế và xử lý sẵn trong phần lớn các môi trường lập trình. Đối với các bài toán hình học thì tình huống khác hẳn, ngay cả các phép toán sơ cấp trên điểm và đoạn thẳng cũng có thể là một thách thức về tính toán.

Các bài toán hình học thì dễ hình dung một cách trực quan nhưng chính điều đó lại có thể là một trở ngại. Nhiều bài toán có thể giải quyết ngay lập tức bằng cách nhìn vào một mảnh giấy nhưng lại đòi hỏi những chương trình không đơn giản.

Ví dụ: Bài toán kiểm tra một điểm có nằm trong đa giác hay không?

2. Đối tượng hình học cơ bản.

Trong các bài toán tin học thuộc loại hình học có 3 đối tượng cơ bản là: Điểm, đoạn thẳng và đa giác.

- Điểm: Được xác định là cặp (x,y) trong hệ toạ độ đề các.

- Đoạn thẳng: Là cặp điểm được nối với nhau bằng một phần của đường thẳng.

- Đa giác: Là dãy các điểm mà 2 điểm liên tiếp nối với nhau bởi đoạn thẳng và điểm đầu nối với điểm cuối tạo thành đường gấp khúc khép kín.

3. Dữ liệu lưu trữ các đối tượng hình học cơ bản

II. MỘT SỐ PHÉP TOÁN CƠ BẢN

1. Vị trí tương đối của điểm so với đường thẳng, tia và đoạn thẳng

Bài toán 1: Cho điểm . Yêu cầu:

a) Kiểm tra M có thuộc đường thẳng đi qua 2 điểm A, B hay không?

b) Kiểm tra M có thuộc đoạn thẳng AB hay không

c) Kiểm tra M có thuộc tia AB hay không

Phương pháp:

Đặt

- Điểm M thuộc đường thẳng AB khi

- Điểm M thuộc đoạn thẳng AB khi:

- Ch­¬ng tr×nh:

2. Giao của các đoạn thẳng, đường thẳng và tia

Bài toán 2. Cho 2 đường thẳng có phương trình . Tìm giao điểm (nếu có) của 2 đường thẳng trên.

Phương pháp:

+ Nếu D=Dx=Dy=0 thì kết luận 2 đường thẳng trùng nhau

+ Nếu D=0 và ((Dx 0) hoặc (Dy 0)) thì kết luận 2 đường thẳng song song

+ Nếu D 0 thì kết luận 2 đường thẳng cắt nhau tại điểm có (Dx/D, Dy/D)

Chương trình:

Bài toán 3. Cho 2 đoạn thẳng AB và CD với . Tìm giao điểm (nếu có) của 2 đoạn thẳng

Phương pháp:

Bước 1. Tìm giao điểm M của 2 đường thẳng AB và CD

Bước 2. Kiểm tra M có thuộc đồng thời cả 2 đoạn AB và CD hay không. Nếu có đó là giao điểm cần tìm, ngược lại kết luận không có.

Chương trình:

Bài toán 4. Cho tia AM chứa điểm B (khác A) và đoạn thẳng CD với . Tìm giao điểm (nếu có) của tia AM với đoạn thẳng CD.

- Phương pháp:

Bước 1. Tìm giao điểm N của 2 đường thẳng AB và CD

Bước 2. Kiểm tra N có thuộc tia AM và đoạn thẳng CD hay không. Nếu có đó là giao điểm cần tìm, ngược lại kết luận không có.

Chương trình:

3. Vị trí của điểm so với đa giác

Bài toán 5. Cho đa giác gồm N đỉnh và điểm M. Xác định vị trí tương đối của M với miền trong đa giác.

Phương pháp:

Bước 1. Kiểm tra M có thuộc cạnh nào của đa giác hay không, nếu có thì kết luận M thuộc miền trong đa giác và kết thúc

Bước 2. Kẻ MN song song với trục hoành (điểm N có hoành độ lớn hơn max hoành độ của đa giác)

Bước 3. Xác định d là số giao điểm của MN với các cạnh của đa giác. Những trường hợp sau được coi như là tăng thêm 1 giao điểm:

+ Đỉnh d[i] không thuộc đoạn thẳng MN, đỉnh d[i+1] nằm trên đoạn thẳng MN, 2 đỉnh d[i] và d[i+2] khác phía so với đường thẳng MN.

+ Đỉnh d[i-1], d[i+2] ngoài đoạn thẳng MN, hai đỉnh d[i] và d[i+1] thuộc đoạn MN, d[i-1] và d[i+1] khác phía so với đường thẳng MN

+ Đỉnh d[i] và d[i+1] không thuộc MN và cạnh (d[i],d[i+1]) cắt đoạn thẳng MN

Võ Sỹ Ngọc

(Còn tiếp)



URL của bài viết này::http://www.vnschool.net/modules.php?name=News&file=article&sid=4595

© Cong ty Cong Nghe Tin hoc Nha truong contact: sales@schoolnet.vn