DạyhọcIntel.net  

Bộ Giáo dục
Đào tạo

Chương trình dạy học
của Intel tại Việt Nam

Tài liệu
Hướng dẫn Kỹ năng

Viện Nghiên cứu Giáo dục
ĐH Sư Phạm TP. HCM

Intel Teach Elements


Trở lại   DạyhọcIntel.net > Góc nghiệp vụ sư phạm > Công tác chuyên môn > Tin Học

Reply
 
Công cụ chủ đề Kiểu hiển thị
Old 04-10-2008, 13:22   #1
admin admin is offline 04-10-2008, 13:22

Chúng ta hãy thử cùng giải bài toán sau:

Cho hai số nguyên dương M và N với M <= N.

Nếu u là ƯCLN của (N - M) và M thì u cũng là ƯCLN của M và N.


Giải:

Trước tiên ta xét bổ đề (1) như sau:

Cho 2 số nguyên dương k, l. Nếu k và l là nguyên tố cùng nhau thì (k+l) và l cũng nguyên tố cùng nhau.

Chứng minh: Ta dùng phản chứng như sau:

Giả sử (k+l) và l không nguyên tố cùng nhau, nghĩa là tồn tại 1 số nguyên dương t > 1 là ƯSC của (k+l) và l. Khi đó ta dễ dàng chứng minh t cũng là ước của k.

Vì k và l có cùng ƯSC t > 1 nên k và l không nguyên tố cùng nhau. Mâu thuẫn giả thiết.

Trở lại bài toán ban đầu. Vì u là ƯCLN của (N-M) và M nên tồn tại 2 số nguyên dương k và l nguyên tố cùng nhau mà N-M = k.u và M = l.u. Suy ra N = (k+l).u và M = l.u.

Theo bổ đề (1) ta có (k+l) và l là nguyên tố cùng nhau nên u là ƯCLN của M và N.

Cách chứng minh tương tự cho bài toán sau:

Cho 2 số nguyên dương M và N với M <= N.

Nếu u là ƯCLN của (N mod M) và M thì u cũng là ƯCLN của M và N.
__________________
Khi cuộc sống có động lực mới mạnh mẽ ... bé Khánh Đan!

 
admin's Avatar
admin
Administrators
Points: 154,068, Level: 100 Points: 154,068, Level: 100 Points: 154,068, Level: 100
Activity: 14% Activity: 14% Activity: 14%
Gia nhập: 06-2007
Đơn vị: THPT Mạc Đĩnh Chi - TP. HCM
Bài viết: 1,897
Cảm ơn: 3,614
Được cảm ơn 7,207 lần trong 1,319 bài
Bài viết blog: 6
Lượt xem: 5109
Trả lời kèm trích dẫn
Đã cảm ơn admin:
Old 04-10-2008, 16:05   #2
trungcannd
Lớp 2
Points: 14,500, Level: 36 Points: 14,500, Level: 36 Points: 14,500, Level: 36
Activity: 0% Activity: 0% Activity: 0%
 
Gia nhập: 09-2008
Đơn vị: ĐHSPKT NĐ
Bài viết: 59
Cảm ơn: 13
Được cảm ơn 32 lần trong 24 bài
Mặc định

Trích dẫn:
Cho 2 số nguyên dương k, l. Nếu k và l là nguyên tố cùng nhau thì (k+l) và l cũng nguyên tố cùng nhau.
2 số được gọi là nguyên tố cùng nhau là 2 số có ƯCLN=1
Phương pháp tìm ƯCLN bằng phép mod (hay trừ) liên liếp là phương pháp Euclit phải không nhỉ
trungcannd is offline   Trả lời kèm trích dẫn
Old 05-10-2008, 15:31   #3
Bảo Đức
Tổng phụ trách
Points: 100,408, Level: 98 Points: 100,408, Level: 98 Points: 100,408, Level: 98
Activity: 17% Activity: 17% Activity: 17%
 
Bảo Đức's Avatar
 
Gia nhập: 03-2008
Đơn vị: Hà Nội
Bài viết: 441
Cảm ơn: 3,206
Được cảm ơn 2,536 lần trong 427 bài
Bài viết blog: 23
Mặc định

Trích dẫn:
Phương pháp tìm ƯCLN bằng phép mod (hay trừ) liên liếp là phương pháp Euclit phải không nhỉ
Ý thầy là gì vậy, em chưa hiểu? mod đâu phải là phép trừ?
__________________

Bảo Đức is offline   Trả lời kèm trích dẫn
Old 05-10-2008, 15:33   #4
Bé Nấm
Cao đẳng
Points: 23,460, Level: 46 Points: 23,460, Level: 46 Points: 23,460, Level: 46
Activity: 0% Activity: 0% Activity: 0%
 
