Violet
Dethi

Tin tức thư viện

Khắc phục hiện tượng không xuất hiện menu Bộ công cụ Violet trên PowerPoint và Word

12099162 Kính chào các thầy, cô. Khi cài đặt phần mềm , trên PowerPoint và Word sẽ mặc định xuất hiện menu Bộ công cụ Violet để thầy, cô có thể sử dụng các tính năng đặc biệt của phần mềm ngay trên PowerPoint và Word. Tuy nhiên sau khi cài đặt phần mềm , với nhiều máy tính sẽ...
Xem tiếp

Quảng cáo

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (024) 66 745 632
  • 096 181 2005
  • contact@bachkim.vn

Tìm kiếm Đề thi, Kiểm tra

Áp dụng Thuật toán Euclid về UCLN & BCNN.doc

Nhấn vào đây để tải về
Hiển thị toàn màn hình
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Phạm Huy Hoạt
Ngày gửi: 17h:39' 07-11-2014
Dung lượng: 105.3 KB
Số lượt tải: 223
Số lượt thích: 0 người
Áp dụng Thuật toán Euclid
tính nhanh ước chung lớn nhất &
Bội số chung nhỏ nhất


“Thuật toán Euclid” là một trong những thuật toán cổ nhất được biết đến, từ thời Hy Lạp cổ đại, sau đó được Euclid (ơ –clit) hệ thống và phát triển nên thuật toán mang tên ông. Về số học, “Thuật toán Euclid” là một thuật toán để xác định ước số chung lớn nhất (GCD – Greatest Common Divisor) của 2 phần tử thuộc vùng Euclid (ví dụ: các số nguyên). Khi có UCLN ta cũng tính nhanh được BSCNN. Thuật toán này không yêu cầu việc phân tích thành thừa số 2 số nguyên.

1/ Thuật toán Oclit – dùng để tìm USCLN của 2 số nguyên bất kỳ.

Để tìm USCLN của hai số nguyên a và b bất kỳ ta dùng cách chia liên tiếp hay còn gọi là “vòng lặp” như sau:

Bước 1: Lấy a chia cho b:
Nếu a chia hết cho b thì USCLN(a,b) = b.
Nếu a không chia hết cho b (dư r) thì làm tiếp bước 2.

Bước 2: Lấy b chia cho số dư r:
Nếu b chia hết cho r thì USCLN(a,b) = r
Nếu b chia cho r dư r1 (r1 # 0) thì làm tiếp bước 3.

Bước 3: Lấy r chia cho số dư r1:
Nếu r chia cho r1 dư 0 thì UCLN(a,b) = r1.
Nếu r chia cho r1 dư r2 (r2 # 0) thì làm tiếp bước 4.

Bước 4: Lấy r1 chia cho số dư r2:
Nếu r1 chia hết cho r2 thì USCLN(a,b) = r2.
Nếu r1 cho cho r2 dư r3 (r3 # 0) thì làm tiếp như trên đến khi số dư bằng 0.

Số dư cuối cùng khác 0 trong dãy chia liên tiếp như trên là USCLN(a,b).

Ví dụ Tính ước số chung lớn nhất của 91 và 287.
Trước hết lấy 287 (số lớn hơn trong 2 số) chia cho 91:
287 = 91*3 + 14 (91 & 14 sẽ được dùng cho vòng lặp kế)
Ta thấy bất kỳ số nào chia hết bởi 287 và 91 cũng sẽ chia hết bởi
287 - 91*3 = 14.
Tương tự, số chia hết bởi 91 và 14 cũng chia hết bởi 91*3 + 14 = 287.
Do đó, ƯSCLN(91,287) = ƯSCLN(91,14).
( Bài toán trở thành tìm ƯSCLN(91,14). Lặp lại quy trình trên cho đến khi phép chia không còn số dư như sau:
91 = 14*6 + 7 (14 & 7 sẽ được dùng cho vòng lặp kế)
14 = 7*2 (không còn số dư ( kết thúc, nhận 7 làm kết quả
Thật ậy: 7 = ƯSCLN(14,7) = ƯSCLN(91,14) = ƯSCLN(287,91
Cuối cùng ƯSCLN(287,91) = 7

2/ Tính BSCNN nhanh nhất

Để việc giải toán về BCNN & UCLN được nhanh, Nếu biết áp dụng “Thuật toán Euclid” :
Biết rằng: hai số nguyên a, b có BCNN là [ a,b] và ƯCLN là (a,b) thì



Nghĩa là: Tích 2 số nguyên (a x b ( = UCLN (a,b) x BSCNN (a,b)

Ví dụ: có a = 12; b = 18 ( USCLN (12,18) = 6 thì:
BSCNN (12,18) = (18) : 6 = 36
Nếu làm theo cách phân tich thừa số nguyên tố thì phải tính:
12 = ; 18 = 2 ( BSCNN (12,18) = 22 x 32 = 36
Nhận xét: Với cặp số nguyên có nhiều chữ số thì việc phân tích ra thừa số nguyên tố mất nhiều thời gian; trong khi lấy tích số có thể bấm máy tính cầm tay khá nhanh và dễ hơn.


PHH sưu tầm & giới thiệu - 11 / 2014
 
Gửi ý kiến

↓ CHÚ Ý: Bài giảng này được nén lại dưới dạng RAR và có thể chứa nhiều file. Hệ thống chỉ hiển thị 1 file trong số đó, đề nghị các thầy cô KIỂM TRA KỸ TRƯỚC KHI NHẬN XÉT  ↓