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 25-10-2008, 11:56  
Chỉ dùm thuật toán tìm Bội chung nhỏ nhất của 2 số nguyên dương
hungchng hungchng is offline 25-10-2008, 11:56

Thầy nào biết chỉ dùm thuật toán tìm Bội chung nhỏ nhất của 2 số nguyên dương M, N

 
hungchng's Avatar
hungchng
Lớp 8
Points: 12,458, Level: 33 Points: 12,458, Level: 33 Points: 12,458, Level: 33
Activity: 0% Activity: 0% Activity: 0%
Gia nhập: 11-2007
Đơn vị: thpt Ninh Hai. Ninh Thuan
Bài viết: 174
Cảm ơn: 9
Được cảm ơn 127 lần trong 76 bài
Lượt xem: 22356
Trả lời kèm trích dẫn
Old 13-01-2010, 00:09   #21
dzt
Lớp lá
Points: 4,167, Level: 18 Points: 4,167, Level: 18 Points: 4,167, Level: 18
Activity: 14% Activity: 14% Activity: 14%
 
dzt's Avatar
 
Gia nhập: 10-2008
Đơn vị: DBDH
Bài viết: 24
Cảm ơn: 2
Được cảm ơn 12 lần trong 8 bài
Mặc định

Trích dẫn:
Nguyên bản bởi Nhất Điểm Tuyết Xem bài viết

nhưng nhỡ máy tính thực hiện phép nhân bằng cách cộng nhiều lần, phép mod bằng cách trừ nhiều lần thì sao ạ? khi đó có phải là dùng phép nhân, phép mod chỉ tiết kiệm được công viết code, chứ không giảm được thời gian tính toán , phải không ạ?
Ah, cái này bạn phải hỏi nơi viết compiler hoăc Intel và AMD thôi. hehe. Chứ nếu chỉ để tiết kiệm công viết code, mọi người chẳng cần thiết phải tối ưu giải thuật làm gì, cứ có sao để vậy
Bạn muốn tìm hiểu xin cứ google http://en.wikipedia.org/wiki/Two%27s_complement

Tôi xin chấm dứt ở đây kẻo lạc đề.

Chỉnh sửa lần cuối bởi dzt : 13-01-2010 lúc 00:49
dzt is offline   Trả lời kèm trích dẫn
Đã cảm ơn dzt:
Old 13-01-2010, 03:47   #22
Nhất Điểm Tuyết
Cao học
Points: 5,081, Level: 21 Points: 5,081, Level: 21 Points: 5,081, Level: 21
Activity: 57% Activity: 57% Activity: 57%
 
Nhất Điểm Tuyết's Avatar
 
Gia nhập: 03-2008
Đơn vị: ĐHSP,SG
Bài viết: 1,093
Cảm ơn: 1,243
Được cảm ơn 2,739 lần trong 770 bài
Mặc định


Thầy và thầy nahata cho rằng dùng phép nhân, phép mod thay cho phép cộng nhiều lần, trừ nhiều lần là một cải tiến cho thuật toán. Nếu em cho rằng đó chỉ là thủ thuật làm gọn code, mà không đóng góp gì cho việc tăng tốc thì đúng hay sai?

Quay trở lại bài toán ban đầu. Ta thử lý luận thiên về định lượng xem sao.
Giả sử M là số có m bits , N là số có n bits. Vd M = 35, N = 65 , thì m = 6, n = 7.
Khi đó độ phức tạp các thuật toán mà các thầy đưa ra và cải tiến là bao nhiêu theo m,n?
__________________

giáo viên nghèo lười dạy

Chỉnh sửa lần cuối bởi Nhất Điểm Tuyết : 13-01-2010 lúc 03:59
Nhất Điểm Tuyết is offline   Trả lời kèm trích dẫn
Old 13-01-2010, 07:38   #23
dzt
Lớp lá
Points: 4,167, Level: 18 Points: 4,167, Level: 18 Points: 4,167, Level: 18
Activity: 14% Activity: 14% Activity: 14%
 
dzt's Avatar
 
Gia nhập: 10-2008
Đơn vị: DBDH
Bài viết: 24
Cảm ơn: 2
Được cảm ơn 12 lần trong 8 bài
Mặc định