Bé Nấm's Avatar
 
Gia nhập: 07-2008
Đơn vị: Quốc Học
Bài viết: 424
Cảm ơn: 3,198
Được cảm ơn 1,913 lần trong 374 bài
Bài viết blog: 1
Mặc định

Trích dẫn:
Nguyên bản bởi Bao Duc Xem bài viết
Ý thầy là gì vậy, em chưa hiểu? mod đâu phải là phép trừ?
Cũng vì cái vụ ni mà hôm qua em đau đầu lục sách. Vẫn chưa hiểu ý của Thầy trungcannd lắm. Hixhix.
__________________
You’re the special one - my only. Cos it’s you [Uniquely You]
Bé Nấm is offline   Trả lời kèm trích dẫn
Old 05-10-2008, 15:50   #5
trungcannd
Lớp 2
Points: 14,500, Level: 36 Points: 14,500, Level: 36 Points: 14,500, Level: 36
Activity: 0% Activity: 0% Activity: 0%
 
Gia nhập: 09-2008
Đơn vị: ĐHSPKT NĐ
Bài viết: 59
Cảm ơn: 13
Được cảm ơn 32 lần trong 24 bài
Mặc định

à tìm UCLN của 2 số có 2 phương pháp và mod dần a với b. Phương pháp còn lại là trừ dần a và b. Xin lỗi ko nói rõ ràng
trungcannd is offline   Trả lời kèm trích dẫn
Đã cảm ơn trungcannd:
Old 05-10-2008, 15:59   #6
tungld
Cao đẳng
Points: 79,930, Level: 87 Points: 79,930, Level: 87 Points: 79,930, Level: 87
Activity: 0% Activity: 0% Activity: 0%
 
tungld's Avatar
 
Gia nhập: 02-2008
Đơn vị: Trường THPT Quảng Uyên, Cao Bằng
Bài viết: 542
Cảm ơn: 723
Được cảm ơn 955 lần trong 336 bài
Bài viết blog: 1
Mặc định

Trích dẫn:
Nguyên bản bởi Bé Nấm Xem bài viết
Cũng vì cái vụ ni mà hôm qua em đau đầu lục sách. Vẫn chưa hiểu ý của Thầy trungcannd lắm. Hixhix.
theo tôi nhớ không nhầm, Euclit đã chứng minh qua phép chia lấy nguyên (trong TP gọi là phép MOD) liên tiếp hai số nguyên dương cho đến khi hai số bằng nhau (hay thương số bằng 1) thì đó là ưcln của 2 số ban đầu. Tương tự đối với phương pháp trừ liên tiếp số lớn cho số bé, ta cũng được kết quả tương tự.
Ví dụ:
Đối với phép chia: Tìm ước chung lớn nhất của 16 và 2.
Đối với phương pháp chia lấy phần nguyên liên tiếp số lớn cho số nhỏ.
ta có: UCLN(16,2) = UCLN(16 div 2, 2) = UCLN(8 div 2, 2) = UCLN(4 div 2, 2) = UCLN(2,2)= 2.
Đối với phương pháp trừ liên tiếp.
UCLN(16 - 2,2) = UCLN(14-2,2) = UCLN(12-2,2) = UCLN(10-2, 2) = UCLN(8-2, 2) = UCLN(6-2,2) = UCLN(4-2,2) = UCLN(2,2) = 2.
Mong các thầy cô cho ý kiến.
__________________
Biển học là vô bờ
Chuyên cần thì cập bến.
----------
Home page: thptquanguyen.edu.vn

Chỉnh sửa lần cuối bởi tungld : 05-10-2008 lúc 21:13 Lý do: sửa mod thành div
tungld is offline   Trả lời kèm trích dẫn
Old 05-10-2008, 16:17   #7
hatrunghoa
Lớp lá
Points: 1,946, Level: 12 Points: 1,946, Level: 12 Points: 1,946, Level: 12
Activity: 1% Activity: 1% Activity: 1%
 
Gia nhập: 05-2008
Đơn vị: Đang xin việc...
Bài viết: 32
Cảm ơn: 5
Được cảm ơn 17 lần trong 9 bài
Mặc định

