zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Tài Liệu Phổ Thông

» Sáng kiến kinh nghiệm

Sáng kiến kinh nghiệm THPT: Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học

Chia sẻ: Caphesua | Ngày: | Loại File: DOC | Số trang:49

Báo xấu

14
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề tài giúp học sinh tổng hợp và phát triển thuật toán sao cho gần gũi với tư duy của học sinh phổ thông. Như vậy các phương pháp giải quyết bài toán này đã được nghiên cứu từ rất lâu, các bài toán này được các nhà nghiên cứu về toán học và lý thuyết Tin học đưa ra. Các vấn đề đưa ra là giúp học sinh sự tổng hợp và phát triển thuật toán gần gũi với tư duy của mình.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học

SỞ GD & ĐT VĨNH PHÚC TRƯỜNG PT DTNT CẤP 23 VĨNH PHÚC BÁO CÁO KẾT QUẢ SÁNG KIẾN KINH NGHIỆM Tên sáng kiến kinh nghiệm: “Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học” Tác giả sáng kiến: Nguyễn Đăng Hiệp Mã sáng kiến: 04.62.01 Vĩnh Phúc, năm 2020
MỤC LỤC Trang Trang ...........................................................................................2 1. Lời giới thiệu ................................................................................................1 2. Tên sáng kiến: ..............................................................................................1 “Một số phương pháp hình học cơ bản để giải quyết các bài toán ................... Tin học” 1 3. Tác giả sáng kiến: .........................................................................................1 5. Lĩnh vực áp dụng sáng kiến: ............................................................................1 7. Mô tả bản chất của sáng .......................................................................... kiến: 2 7.1. Về nội dung của sáng kiến: ............................................................................2 7.1.1. Thực trạng của vấn đề mà sáng kiến cần giải ...................................... quyết. 2 7.1.2. Các giải pháp: .........................................................................................2 Ví dụ............................................................................................................15 DAGIAC.INP.................................................................................................15 DAGIAC.OUT................................................................................................15 * Phương pháp 1: Dựa vào định nghĩa đa.................................................... giác lồi 15 Bài 5: Cờ vây ................................................................................................37 Bài 6: Rệp điện ......................................................................................... tử 38 Bài 7: Cắt gạch lát nền ...................................................................................39 7.2. Về khả năng áp dụng của sáng .............................................................. kiến: 40 8. Những thông tin cần được bảo mật:........................................................ không 40 9. Các điều kiện cần thiết để áp dụng sáng .................................................... kiến: 41 10. Đánh giá lợi ích thu được của sáng ........................................................... kiến 41
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN 1. Lời giới thiệu Các bài toán tin rất đa dạng và phong phú và thể loại, tuy nhiên để áp dụng và giải quyết các bài toán này yêu cầu học sinh phải nắm vững về kiến thức toán học. Trong chương trình phổ thông, môn Tin học được đưa vào giảng dạy chính khoá từ năm học 2006 2007. Lớp 11 các em sẽ được tiếp cận với ngôn ngữ lập trình Pascal, một trong những ngôn ngữ lập trình được chọn giảng dạy không chỉ ở các trường THPT mà còn được đưa vào giảng dạy ở các trường Đại học. Ngôn ngữ lập trình Pascal còn được chọn là ngôn ngữ lập trình trong các kỳ thi OLYMPIC Tin học Quốc tế. Đối với người lập trình, kiến thức tối thiểu là biết được cách tổ chức cấu trúc dữ liệu và nêu được thuật toán để giải bài toán, phát hiện bài toán và áp dụng các phương pháp giải các dạng toán đều phải qua một quá trình hình thành và tích luỹ. Xin nêu “Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học” trong chương trình phổ thông và nêu một số bài toán nâng cao. 2. Tên sáng kiến: “Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học” 3. Tác giả sáng kiến: Họ và tên: Nguyễn Đăng Hiệp Địa chỉ: Trường Phổ Thông Dân Tộc Nội Trú Cấp 23 Vĩnh Phúc Số điện thoại: 0975.486.964 E_mail:nguyendanghiep.dtnt@gmail.com 4. Chủ đầu tư tạo ra sáng kiến: Nguyễn Đăng Hiệp 5. Lĩnh vực áp dụng sáng kiến: Đề tài giúp học sinh tổng hợp và phát triển thuật toán sao cho gần gũi với tư duy của học sinh phổ thông. 1
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học Đây cũng là một vấn đề mới vì: Muốn hiển thị được một điểm ảnh hay hoạt động của con chuột máy tính đúng toạ độ, các lập trình viên đã phải lập trình và căn đúng toạ độ cho con chuột… Như vậy các phương pháp giải quyết bài toán này đã được nghiên cứu từ rất lâu, các bài toán này được các nhà nghiên cứu về toán học và lý thuyết Tin học đưa ra. Các vấn đề đưa ra là giúp học sinh sự tổng hợp và phát triển thuật toán gần gũi với tư duy của mình 6. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử Sáng kiến được áp dụng với 100 học sinh khối 11 trong trường bắt đầu từ học kỳ 1 năm học 2019 2020 7. Mô tả bản chất của sáng kiến: 7.1. Về nội dung của sáng kiến: 7.1.1. Thực trạng của vấn đề mà sáng kiến cần giải quyết. Như chúng ta đã biết lập trình trong Tin học là một phần học rất khó, đòi hỏi nhiều đến sự phát triển tư duy để tìm tìm thuật toán và đòi hỏi học sinh phải nắm vững kiến thức về mặt toán học nên đa số học sinh không say mê với môn học này. Vì vậy vai trò của giáo viên là rất quan trọng, làm thế nào để cho học sinh có hứng thú, không khí lớp học thoải mái. Giáo viên phải có phương pháp truyền đạt lôi cuốn học sinh thông qua gợi mở, thuyết minh, giải quyết vấn đề… Nhưng vẫn đảm bảo thời gian, và nội dung cơ bản của giờ học. Song do tình trạng chung hiện nay học sinh đa số mất gốc về mặt toán học, cơ sở vật chất để phục vụ giảng dạy còn thiếu vì vậy ảnh hưởng rất nhiều đến khả năng tiếp thu và sự say mê của học sinh khi học Tin học. Cho nên hiệu quả giờ học không cao. 7.1.2. Các giải pháp: Để học sinh đạt được mục đích, yêu cầu của chuẩn kiến thức, tôi đã tìm tòi, nghiên cứu, hướng dẫn học sinh thảo luận một số phương pháp hình học để 2
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học giải quyết bài toán. Giúp các em xây dựng được một số thuật toán điển hình ở dạng đơn giản và nâng cao. Tiết học trở nên sinh động hơn và giáo viên không đóng vai trò là người xây dựng lý luận mà học sinh là người chủ động để giải quyết các vấn đề. Để giờ dạy đạt hiệu quả cao và tạo hứng thú học tập của học sinh tôi đã chuẩn bị các slide (bằng phần mềm Microsoft Power Point) để trình chiếu và sử dụng các phần mềm để mô phỏng các thuật toán. Sau đây là một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học thông qua các bài toán điển hình dưới đây: 1 Vị trí tương đối của điểm so với đường thẳng và đoạn thẳng Bài toán 1: Tìm vị trí tương đối của điểm M(x0; yo) so với đường thẳng đi qua 2 điểm A(x1; y1) và B(x2; y2) (với x1 x2) Phương trình đường thẳng qua A, B là (yy1)(x2 – x1) = (y2y1)(xx1) hay là: (y2y1)*x (x2x1)*y + y1*x2 –x1* y2 = 0. +) Nếu (y2y1)*x0 (x2x1)*y0 + y1*x2 –x1* y2 > 0 thì điểm M nằm phía trên cao hơn đường thẳng AB. +) Nếu (y2y1)*x0 (x2x1)*y0 + y1*x2 x1* y2
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học Bài toán 3: Cho 2 đoạn thẳng AB và CD, toạ độ các đầu mút là A(x 1,y1), B(x2,y2), C(x3,y3) và D(x4,y4). Hãy xét xem hai đoạn thẳng này có giao nhau không. a) Cách 1: Tìm giao điểm của 2 đường thẳng AB và CD bằng cách giải hệ gồm 2 phương trình: (y2y1)*x (x2x1)*y + y1*x2 x1* y2= 0 (1) (y4y3)*x (x4x3)*y + y3*x4 x3* y4 = 0 (2) Sau đó kiểm tra xem giao điểm có thuộc 2 đoạn thẳng AB và CD hay không Tìm giao điểm (nếu có) của hai đường thẳng trong mặt phẳng tọa độ có phương trình lần lượt là a1x + b1y = c1 và a2x + b2y = c2. Bài toán này có thể dễ dàng giải được bằng việc sử dụng phương pháp đã biết ở phổ thông. Cụ thể: D: = a1*b2 a2*b1; Dx : = c1*b2 c2*b1; Dy: = a1*c2 a2*c1; If D 0 then Writeln (' x = ', Dx/D : 4:2, 'y = ', Dy/D: 4:2) else If (Dx = 0) and (Dy = 0) then Writeln (' H ai đường thẳng trùng nhau’) b) Cách 2: Trước hết xét bài toán phụ: Trên mặt phẳng toạ độ cho tam giác ABC, đi trên cạnh từ A đến B rồi đến C theo chiều nào (ngược chiều kim đồng hồ hay thuận chiều kim đồng hồ) với giả thiết không có cạnh nào song song trục tung. Ta thấy không mất ý nghĩa của bài toán khi ta quay toàn bộ tam giác một cách tuỳ ý. Vì vậy đầu tiên ta giả sử A là đỉnh có hoành độ bé nhất (x2 > x1,x3 > x1) thì hệ số góc đường thẳng AB là: k1= (y2 y1)/ (x2 x1) hệ số góc đường thẳng AC là: k2= (y3 y1)/ (x3 – x1) Ký hiệu dy1 = (y2 – y1); dx1 = (x2 x1) > 0 dy2 = (y3 – y1); dx2 = (x3 –x1) > 0 4
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học Do đó đi trên cạnh từ A đến B rồi đến C theo chiều ngược chiều kim đồng hồ khi k2 > k1 hay là dy2* dx1 > dx2 *dy1 ( mã hoá là chiều +1 ) Ngược lại đi trên cạnh từ A đến B rồi đến C theo chiều thuận chiều kim đồng hồ khi k2
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học end; function chieu(p1,p2,p3: diem): integer; var dx1,dx2,dy1,dy2: integer; begin dx1: = p2.xp1.x; dy1: = p2.yp1.y; dx2: = p3.xp1.x; dy2: = p3.yp1.y; if dx1*dy2>dy1*dx2 then chieu: = 1; if dx1*dy2
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học if giaonhau(l[1],l[2]) then writeln('giao nhau') else writeln('khong giao nhau '); readln; END. Có được điều đó là vì đoạn thẳng AB giao với đoạn thẳng CD khi và chỉ khi đi theo ABC ngược chiều với ABD và đi theo CDA ngược chiều với CDB 3 Vi trí của Điểm so với Đa giác Bài toán 4: Cho đa giác gồm N đỉnh d[1],d[2],...,d[n] và điểm M. Hãy xác định vị trí tương đối của M với miền trong của đa giác (M nằm ngoài hay nằm trong đa giác) Thuật toán: Kẻ đoạn thẳng MN song song trục hoành sao cho hoành độ của N lớn hơn hoành độ max của các hoành độ đỉnh đa giác. Xét giao các cạnh của đa giác với đoạn thẳng MN. Số giao điểm là lẻ thì M trong đa giác, chẵn thì M ngoài đa giác Có một trở ngại là gặp những trường hợp: Đỉnh d[i+1] của cạnh nằm trên đoạn thẳng MN, thì cạnh d[i]d[i+1] và cạnh d[i+1]d[i+2] đều giao với đoạn MN, hoặc cạnh d[i]d[i+1] nằm trên đoạn thẳng MN thì cả 3 cạnh d[i1]d[i], d[i]d[i+1], d[i+1]d[i+2] đều giao với MN nên xử lý như chương trình sau: Ngoài ra ta cũng có thể giải bài toán này bằng cách chia đa giác thành n2 tam giác rồi tính tổng diện tích của các tam giác ấy. Tuy nhiên phương pháp này dài dòng, ta làm cách khác như sau: chia đa giác thành các hình thang bằng cách chiếu các cạnh xuống trục hoành (hình vẽ). Hình thang được xác lập bởi cạnh A [i] A[i+1]có diện tích là Abs (S) với 1 S= * ( A[i ]* x − A[i + 1]* x ) * ( A[i ]* y + A[i + 1]* y ) 2 7
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học 1 Vậy S = S + ( A[i]* x − A[i + 1]* x ) * ( A[i ]* y + A[i + 1]* y ) ; S = Abs ( S ) 2 Sau khi gán đỉnh A[n+1]:=A[1] ta tính diện tích toàn phần của đa giác như sau: S: = 0; For i: =1 to N do S: = (1/2) * Abs(S); Chú ý : 1. Hoàn toàn tương tự ta có thể tìm diện tích của đa giác bằng cách chiếu các cạnh xuống trục tung. 2. Nếu thay bước gán S: = (1/2) * abs (S) bởi S: = S/2 thì dấu của S là dương hay âm sẽ cho ta biết chiều đánh số của các đỉnh theo thứ tự từ 1, 2,.... N là ngược hay xuôi chiều kim đồng hồ. Uses crt; const max = 100; fi = 'dagiac.inp'; type diem = record x,y: integer; end; doanthang = record p1,p2: diem; end; 8
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học var l: array[1..2] of doanthang; d: array[0..max+2] of diem; m: diem; n: byte; maxx: integer; function chieu(p1,p2,p3: diem): integer; {Xac dinh chieu di tu p1>p2>p3} var dx1,dx2,dy1,dy2: integer; begin dx1: = p2.xp1.x; dy1: = p2.yp1.y; dx2: = p3.xp1.x; dy2: = p3.yp1.y; if dx1*dy2>dy1*dx2 then chieu: = 1; if dx1*dy2
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học and (chieu(l2.p1,l2.p2,l1.p1)*chieu(l2.p1,l2.p2,l1.p2)maxx then maxx: = d[i].x; end; readln(f,m.x,m.y); close(f); end; function thuoc(p: diem;lp: doanthang): boolean; var a,b,c: real; function min2(a,b: real): real; begin if a
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học if a>b then max2: = a else max2: = b; end; begin a: = lp.p2.ylp.p1.y; b: = lp.p1.xlp.p2.x; c: = lp.p1.y*lp.p2.xlp.p1.x*lp.p2.y; if (a*p.x+b*p.y+c=0) and (min2(lp.p1.x,lp.p2.x)=p.x) then thuoc: = true else thuoc: = false; end; function trong(p: diem): boolean; var dem,i,j: integer; lt,lp: doanthang; begin dem: = 0; d[0]: = d[n]; d[n+1]: = d[1]; d[n+2]: = d[2]; lt.p1: = p; lt.p2.y: = p.y; lt.p2.x: = maxx+1; for i:=1 to n do begin lp.p1: = d[i]; lp.p2: = d[i+1]; if thuoc(p,lp) then begin 11
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học trong: = true; exit; end; if giaonhau(lp,lt) and (lp.p1.yp.y) and (lp.p2.yp.y) then inc(dem); if giaonhau(lp,lt) and ((lp.p1.y=p.y) and (lp.p2.y=p.y)) and ((d[i1].yd[i].y)*(d[i+2].yd[i].y)
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học type toado = array[1..max] of real; var x,y : toado; n: word; procedure input; var i : word; f : text; begin assign(f,fi); reset(f); readln(f,n); for i:=1 to n do readln(f,x[i],y[i]); close(f); end; function cungfia(x1,x2,x3,x4,y1,y2,y3,y4: real):boolean; var d1,d2: real; begin d1: = (y3y1)*(x2x1)(x3x1)*(y2y1); d2: = (y4y1)*(x2x1)(x4x1)*(y2y1); cungfia:=d1*d2>=0; end; function dg_loi: boolean; var i,j,k,l : word; begin for i:=1 to n do begin k: = i+2; 13
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học l: = i+1; if k=n+1 then k: = 1; if l=n+1 then l: = 1; for j:=1 to n do if (ji) and ( not cungfia(x[i],x[l],x[j],x[k],y[i],y[l],y[j],y[k])) then begin dg_loi: = false; exit; end; end; dg_loi: = true; end; BEGIN clrscr; input; if dg_loi then writeln('da giac loi ') else writeln('da giac khong loi '); END. 5 Tìm đường bao lồi chứa tập điểm cho trước Bài 6: Cho N điểm a1,a2,..., an trên mặt phẳng. Các điểm có toạ độ nguyên và không có 3 điểm nào thẳng hàng. Hãy viết chương trình xác định một đa giác không tự cắt có các đỉnh là một số điểm trong n điểm đã cho và chứa tất cả các điểm còn lại, đồng thời có chu vi nhỏ nhất. Hãy tính diện tích đa giác này Dữ liệu vào cho trong file DAGIAC.INP gồm n+1 dòng 14
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học Dòng 1 chứa số N. N dòng tiếp theo: dòng i trong n dòng này chứa toạ độ (xi,yi) của điểm ai Dữ liệu ra ghi vào file DAGIAC.OUT: Dòng 1 ghi 3 số k, v, s với k là số đỉnh đa giác tìm được, v là chu vi và s là diện tích của nó. Dòng i+1 (1 i k ) ghi toạ độ của đỉnh thứ i của đa giác. Ghi chú: các số thực có phần thập phân có 2 số lẻ Ví dụ DAGIAC.INP 5 0 1 4 4 0 4 4 0 2 2 DAGIAC.OUT 4 15.12 14.00 4 4 0 4 0 1 3 0 15
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học * Phương pháp 1: Dựa vào định nghĩa đa giác lồi Trước hết cần chú ý đa giác không tự cắt có các đỉnh là một số điểm trong n điểm đã cho và chứa tất cả các điểm còn lại, đồng thời có chu vi nhỏ nhất đó chính là đường bao lồi chứa các điểm đã cho mà các đỉnh của bao lồi thuộc tập đỉnh đã cho. Để tìm bao lồi này theo định nghĩa đa giác lồi, ta thực hiện như sau: + Tìm 2 điểm: x0, x1 chắc chắn thuộc bao lồi: đó là 2 điểm nằm trên một đường thẳng d sao cho mọi điểm còn lại đều ở cùng một phía của d. + Tìm điểm tiếp theo là xi (chọn trong các điểm còn lại chưa trong bao lồi) sao cho với mọi điểm j luôn cùng phía với x0 so với đường thẳng qua xi, x1. + Lại coi j là xi và tiếp tục tìm j mới cho đến khi không còn tìm được nữa Uses crt; const max = 100; fi = 'baoloi.inp'; fo = 'baoloi.out'; type toado = array[1..max] of real; var x,y,ly : toado; b : array[1..1000] of boolean; ds: array[1..1000] of integer; n,top : integer; f : text; procedure input; var i: integer; f : text; begin assign(f,fi); 15
Một số phương pháp hình học cơ bản để giải quyết các bài toán Tin học reset(f); readln(f,n); for i:=1 to n do readln(f,x[i],y[i]); close(f); end; function cungfia(x1,x2,x3,x4,y1,y2,y3,y4: real): boolean; var d1,d2: real; begin d1: = (y3y1)*(x2x1)(x3x1)*(y2y1); d2: = (y4y1)*(x2x1)(x4x1)*(y2y1); cungfia:=d1*d2>=0; end; function timhaidiem(var i,j: integer): boolean; var k,l: integer; begin for k:=1 to n do for l:=1 to n do if (ki)*(kj)*(li)*(lj)0 then if not cungfia(x[i],x[j],x[k],x[l],y[i],y[j],y[k],y[l]) then begin timhaidiem: = false; exit; end; timhaidiem: = true; end; 16

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.