Trích dẫn:
Thầy và thầy nahata cho rằng dùng phép nhân, phép mod thay cho phép cộng nhiều lần, trừ nhiều lần là một cải tiến cho thuật toán. Nếu em cho rằng đó chỉ là thủ thuật làm gọn code, mà không đóng góp gì cho việc tăng tốc thì đúng hay sai?
Cụ thể về bài toán GCD, cái này tôi không nói mà Euclide nói nhé, tôi chỉ trình bày lại thôi. Còn về vấn đề chỉ cải tiến để làm gọn code, tôi thấy không cần thiết phải làm với thuật toán này.

Câu trả lời cho vấn đề độ phức tạp của giải thuật Euclide, bác đọc kỹ phần "Algorithmic Effiency" ở đây, tôi không giải thích thêm nhiều vì thấy chủ đề cần thảo luận ở đây là thuật toán tìm LCM chứ không phải là thuật toán tìm LCM "tối ưu", tôi không muốn mất thời gian phân tích.
Trích dẫn:
Worst-case:
...
The number of steps in Euclid's algorithm can never be more than five times the number of its digits (base 10)...
Và nếu như bác vẫn chưa thỏa mãn, bấm tiếp vô đây. Thuật toán tìm GCD được cho là tốt hiện giờ là "Binary GCD" nếu như các bác muốn tìm. Và liệu các bác có trình bày các vấn đề này cho học sinh hiểu không?

Cảm ơn đã đọc ngần ấy chữ trong các bài viết của tôi
dzt is offline   Trả lời kèm trích dẫn
Old 13-01-2010, 11:22   #24
nahata
Lớp lá
Points: 1,026, Level: 8 Points: 1,026, Level: 8 Points: 1,026, Level: 8
Activity: 49% Activity: 49% Activity: 49%
 
Gia nhập: 10-2008
Đơn vị: THCS Ninh Nhat
Bài viết: 23
Cảm ơn: 7
Được cảm ơn 10 lần trong 7 bài
Mặc định

Trích dẫn:
Và nếu như bác vẫn chưa thỏa mãn, bấm tiếp vô đây. Thuật toán tìm GCD được cho là tốt hiện giờ là "Binary GCD" nếu như các bác muốn tìm. Và liệu các bác có trình bày các vấn đề này cho học sinh hiểu không?
Yêu cầu học sinh THPT thực hiện giải thuật quá khó (để tối ưu nhất) là phản giáo dục, nhưng tối ưu 1 giải thuật đã biết mức độ vừa phải là điều cần thiết để phát triển tư duy, cải tiến tìm BCNN giống như cải tiến tìm UCLN từ cộng liên tiếp sang Euclide vậy.

Trích dẫn:
Cảm ơn đã đọc ngần ấy chữ trong các bài viết của tôi
Em luôn tìm hiểu kĩ vấn đế trước khi tranh luận để tránh sự chủ quan cá nhân nên thày ko cần cảm ơn đâu.

Ưu điểm của thày là rất tự tin vào kiến thức của mình nhưng đó cũng chính là nhược điểm của thày đó, tất cả những gì e định nói đã gói gọn trong bài viết đầu tiên trong topic này.
http://www.dayhocintel.net/diendan/s...2&postcount=12
Việc tranh cãi từ đầu đến giờ cảm giác chỉ chú trọng vào cài đặt thuật toán e đã nêu. Tuy nhiên e cảm giác thày rất hay áp đặt suy nghĩ của mình cho người khác, nhất là những đoạn code C++ kia. Có lẽ việc tranh luận nên dừng ở đây vì thể hiện thuật toán bằng ngôn ngữ cụ thể ra sao, có tối ưu không là tuy ở mỗi người.
nahata is offline   Trả lời kèm trích dẫn
Old 13-01-2010, 11:27   #25
nahata
Lớp lá
Points: 1,026, Level: 8 Points: 1,026, Level: 8 Points: 1,026, Level: 8
Activity: 49% Activity: 49% Activity: 49%
 
Gia nhập: 10-2008
Đơn vị: THCS Ninh Nhat
Bài viết: 23
Cảm ơn: 7
Được cảm ơn 10 lần trong 7 bài
Mặc định

Trích dẫn:
Nguyên bản bởi Nhất Điểm Tuyết Xem bài viết