Theo em biết thì có 2 thuật toán tìm UCLN:
1. Phương pháp Euclid thì là chia lấy phần dư
2. Phương pháp trừ liên tiếp
Trích dẫn:
ta có: UCLN(16,2) = UCLN(16 mod 2, 2) = UCLN(8 mod 2, 2) = UCLN(4 mod 2, 2) = UCLN(2,2)= 2.
E ko hiểu là 16 mod 2 = 8 hay 16 mod 2 = 0
hatrunghoa is offline   Trả lời kèm trích dẫn
Đã cảm ơn hatrunghoa:
Old 05-10-2008, 16:23   #8
tungld
Cao đẳng
Points: 79,930, Level: 87 Points: 79,930, Level: 87 Points: 79,930, Level: 87
Activity: 0% Activity: 0% Activity: 0%
 
tungld's Avatar
 
Gia nhập: 02-2008
Đơn vị: Trường THPT Quảng Uyên, Cao Bằng
Bài viết: 542
Cảm ơn: 723
Được cảm ơn 955 lần trong 336 bài
Bài viết blog: 1
Mặc định

Chào bạn.
cảm ơn bạn đã phát hiện.
mình dùng phép div. chia lấy nguyên.
__________________
Biển học là vô bờ
Chuyên cần thì cập bến.
----------
Home page: thptquanguyen.edu.vn

Chỉnh sửa lần cuối bởi tungld : 05-10-2008 lúc 21:14 Lý do: nhầm div và mod
tungld is offline   Trả lời kèm trích dẫn
Old 05-10-2008, 19:28   #9
trungcannd
Lớp 2
Points: 14,500, Level: 36 Points: 14,500, Level: 36 Points: 14,500, Level: 36
Activity: 0% Activity: 0% Activity: 0%
 
Gia nhập: 09-2008
Đơn vị: ĐHSPKT NĐ
Bài viết: 59
Cảm ơn: 13
Được cảm ơn 32 lần trong 24 bài
Mặc định

Trích dẫn:
Nguyên bản bởi tungld Xem bài viết
Chào bạn.
Mình trình bày phép toán Mod ở đây --- UCLN(16 mod 2,2)--- là phép chia lấy nguyên, tức là mình sử dụng phép Mod trong Turbo Pascal để minh hoạ. 16 mod 2 = 8.
Bạn học SP Tin 40 à? mình cũng là cựu SV của ĐHSP TN đó. mình học K37. rất vui khi được làm quen với bạn.
Xin đính chính với thầy là phép mod là lấy phần dư không phải lấy phần nguyên. Do đó 16 mod 2 = 0 chứ không phải bằng 8. Vì vậy khi a mod b = 0 thì dừng lại và lấy UCLN=b. Ở đây UCLN(16,2)=UCLN(0,2)=2.
trungcannd is offline   Trả lời kèm trích dẫn
Đã cảm ơn trungcannd:
Old 05-10-2008, 20:32   #10
tuyenty
Cao đẳng
Points: 21,203, Level: 44 Points: 21,203, Level: 44 Points: 21,203, Level: 44
Activity: 0% Activity: 0% Activity: 0%
 
tuyenty's Avatar
 
Gia nhập: 07-2008
Đơn vị: Trường THCS Quảng Phú_Huế
Bài viết: 589
Cảm ơn: 1,484
Được cảm ơn 1,355 lần trong 448 bài
Mặc định

Phép div mới lấy phần nguyên thầy ạ!
__________________
Suốt đời tận tuỵ vì lớp trẻ
Nghìn năm cống hiến tuổi thanh xuân

ttuyenty@yahoo.com
tuyenty is offline   Trả lời kèm trích dẫn
Reply


Những người đang xem chủ đề này: 1 (0 thành viên và 1 khách)
 
Công cụ chủ đề
Kiểu hiển thị

Quyền đăng bài
Bạn không thể đăng chủ đề mới
Bạn không thể đăng bài trả lời
Bạn không thể đính kèm
Bạn không thể sửa bài viết của bạn

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Nhảy đến diễn đàn

Những chủ đề liên quan
Chủ đề Người khởi xướng Diễn đàn Trả lời Bài cuối
x là số nguyên tố? admin Tin Học 17 21-03-2009 00:15
Đột phá trong nhận thức về chúa Nguyễn, triều Nguyễn ProIT Góc trò chuyện 0 18-10-2008 12:46
Cần tìm thông tin về Hàn Hải Nguyên ThiHoa Lịch Sử 0 03-10-2008 08:35
Các trường sư phạm phải tìm ra nguyên nhân bạo hành học đường CoSin Công tác quản lý giáo dục 0 22-09-2008 20:14
Ns. Nguyễn Cường hungbean30b Âm nhạc 0 03-04-2008 07:05

Tất cả giờ đều quy về GMT +7. Bây giờ là 13:44.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Thuộc quyền sở hữu của DạyhọcIntel.net