Thuật Toán Ơ Cơ Lít

     

I. Mục Tiêu· nhằm mục tiêu giúp giáo sinh gọi một cách hệ thống,tổng quát mắng từ Ước =ƯC =UCLN của những sốtự nhiên(đến số nguyên). Vào đó trình bày từ cách thức tìm UCLN : bằng phương pháp phântích các số ra thừa số nguyên tố = mang đến thuật toán Ơ-clit.(thuyết trình thuật toán Ơ-clit mởrộng và thuật toán Ơ-clit search UCLN của nhì hay nhiều đa thức).· Xây dựng hệ thống bài tập củng cố.




Bạn đang xem: Thuật toán ơ cơ lít

*

Giáo viên hướng dẫn: Thầy ThiệnNhóm thể hiện VI: Tiển, Long, Trinh. Bài bác giảng UCLN VÀ THUẬT TOÁN Ơ-CLITI. Mục tiêu • nhằm giúp giáo sinh gọi một giải pháp hệ thống,tổng quát lác từ Ước =>ƯC =>UCLN của những số từ nhiên(đến số nguyên). Trong đó trình bày từ phương pháp tìm UCLN : bằng phương pháp phân tích những số ra thừa số yếu tố => đến thuật toán Ơ-clit.(thuyết trình thuật toán Ơ-clit không ngừng mở rộng và thuật toán Ơ-clit kiếm tìm UCLN của hai hay những đa thức). • Xây dựng hệ thống bài tập củng cố.II. Chuẩn bị • Bảng phụ ,thước kẻ, phấn màu. • Sgk toán 6 tập . • Đại số sơ cấp cho và thực hành thực tế giải toán(Hoàng Kì). • lý thuyết số (Nguyễn Hữu Hoan).III. Nội Dung hoạt động của GV với HS nội dung Hoạt Động 1 : Kiểm Tra bài Cũ 1.Ước:Câu 1:a. Số tự nhiên và thoải mái a chia hết mang đến số thoải mái và tự nhiên b Số tự nhiên và thoải mái a phân chia hết mang đến số thoải mái và tự nhiên bkhác 0 khi nào ?. Khác 0 khi tồn trên số tự nhiên và thoải mái q sao choHS: Số thoải mái và tự nhiên a phân chia hết mang lại số tự nhiên b (b là ước của a ) a= b.q •khác 0 lúc tồn trên số tự nhiên q làm thế nào cho a= b.qb, khi ấy b là gì của a ?. Ư(4)=1;2;4HS: b là mong của a (a là bội của b) Ư(6)=1;2;3;6c, tìm cầu của 4 và 6?HS : Ư(4)=1;2;4 2, Ước bình thường của nhì hay những số là ước Ư(6)=1;2;3;6 của tất cả các số đó.Câu 2: ƯC(4;6)=Ư(4) I Ư(6)=1;2a,Ước chung của nhị số a và b là gì ?HS : Ước bình thường của nhị số a với b là ước củahai số kia .GV:Ước chung của hai hay các số là ướccủa tất cả các số đó.b, tra cứu ƯC của 4 với 6 ?HS :ƯC(4;6)=Ư(4) I Ư(6)=1;2GV: Số như thế nào là số lớn nhất trong tập thích hợp cácước tầm thường của 4 cùng 6?HS: Số “2” số lớn số 1 trong tập hợp các ướcchung của 4 và 6.GV: Số “2” được call là gì ? chúng ta cùng điqua bài học lúc này để tìm câu trả lời cho câu hỏinày. Vận động 2: tra cứu ƯCLN bằng phương pháp Phân Tích những Số Ra thừa Số Nguyên Tố1.ƯCLN 1.ƯCLNVd1: trường đoản cú câu 2 ta gồm : ƯC(4;6)=1;2 ƯCLN của nhị hay nhiều số là số lớn nhất trong tập hợp các ước chung của các số đó. • 2 là ƯC của 4 cùng 6 • 2 là số lớn nhất trong tập những ước chung Nhận Xét : của 4 cùng 6. • tất cả các ước tầm thường của 4 cùng Số 2 được gọi là mong chung lớn nhất của 4 6(là1;2) đầy đủ là cầu củavà 6 . KH :ƯCLN(4;6) ƯCLN(4;6).Vd2: ƯCLN(8,12) = ? • Vậy để tìm những ước chung của các số GV phía dẫn: đã cho thì ta tìm mong của “ƯCLN của • B1: tìm kiếm ƯC(8,12) các số đó”. • B2: Số nào là số lớn số 1 trong tập hợp những ước chung của 8 cùng 12? Vd 2: ƯCLN(8,12) = ?HS: B1: ƯC(8,12)=1;2;4 B1: ƯC(8,12)=1;2;4 B2: Số “4” là số lớn nhất trong tập thích hợp B2: Số “4” là số lớn nhất trong tập hợpcác ước chung của 8 với 12. Những ước phổ biến của 8 cùng 12.Vậy ƯCLN(8,12)= 4. Vậy ƯCLN(8,12)= 4.Vd3: ƯCLN(36;84;168) = ? GV khuyên bảo : • Để tìm ƯC(36;84;168) thì ta cần liệt kê từng Ư(36);Ư(84); Ư(168) thì rất mất thời gian và khó.