Thầy và thầy nahata cho rằng dùng phép nhân, phép mod thay cho phép cộng nhiều lần, trừ nhiều lần là một cải tiến cho thuật toán. Nếu em cho rằng đó chỉ là thủ thuật làm gọn code, mà không đóng góp gì cho việc tăng tốc thì đúng hay sai?

Như em đã nói dùng nhân, mod để tránh dùng phép cộng nhiều lần
VD a=1; b=1000 thì a cộng 1000 lần mới bằng b, rõ ràng tăng tốc thuật toán vì 1000 phép cộng chậm hơn chỉ thực hiện 1 phép nhân chứ

Trích dẫn:
Quay trở lại bài toán ban đầu. Ta thử lý luận thiên về định lượng xem sao.
Giả sử M là số có m bits , N là số có n bits. Vd M = 35, N = 65 , thì m = 6, n = 7.
Khi đó độ phức tạp các thuật toán mà các thầy đưa ra và cải tiến là bao nhiêu theo m,n?
Nếu dùng phép cộng liên tiếp tìm BCNN(n,m) độ phức tạp O(n*m), cải tiến thì chạy nhanh hơn chút nhưng độ phức tạp vẫn vậy.
Thuật toán phân tích ra thừa số nguyên tố: đặt N=max(n,m), bước duyệt mọi ước nguyên tố chi phí thời gian N/ lg(n)
Bước chia liên tiếp cho ước lg(N)
Vậy chi phí thời gian là O( N/lg(N)*lg(N) ) =O (N)
Ưu điểm khác của phân tích nguyên tố là ko tính trực tiếp BCNN(n,m) nên phạm vi n,m lớn hơn rất nhiều

Chỉnh sửa lần cuối bởi nahata : 13-01-2010 lúc 11:40
nahata is offline   Trả lời kèm trích dẫn
Old 13-01-2010, 13:04   #26
dzt
Lớp lá
Points: 4,167, Level: 18 Points: 4,167, Level: 18 Points: 4,167, Level: 18
Activity: 14% Activity: 14% Activity: 14%
 
dzt's Avatar
 
Gia nhập: 10-2008
Đơn vị: DBDH
Bài viết: 24
Cảm ơn: 2
Được cảm ơn 12 lần trong 8 bài
Mặc định

Trích dẫn:
Yêu cầu học sinh THPT thực hiện giải thuật quá khó (để tối ưu nhất) là phản giáo dục, nhưng tối ưu 1 giải thuật đã biết mức độ vừa phải là điều cần thiết để phát triển tư duy, cải tiến tìm BCNN giống như cải tiến tìm UCLN từ cộng liên tiếp sang Euclide vậy.
Đúng vậy đấy, những thứ đó không nên yêu cầu HS thực hiện cho nên tôi không đưa ra ngay từ đầu. Và tôi cũng đồng ý là cải tiến một chút bằng phép mod hoặc nhân cho tốt hơn.

Trích dẫn:
Việc tranh cãi từ đầu đến giờ cảm giác chỉ chú trọng vào cài đặt thuật toán e đã nêu. Tuy nhiên e cảm giác thày rất hay áp đặt suy nghĩ của mình cho người khác, nhất là những đoạn code C++ kia. Có lẽ việc tranh luận nên dừng ở đây vì thể hiện thuật toán bằng ngôn ngữ cụ thể ra sao, có tối ưu không là tuy ở mỗi người.
Tôi cũng nói rồi, giải thuật là chính, còn tối ưu là ở mỗi người do đó tôi không áp đặt phải tối ưu thế này, thế kia mà nói là nên để ở một bài khác. Những đoạn code mà tôi trình bày đều do tôi tự viết và tôi thấy nên đưa vào đây để giúp các bác tiện kiểm tra thôi. Bác nói tôi áp đặt là hơi áp đặt tôi đấy hehe. Tôi đưa các liên kết đó nhằm vì bác Nhất hỏi độ phức tạp, tôi không tự viết ra giải thuật mà nó được trình bày và chứng minh rõ ràng thế rồi.

Hiện nay giải thuật LCM chưa có tài liệu nào trình bày, vì thế những thứ mình tìm hiểu được trên Internet thì cần chia sẻ với mọi người. Tranh cãi làm gì về tối ưu hay không tối ưu. Tôi chỉ cần học sinh nắm được vấn đề và thực hiện được là đủ.

