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 03-02-2010, 10:05   #1
Thuật toán sắp xếp tráo đổi
gvcnb gvcnb is offline 03-02-2010, 10:05

Thuật toán sắp xếp tráo đổi
- Bước 1: Nhập N và dãy A1,A2,…,AN;
- Bước 2: j<--N;
- Bước 3: Nếu j<2 thì đưa ra dãy A được sắp xếp rồi kết thúc;
- Bước 4: j<--j-1; i<--0;
- Bước 5: i<--i+1;
- Bước 6: Nếu i>j thì chuyển đến bước 3;
- Bước 7: Nếu Ai>Ai+1 thì đổi chỗ 2 giá trị này cho nhau;
- Bước 8: Quay lại bước 5;
( Theo thuật toán SGK tin học 10)
Sách lớp 11 chuyển thuật toán sang đoạn chương trình sau:
For j:=N downto 2 do
For i:=1 to j-1 do
Begin
T:=a[i];
a[i]:=a[i+1];
a[i+1]:=t;
end;
- Các thầy cô cho em một ví dụ và Test hộ nhé
- Em muốn hỏi là theo thuật toán thì có phải j tham gia vào lượt duyệt khi j=4 không? (Bước 4: j<--j-1; i<--0
- Câu lệnh For i:=1 to j-1 do tức là tại mỗi lượt duyệt thì i tăng từ 1 tới j-1. Nếu nhìn lại bảng em làm thì mâu thuẫn.
- Em kính mong các thầy cô có thể giải thích giúp em thuật toán này với và lấy luôn VD Test trên dãy cụ thể để em có thể quan sát và hiểu kĩ hơn

Chỉnh sửa lần cuối bởi gvcnb : 03-02-2010 lúc 11:07.

gvcnb
Lớp mầm
Points: 1,318, Level: 9 Points: 1,318, Level: 9 Points: 1,318, Level: 9
Activity: 1% Activity: 1% Activity: 1%
Gia nhập: 02-2010
Đơn vị: nghe an
Bài viết: 6
Cảm ơn: 5
Được cảm ơn 0 lần trong 0 bài
Lượt xem: 6720
Trả lời kèm trích dẫn
Old 03-02-2010, 11:21   #2
Nhất Điểm Tuyết
Cao học
Points: 6,132, Level: 23 Points: 6,132, Level: 23 Points: 6,132, Level: 23
Activity: 14% Activity: 14% Activity: 14%
 
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

Ý tưởng của thuật toán là tại mỗi giá trị của j, phần tử lớn nhất từ A[1] đến A[j] sẽ được "đùn" lên chiếm vị trí của A[j]. Xem ví dụ:

Source: http://en.wikipedia.org/wiki/Bubble_sort

Khi j = N = 5
( 5 1 4 2 8 ) --> ( 1 5 4 2 8 )
( 1 5 4 2 8 ) --> ( 1 4 5 2 8 )
( 1 4 5 2 8 ) --> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) --> ( 1 4 2 5 8 )

Khi j = N-1 = 4
( 1 4 2 5 8 ) --> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) --> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