Xem thêm: Những Câu Đố Mẹo Khó Có Đáp An, Tổng Hợp Những Câu Đố Mẹo Hại Não Có Đáp Án



Xem thêm: Yếu Tố Nào Quyết Định Thành Phần Cơ Giới Của Đất Được Quyết Định Bởi

• Đó là bí quyết tìm ước tầm thường theo có mang (liệt kê từng ước=> tìm cầu chung=>lấy số béo nhất). • Có cách thức nào tạo điều kiện cho ta tìm ƯCLN của đa số số có mức giá trị tương đối lớn một cách dễ dàng ! (khắc phục hạn chế liệt kê từng ước).2.Tìm ƯCLN bằng phương pháp phân tích những số 2. Tìm kiếm ƯCLN bằng phương pháp phân tích cácra vượt số yếu tắc số ra vượt số nguyên tố? Phân tích một số tự nhiên to hơn 1 ra thừa a, phân tích một số tự nhiên to hơn 1 rasố yếu tắc là gì? vượt số thành phần là: viết số đó dưới dạngHS: Phân tích một số tự nhiên to hơn 1 ra tích các thừa số nguyên tố.thừa số nhân tố là: viết số kia dưới dạng tích Vd1: 30= 2.3.5các thừa số nguyên tố.Vd1: so với sồ 30 ra thừa số nguyên tố ?HS : 30= 2.3.5Vd1 (Vd3 phần 1): ƯCLN(36;84;168) = ? GV giải đáp : B1 :Phân tích 3 số kia ra thừa số yếu tố Quy tắc: muốn tìm ƯCLN của hai hay • 36= ? các số to hơn 1, ta thực 3 bước : • 84=? B1 :Phân tích mỗi số kia ra vượt số nguyên • 168=? tố.HS: 36= 2.2.3.3 = 22.32 B2 : Chọn các thừa số thông thường lấy số mũ nhỏ tuổi 84= 2.2.3.7 = 22.3.7 nhất. 168= 2.2.2.3.7 = 23.3.7 B3 : Lập tích các thừa số đã chọn ,mỗi quá B2 : Chọn các thừa số phổ biến lấy số mũ nhỏ dại số đem với số mũ bé dại nhất của nó.Tích kia lànhất ? vận động 3 :Thuật Toán Ơ-clit1. Thuật Toán Ơ-clit 1. Thuật Toán Ơ-clit Định lí : ∃ ƯCLN(a;b) ∀ a, b Z*.Vd1(Vd3 phần 2): ƯCLN(396;378) = ?  Với nhì số nguyên a,b khác 0 ta có Ta có : 396 = 378.(…)+ (…) ? ƯCLN(a;b) = ƯCLN(|a|;|b|) phải ta có thể giảHS: 396 = 378.1+ 18Theo xẻ đề 2 ta được: thiết a>0,b>0 và a>b. • ƯCLN(396;378) = ƯCLN(…;...) ? a, té đề 1: ƯCLN(a;b) = b giả dụ a Mb . Vd :ƯCLN(12;48) = 12. (*)HS: ƯCLN(396;378) = ƯCLN(378;18) (*) b, ngã đề 2 : trường hợp a = bq + r , 0 r Theo xẻ đề 1 : b > 0) kiếm tìm số tự nhiên và thoải mái d = ƯCLN(a;b) • ƯCLN(378;18) = … ? (**) triển khai phép chia bao gồm dư:HS: ƯCLN(378;18) = 18 (**) a = bq + r (*) 0 r B2; 51 = 24.2 + 3 19 • 38 1 vì 3 0 buộc phải ƯCLN(126;51)=ƯCLN(51;24)=ƯCLN(24;3) 0 2 • B3; 24 = 3.8 + 0ƯCLN(323;57) = 19 . Vậy : b, tìm kiếm x,y Z thế nào cho 19 = 323.x + 57.y ? ƯCLN(126;51)=ƯCLN(51;24)=ƯCLN(24;3)=GV lí giải : 3Từ thuật toán Ơ-clit ta suy ra được một thuậttoán có thể chấp nhận được tìm đôi khi d = ƯCLN(a;b)và cặp số x,y Z sao để cho d =a.x + b.y.Đượcgọi là thuật toán Ơ-clit không ngừng mở rộng .2 Thuật Toán Ơ-clit mở rộngVd1 (Vd3 b): 2. Thuật Toán Ơ-clit không ngừng mở rộng Tìm x,y Z làm thế nào để cho 19 = 323.x + 57.y ? Tìm công thức của xk ,yk làm thế nào để cho ở từng bước của thuật toán Ơ-clit xẩy ra đẳng thức : rk = a.xk + b.yk (*) Vì: r0 = a = a.1+ b.0 bắt buộc lấy x0= 1, y0 =0 r1 = b = a.0+ b.1 buộc phải lấy x0= 0, y0 =1 trả sử tính được xk-2 , yk-2 và xk-1, yk-1 thì : • xk= xk-2 - xk-1.qk-1 • yk= yk-2 - yk-1.qk-1 (2 k n) khi thuật toán hoàn thành thì rn+1 =0 và d = rn . (*) đổi thay : rn = a.xn + b.yn với : xn= xn-2 – xn-1.qn-1 yn= yn-2 – yn-1.qn-1 Vậy: d = rn với x = xn ,y = yn d = ƯCLN(a;b) và d =a.x + b.y i q r0 r1 r2 x0 x1 x2 y0 y1 y2 0 5 323 57 38 1 0 1 0 1 -5 1 1 57 38 19 0 1 -1 1 -5 6 2 2 38 19 0 1 -1 -5 6Vd2 :Tìm x,y Z thế nào cho d = 41.x + 24.y với d = ƯCLN(41;24) ? i q r0 r1 r2 x0 x1 x2 y0 y1 y2 0 1 41 24 17 1 0 1 0 1 -1 1 1 24 17 7 0 1 -1 1 -1 2 2 2 17 7 3 1 -1 3 -1 2 -5 3 2 7 3 1 -1 3 -7 2 -5 12 4 3 3 1 0 3 -7 -5 12ƯCLN(41;24) = 1 và 1 = 41.(-7) + 24.12Vd3 : ƯCLN(f(x);g(x)) = ? f(x) = x4 – 4x3 + 3x2+ 4x – 4 cùng g(x) = x4 – 4x3 + 5x2 – 2xGV gợi ý : nhằm tìm ƯCLN của 2 đa thức ta cóthể dùng thuật toán Ơ-clit như search ƯCLN của haisố nguyên ko ? 3Thuật Toán Ơ-clit tìm ƯCLN của đa3Thuật Toán Ơ-clit kiếm tìm ƯCLN của nhiều thứcthức • Định lí 1. Đối cùng với hai nhiều thức không giống khôngĐể search UCLN của hai nhiều thức, ta dùng thuật toán f(x) với g(x) của P(x) luôn tồn tại và duy nhấtgiống như thuật toán Ơclit để tìm UCLN của hai UCLN của chúng.số nguyên. Vị UCLN của nhì số nguyên là 1 trong những trường giả sử f(x) cùng g(x) là hai nhiều thức bên trên trường sốhợp quan trọng đặc biệt của UCLN của hai đa thức, khi hai đa p. Ta điện thoại tư vấn đa thức h(x) là ước tầm thường của f(x) vàthức chỉ tất cả hạng tử từ bỏ do. G(x) nếu như f(x) với g(x) rất nhiều chia hết mang lại h(x).Vd1 (Vd3 phần 2): ƯCLN(f(x);g(x)) = ? f(x) Đa thức d(x) P được call là ước tầm thường lớn= x4 – 4x3 + 3x2 + 4x – 4 cùng g(x) = x4 – 4x3 + 5x2 tốt nhất (UCLN) của f(x) và g(x), kí hiệu là: d(x) =– 2x UCLN(f(x), g(x))nếu: a) d(x) là ước chung của f(x) với g(x). B) d(x) phân chia hết cho đa số ước thông thường của f(x) cùng g(x). C) hệ số tối đa của d(x) bằng 1. Hai đa thức f(x) cùng g(x) được điện thoại tư vấn là nguyên tố cùng mọi người trong nhà nếuUCLN(f(x), g(x)) = 1 • Định lí 2. Giả sử (f(x), g(x)) = d(x), lúc ấy tồn tại những đa thức u(x) với v(x) sao cho: f(x).u(x) + g(x).v(x) = d(x) vận động 4 : Củng CốBài tập 1: tra cứu x là số tự nhiên lớn tuyệt nhất sao cho: 72 Mx ; 48Mx a,Theo bí quyết phân tích các số ra tích những thừa số thành phần b,Theo thuật toán Ơ-clitHướng dẫn : ta có 72 Mx theo tư tưởng thì x là ….của 72 ? 48Mx theo tư tưởng thì x là ….của 48 ? Ta lại sở hữu đề bài xích cho “x là số thoải mái và tự nhiên lớn nhất” Vậy: x là gì của 72 cùng 48 ?Bài tập 2: Môt ngôi nhà tắm có size nền là 4,2(m) x 2,8(m). Tìm size viên gạch men nátnền hình vuông vắn sao đến vừa vặn lát kín căn phòng (không phải xẻ thêm viên nào nhằm chèn vào chỗcòn thừa) và con số viên gạch là ít nhất.Hướng dẫn : call x là cạnh viên gạch hình vuông cần tìm. Để thuận lợ đến quá trình đo lường và thống kê , đổi : 4,2m =….cm ? 2,8m =….cm ?Vì : Viên gạch nát nền hình vuông sao đến vừa vặn vẹo lát bí mật căn phòng thì …………. Con số viên gạch là ít nhất nên……………Bài 3: kiếm tìm x,y Z làm sao cho d = 204.x + 63.y .Với d = ƯCLN(204;63) ?Bài 4: search ƯCLN của những đa thức f(x) = x4 +4x3 – 3x2 – 4x – 1 cùng g(x) = x3 + x2 – x–1