Cuối cùng xin mọi người cứ tập trung vào giải thuật chính và tôi xin thôi không tranh luận kẻo bị nói là áp đặt

Mà sao không thấy bác chủ thread có ý kiến gì nhẩy?

Chỉnh sửa lần cuối bởi dzt : 13-01-2010 lúc 13:11
dzt is offline   Trả lời kèm trích dẫn
Old 13-01-2010, 22:44   #27
tttymhy
Lớp lá
Points: 1,805, Level: 11 Points: 1,805, Level: 11 Points: 1,805, Level: 11
Activity: 1% Activity: 1% Activity: 1%
 
Gia nhập: 10-2008
Đơn vị: Sơn La
Bài viết: 35
Cảm ơn: 40
Được cảm ơn 19 lần trong 11 bài
Bài viết blog: 1
Mặc định

Thầy thử tham khảo thuật toán nếu dạy đến bài For
If a>b then max:=a els max:=b;
For i:= a*b Downto max Do
If (i mod a= 0) and (i mod b =0)then BCNN:=i;
Thầy cô nào có thuật toán hay hơn thì chia sẻ nhé
tttymhy is offline   Trả lời kèm trích dẫn
Old 14-01-2010, 13:16   #28
tttymhy
Lớp lá
Points: 1,805, Level: 11 Points: 1,805, Level: 11 Points: 1,805, Level: 11
Activity: 1% Activity: 1% Activity: 1%
 
Gia nhập: 10-2008
Đơn vị: Sơn La
Bài viết: 35
Cảm ơn: 40
Được cảm ơn 19 lần trong 11 bài
Bài viết blog: 1
Mặc định

Thầy thử xem thuật toán này tìm BCNN của 2 số M,N
if M>N then Max:=M else Max:=N;
For i:= M*N Downto Max Do
If (i mod M=0) and (i mod N=0) Then BC:=i;
Write(BC);

Hoặc
if M>N then Max:=M else Max:=N;
i:=m*n;
While i<=M*N Do
If (i mod M=0) and (i mod N=0) Then
Begin
BC:=i;
i:=M*N+1;
end else i:=i+1;
Write(BC);

Chỉnh sửa lần cuối bởi thangntmk : 14-01-2010 lúc 14:21 Lý do: Ghép bài viết
tttymhy is offline   Trả lời kèm trích dẫn
Old 30-09-2010, 00:07   #29
khoipm
Lớp mầm
Points: 2,413, Level: 13 Points: 2,413, Level: 13 Points: 2,413, Level: 13
Activity: 0% Activity: 0% Activity: 0%
 
Gia nhập: 08-2008
Đơn vị: THPT Nguyen Duc Canh
Bài viết: 6
Cảm ơn: 0
Được cảm ơn 4 lần trong 3 bài
Mặc định

Function BCNN(a,b:Integer):Integer
Var oa,ob:Integer;
Begin
Oa:= a; ob:= b;
while (a <> b) do
if (a <= b) then
a:=a+oa
else
b:=b+ob;
BCNN:=a;
End;
khoipm is offline   Trả lời kèm trích dẫn
Old 02-11-2010, 20:44   #30
lulithichhat
Khách
 
Bài viết: n/a
Cool

B1: Bắt đầu, Nhập M, N
B2: Gán M*N cho BCNN
B3: Nếu M=N thì đến B6
B4: Nếu M>N thì gán M-N cho M rồi trở lại B3
B5: Gán N-M cho N rồi trở lại B3
B6: Gán BCNN/M cho BCNN
B7: Xuất BCNN, Kết thúc
  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
bút pháp ước lệ tượng trưng của Nguyễn Du qua đoạn trích" Thúc Sinh từ biệt Thuý Kiều hangnga14 Ngữ Văn 0 20-04-2009 21:31
Thuật tóan số nguyên tố - Tin học 10 huynhtanthong Tin Học 14 28-11-2008 15:26
Thuật toán tìm các số nguyên tố nhỏ hơn N Thu Ha Tin Học 4 31-10-2008 00:12
Mọi người cùng chung tay nguyenhonghanh Lịch Sử 0 08-09-2008 13:21

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


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