Khi j = N-2 = 3
( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

Khi j = 2
( 1 2 4 5 8 ) --> ( 1 2 4 5 8 )

Hình minh họa:


PS: đoạn code ở sách lớp 11 chắc là thiếu cái này : Bước 7: Nếu Ai>Ai+1
__________________

giáo viên nghèo lười dạy
Nhất Điểm Tuyết is offline   Trả lời kèm trích dẫn
Đã cảm ơn Nhất Điểm Tuyết:
Old 03-02-2010, 11:41   #3
shsh
Lớp 2
Points: 2,548, Level: 14 Points: 2,548, Level: 14 Points: 2,548, Level: 14
Activity: 0% Activity: 0% Activity: 0%
 
shsh's Avatar
 
Gia nhập: 11-2009
Đơn vị: Lục Ngạn
Bài viết: 51
Cảm ơn: 87
Được cảm ơn 29 lần trong 20 bài
Mặc định

Sách lớp 11 không phải là thiếu mà là gvcnb ghi thiếu.
__________________
4.12:Trên đời có ba thứ dốt:
- Không biết những gì mình phải biết,
- Biết không rành những gì mình biết,
- Biết những điều mình không nên biết
.
_"Et_xi¯O¯No_Go"_

shsh is offline   Trả lời kèm trích dẫn
Old 03-02-2010, 12:07   #4
ttk41
Lớp 5
Points: 3,043, Level: 15 Points: 3,043, Level: 15 Points: 3,043, Level: 15
Activity: 14% Activity: 14% Activity: 14%
 
ttk41's Avatar
 
Gia nhập: 01-2010
Đơn vị: Coltech, VNU, hà Nội
Bài viết: 81
Cảm ơn: 23
Được cảm ơn 89 lần trong 44 bài
Mặc định

Vừa giở lại SGK trang 57 thì gvcnb thiếu mất 1 câu lệnh sau vòng for thứ 2, chắc là định thắc mắc chỗ này , nếu thêm vào chắc sẽ ko vấn đề gì. test và vd tuyết đưa ra khá cụ thể rồi ko cần nói thêm nữa nhưng khyên gvcnb tiếp cận các bài tin thì nên tiếp cận giải thuật (chủ yếu nghiên cứu thuật toán và tư tưởng ) sẽ nhàn hơn nhiều đấy
ttk41 is offline   Trả lời kèm trích dẫn
Old 03-02-2010, 12:15   #5
shsh
Lớp 2
Points: 2,548, Level: 14 Points: 2,548, Level: 14 Points: 2,548, Level: 14
Activity: 0% Activity: 0% Activity: 0%
 
shsh's Avatar
 
Gia nhập: 11-2009
Đơn vị: Lục Ngạn
Bài viết: 51
Cảm ơn: 87
Được cảm ơn 29 lần trong 20 bài
Mặc định

j ở trong thuật toán này là số phần tử chưa được sắp xếp về đúng vị trí, sau mỗi lượt sắp xếp thì có ít nhất một số được đưa về đúng vị trí nên j giảm đi 1. ví dụ Khi j=5 thì có 5 phần tử chưa được sắp xếp về đúng vị trí nên ta phải tìm ra phần tử lớn nhất trong 5 phần tử a[1] đến a[5](i nhận giá trị từ 1 đến j) để đưa về vị trí a[5](a[j]) tương tự khi j nhận các giá trị giảm dần, khi j nhận giá trị đến 2 thì chỉ còn 2 phần tử a[1] và a[2] cần sắp xếp nên ta chỉ cần so sánh a[1] với a[2] tìm ra phần tử lớn hơn đặt vào a[2]. vậy là dãy số đã được sắp xếp.
__________________
4.12:Trên đời có ba thứ dốt:
- Không biết những gì mình phải biết,
- Biết không rành những gì mình biết,
- Biết những điều mình không nên biết
.
_"Et_xi¯O¯No_Go"_

shsh is offline   Trả lời kèm trích dẫn
Old 19-02-2010, 13:01   #6
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

ở thuật toán sx trong SGK thì i tiến còn j lùi dần, sau 1 lượt chạy của i ta được số lớn nhất đẩy về cuối. Tôi thấy thuật toán sau học sinh dễ hiểu hơn:
For i:=1 To n-1 Do
For j:=i+1 To n Do
Begin
T:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
sau 1 lần duyệt ta được số nhỏ nhất đứng đầu dãy, các thầy cô cho ý kiến về thuật toán này nhé. Cảm ơn nhiều
tttymhy is offline   Trả lời kèm trích dẫn
Old 20-02-2010, 20:46   #7
shsh
Lớp 2
Points: 2,548, Level: 14 Points: 2,548, Level: 14 Points: 2,548, Level: 14
Activity: 0% Activity: 0% Activity: 0%
 
shsh's Avatar
 
Gia nhập: 11-2009
Đơn vị: Lục Ngạn
Bài viết: 51
Cảm ơn: 87
Được cảm ơn 29 lần trong 20 bài
Mặc định

Thuật toán của thầy thiếu mất câu lệnh so sánh giá trị của a[i] và a[j].
__________________
4.12:Trên đời có ba thứ dốt:
- Không biết những gì mình phải biết,
- Biết không rành những gì mình biết,
- Biết những điều mình không nên biết
.
_"Et_xi¯O¯No_Go"_

shsh is offline   Trả lời kèm trích dẫn
Old 21-02-2010, 14:20   #8
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

Cảm ơn thầy
For i:=1 To n-1 Do
For j:=i+1 To n Do
If a[i]>a[j] Then
Begin
T:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
tttymhy is offline   Trả lời kèm trích dẫn
Đã cảm ơn tttymhy:
Old 21-02-2010, 21:48   #9
pun_hatlot
Lớp chồi
Points: 8,339, Level: 27 Points: 8,339, Level: 27 Points: 8,339, Level: 27
Activity: 0% Activity: 0% Activity: 0%
 
pun_hatlot's Avatar
 
Gia nhập: 08-2008
Đơn vị: THPT Chuyên Sơn La
Bài viết: 16
Cảm ơn: 7
Được cảm ơn 19 lần trong 10 bài
Mặc định

Trên thực tế thì mọi người thường không hay sắp xếp kiểu tráo đổi như trong SGK mà chọn sắp xếp kiểu chọn "SelectionSort":
Ví dụ giáo viên thể dục cho HS xếp hàng từ thấp đến cao thì không giáo viên nào sắp xếp như SGK mà họ chọn cách sắp xếp kiểu chọn (tìm HS thấp nhất cho đứng đầu hàng, HS cao nhất cho đứng cuối hàng ....), ưu điểm vừa củng cố thuật toán tìm kiếm vừa thực tế.
Các bước tiến hành như sau:
Bước 1: i=1
Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]
Bước 3: Hoán vị a[min] và a[i]
Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2
Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.
Ví dụ: Cho dãy a = (12,2,8,5,1,6,4,15)
12 2 8 5 1 6 4 15
Lượt duyệt 1:1 2 8 5 12 6 4 15
Lượt duyệt 2:1 2 8 5 12 6 4 15
Lượt duyệt 3:1 2 4 5 12 6 8 15
Lượt duyệt 4:1 2 4 5 12 6 8 15
Lượt duyệt 5:1 2 4 5 6 12 8 15
Lượt duyệt 6:1 2 4 5 6 8 12 15
Lượt duyệt 7:1 2 4 5 6 8 12 15
Xem ví dụ:

Source : http://vi.wikipedia.org/wiki/S%E1%BA...p_ch%E1%BB%8Dn
Thuật toán:
for i:=1 to n-1 do
begin
jmin:=i;
for j:=i+1 to n do
if a[j]<a[jmin] then jmin:=j;
if jmin <>i then
Begin
T:=a[i];
a[i]:=a[jmin];
a[jmin]:=t;
end;
end;
Trong SGK tin học 10 (Tr 38-40) thì thuật toán sắp xếp bằng tráo đổi (Exchange Sort) được trình bày trước thuật toán tìm kiếm, các tài liệu khác cũng vậy !?!?!??? nên cứ theo thuật toán SGK là tốt nhất (không cần nhiều biết một là đủ)
__________________
DPun

Chỉnh sửa lần cuối bởi pun_hatlot : 21-02-2010 lúc 22:14
pun_hatlot is offline   Trả lời kèm trích dẫn
Đã cảm ơn pun_hatlot:
Old 22-02-2010, 18:33   #10
Vu_Truong
Lớp 10
Points: 80,910, Level: 88 Points: 80,910, Level: 88 Points: 80,910, Level: 88
Activity: 0% Activity: 0% Activity: 0%
 
Vu_Truong's Avatar
 
Gia nhập: 04-2008
Đơn vị: Trường THPT Tân Phong, Q.7, Tp.HCM
Bài viết: 221
Cảm ơn: 100
Được cảm ơn 208 lần trong 79 bài
Mặc định

Theo tôi nghĩ thì mình chỉ nên chọn một kiểu (duy nhất) sắp xếp nào đó giảng cho học sinh hiểu và chạy ví dụ bằng tay trên bảng, còn các kiểu sắp xếp khác chỉ nên giới thiệu sơ qua thuật toán thôi.
Nếu được thì minh nên minh họa trên máy chương trình chạy cụ thể (dạng đồ họa : thấy được từng bước sắp xếp như thế nào) để học sinh hiểu được từng bước sắp xếp như thế nào; có thể nhập nhiều lần để thấy được cách sắp xếp cụ thể hơn.
__________________
Mỗi khi đối mặt với thử thách hãy tìm kiếm một lối đi chứ không phải là một lối thoát
Vu_Truong is offline   Trả lời kèm trích dẫn
Đã cảm ơn Vu_Truong:
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
10 thủ thuật khi sử dụng đĩa DVD nhipsongthoicongnghe Tiện ích 0 24-11-2008 20:09
THCS Thuỷ Phương - Hương Thuỷ boc2008 Góc trò chuyện 1 27-09-2008 10:17
Giáo án Mỹ Thuật 6,7,8,9 CoSin Mỹ thuật 0 19-08-2008 16:10
Thủ thuật tạo đĩa cứu hộ máy tính bằng USB ledungthcs Hệ thống 0 14-06-2008 10:29
Tặng ThiHoa, Sương Ngọc và Thuận Thuỷ nguyennga Góc trò chuyện 6 22-04-2008 08:27

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


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