Diễn Đàn MathScopeDiễn Đàn MathScope
  Diễn Đàn MathScope
Ghi Danh Hỏi/Ðáp Thành Viên Social Groups Lịch Ðánh Dấu Ðã Ðọc

Go Back   Diễn Đàn MathScope > Đại Học Và Sau Đại Học/College Playground > Logic, Tập Hợp, Toán Rời Rạc

News & Announcements

Ngoài một số quy định đã được nêu trong phần Quy định của Ghi Danh , mọi người tranh thủ bỏ ra 5 phút để đọc thêm một số Quy định sau để khỏi bị treo nick ở MathScope nhé !

* Nội quy MathScope.Org

* Một số quy định chung !

* Quy định về việc viết bài trong diễn đàn MathScope

* Nếu bạn muốn gia nhập đội ngũ BQT thì vui lòng tham gia tại đây

* Những câu hỏi thường gặp

* Về việc viết bài trong Box Đại học và Sau đại học


Trả lời Gởi Ðề Tài Mới
 
Ðiều Chỉnh Xếp Bài
Old 05-06-2011, 06:39 AM   #1
tranbatphong
Banned
 
Tham gia ngày: Apr 2011
Bài gởi: 165
Thanks: 220
Thanked 48 Times in 30 Posts
Một số thuật toán tìm phần tử kế tiếp

Bạn nào biết các thuật toán sau thì trình bày rõ các bước mình tham khảo với:
1. Thuật toán sinh kế tiếp xâu ở sau xâu a có độ dài n?
2. Thuật toán sinh kế tiếp tổ hợp chấp k của tập n số tự nhiên?
3. Thuật toán sinh kế tiếp hoán vị của tập n số tự nhiên?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
tranbatphong is offline   Trả Lời Với Trích Dẫn
Old 05-06-2011, 06:59 AM   #2
Galois_vn
+Thành Viên+
 
Tham gia ngày: Nov 2007
Đến từ: Konoha
Bài gởi: 899
Thanks: 372
Thanked 362 Times in 269 Posts
Bạn làm rõ cụm từ "sinh kế tiếp " nhen

1. xâu xem như dãy các bit: cộng thêm bit 1 vào.
2. $C_n^{k+1}=\frac{n-k}{k+1}C_n^k $
3. $(n+1)!=(n+1)n! $
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: Galois_vn, 05-06-2011 lúc 07:03 AM
Galois_vn is offline   Trả Lời Với Trích Dẫn
Old 05-06-2011, 08:57 PM   #3
tranbatphong
Banned
 
Tham gia ngày: Apr 2011
Bài gởi: 165
Thanks: 220
Thanked 48 Times in 30 Posts
Trích:
Nguyên văn bởi Galois_vn View Post
Bạn làm rõ cụm từ "sinh kế tiếp " nhen

1. xâu xem như dãy các bit: cộng thêm bit 1 vào.
2. $C_n^{k+1}=\frac{n-k}{k+1}C_n^k $
3. $(n+1)!=(n+1)n! $
Tức tìm phần tử liền kề với 1 phần tử cho trước ấy bạn.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
tranbatphong is offline   Trả Lời Với Trích Dẫn
Old 05-06-2011, 09:04 PM   #4
huynhcongbang
Administrator

 
huynhcongbang's Avatar
 
Tham gia ngày: Feb 2009
Đến từ: Ho Chi Minh City
Bài gởi: 2,413
Thanks: 2,165
Thanked 4,188 Times in 1,381 Posts
Gửi tin nhắn qua Yahoo chát tới huynhcongbang
Trích:
Nguyên văn bởi tranbatphong View Post
Bạn nào biết các thuật toán sau thì trình bày rõ các bước mình tham khảo với:
1. Thuật toán sinh kế tiếp xâu ở sau xâu a có độ dài n?
2. Thuật toán sinh kế tiếp tổ hợp chấp k của tập n số tự nhiên?
3. Thuật toán sinh kế tiếp hoán vị của tập n số tự nhiên?
Các bài toán này mình nghĩ đều có giải thích rõ trong cuốn "Giáo trình thuật toán" của thầy Lê Minh Hoàng, bạn xem thử trong chương 1 nha!
Các bài toán minh họa bằng Pascal hoặc mã giả, nếu bạn muốn hiện thực bằng ngôn ngữ khác thì mình sẽ gửi cái khác.

http://www.mediafire.com/?w1m41hvywxy
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
huynhcongbang is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to huynhcongbang For This Useful Post:
tranbatphong (05-06-2011)
Old 05-06-2011, 11:02 PM   #5
tranbatphong
Banned
 
Tham gia ngày: Apr 2011
Bài gởi: 165
Thanks: 220
Thanked 48 Times in 30 Posts
1. Thuật toán sinh kế tiếp xâu ở sau xâu $a $ có độ dài $n $:
Xét từ cuối dãy về đầu, tìm gặp số 0 đầu tiên:
+) Nếu thấy thì thay bởi 1 và thay các phần tử phí sau bởi 0.
+) Không thấy thì dừng lại, đây là cấu hình cuối cùng.

2. Thuật toán sinh kế tiếp tổ hợp chập $k $ của tập $n $ số tự nhiên:
Xét từ cuối dãy về đầu, tìm phần tử $x_i $ chưa đạt tới $n-k+i $:
+) Nếu thấy thì tăng $x_i $ đó lên 1 và đặt tất cả các phần tử phía sau bằng giới hạn dưới.
+) Không thấy thì dừng lại, đây là cấu hình cuối cùng.

3. Thuật toán sinh kế tiếp hoán vị của tập $n $ số tự nhiên:
Xác định đoạn cuối giảm dần dài nhất, tìm phần tử $x_i $ đứng liền trước đoạn cuối đó:
+) Nếu tìm thấy thì trong đoạn giảm dần, tìm phần tử $x_k $ nhỏ nhất thỏa mãn $x_k>x_i $; đảo $x_k $ và $x_i $ rồi lật ngược đoạn cuối (từ $x_{i+1} $ đến $x_k $) giảm dần thành tăng dần.
+) Không thấy thì dừng lại, đây là cấu hình cuối cùng.

Các bạn check dùm!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: tranbatphong, 05-06-2011 lúc 11:19 PM
tranbatphong is offline   Trả Lời Với Trích Dẫn
Old 06-06-2011, 09:00 AM   #6
tranbatphong
Banned
 
Tham gia ngày: Apr 2011
Bài gởi: 165
Thanks: 220
Thanked 48 Times in 30 Posts
Mình vừa đi thi về, bó tay bài ni:
Bài toán. Xây dựng 1 thuật toán in ra tất cả các biển số xe theo quy cách biển có dạng $X x1x2x3.x4x5 $ (dấu chấm chạy lòng vòng ngăn cách 5 số chứ không phải chỉ ở vị trí thứ 3 đó) với X là 1 trong các chữ cái tiếng Anh, $x_i $ là các chữ số, mỗi biển số thuộc một dòng?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: tranbatphong, 06-06-2011 lúc 06:08 PM
tranbatphong is offline   Trả Lời Với Trích Dẫn
Old 06-06-2011, 10:53 AM   #7
Galois_vn
+Thành Viên+
 
Tham gia ngày: Nov 2007
Đến từ: Konoha
Bài gởi: 899
Thanks: 372
Thanked 362 Times in 269 Posts
Trích:
Nguyên văn bởi tranbatphong View Post
Mình vừa đi thi về, bó tay bài ni:
Bài toán. Xây dựng 1 thuật toán in ra tất cả các biển số xe theo quy cách biển có dạng $X x1x2x3.x4x5 $ với X là 1 trong các chữ cái tiếng Anh, $x_i $ là các chữ số, mỗi biển số thuộc một dòng?
Bài này, dùng cách đơn giản nhất (= ngu nhất )6 vòng for .
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: Galois_vn, 06-06-2011 lúc 11:03 AM
Galois_vn is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to Galois_vn For This Useful Post:
tranbatphong (06-06-2011)
Old 06-06-2011, 06:09 PM   #8
tranbatphong
Banned
 
Tham gia ngày: Apr 2011
Bài gởi: 165
Thanks: 220
Thanked 48 Times in 30 Posts
Trích:
Nguyên văn bởi Galois_vn View Post
Bài này, dùng cách đơn giản nhất (= ngu nhất )6 vòng for .
Bạn nói rõ hơn được không?
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
tranbatphong is offline   Trả Lời Với Trích Dẫn
Old 06-06-2011, 06:46 PM   #9
Galois_vn
+Thành Viên+
 
Tham gia ngày: Nov 2007
Đến từ: Konoha
Bài gởi: 899
Thanks: 372
Thanked 362 Times in 269 Posts
Trích:
Nguyên văn bởi tranbatphong View Post
Bạn nói rõ hơn được không?
Trích:
xa='A';
.for X=0:25
......for $ x_1=0\to 9 $
........... for $ x_2=0\to 9 $
...................... for $ x_3=0\to 9 $
................................for $ x_4=0\to 9 $
...................................... for $ x_5=0\to 9 $
.................................................. ...In $xa+X, x_1, x_2, x_3, x_4, x_5 $ //Phép cộng hình thức, dùng lệnh tương ứng.
.................................................. ....và xuống dòng.
........................................end $x_5 $
.................................end $x_4 $
.......................end $x_3 $
............end $x_2 $
.......end $x_1 $
.end X
Bạn chỉnh chút thì sẽ in đầy đủ kí tự X là hoa lẫn thường.

ps: Như tui nói, cách này ko hay!
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 

thay đổi nội dung bởi: Galois_vn, 06-06-2011 lúc 06:53 PM
Galois_vn is offline   Trả Lời Với Trích Dẫn
Old 19-05-2012, 03:22 PM   #10
franciscokison
+Thành Viên+
 
franciscokison's Avatar
 
Tham gia ngày: May 2009
Đến từ: Hanoi University of Science and Technology
Bài gởi: 652
Thanks: 120
Thanked 249 Times in 181 Posts
Gửi tin nhắn qua MSM tới franciscokison Gửi tin nhắn qua Yahoo chát tới franciscokison
Icon1

Trích:
Nguyên văn bởi tranbatphong View Post
Mình vừa đi thi về, bó tay bài ni:
Bài toán. Xây dựng 1 thuật toán in ra tất cả các biển số xe theo quy cách biển có dạng $X x_1 x_2 x_3\cdot x_4 x
_5 $ (dấu chấm chạy lòng vòng ngăn cách 5 số chứ không phải chỉ ở vị trí thứ 3 đó) với X là 1 trong các chữ cái tiếng Anh, $x_i $ là các chữ số, mỗi biển số thuộc một dòng?
Viết dạng mã giả cho dễ hiểu:
PHP Code:
function Print_Number_Plate();
begin:
    
integer L=0;R=0;
    
char np 'A 000 00'X;
    while 
X in A to Z do
         while 
0<= <=999 do
             while 
0<= <=99 do
                print(
np L R); next// Ngắt dòng
                
R=R+1// tức là R=R+1
             
endwhile;
             
L++; // tức là L=L+1
         
endwhile;
    endwhile;
end
Thuật toán là: In tuần tự từ trái sang phải X từ A đến Z. Với mỗi điều kiện X trong vòng lặp chuỗi 3 chữ số sẽ được in theo thứ tự tăng dần, tương tự cho hai chữ số còn lại chú ý là phép so sánh mất thời gian ít hơn phép gán và hạn chế vòng lặp sẽ hạn chế được nhiều phép ss và phép gán.

Có thuật toán in đệ qui:

PHP Code:
function Print_Number_Plate(char Xint NP=0);
begin:
        if 
NP<=99999 do 
            print( %
5d NP); //In ra NP với 5 chữ số;
            
NP=NP+1;
            
Print_Number_Plate(X,NP);
        
end if;
        else 
            
X next//Chuyển sang kí tự tiếp theo trong Alphabet
            
NP=0;
        
end else;
        
Print_Number_Plate(X,NP);
end

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
SvBk
[Only registered and activated users can see links. ][Only registered and activated users can see links. ]
$\begin{math}
\heartsuit\heartsuit\heartsuit
\end{math}. $
[Only registered and activated users can see links. ]

thay đổi nội dung bởi: franciscokison, 20-05-2012 lúc 04:10 PM
franciscokison is offline   Trả Lời Với Trích Dẫn
Old 19-05-2012, 04:19 PM   #11
franciscokison
+Thành Viên+
 
franciscokison's Avatar
 
Tham gia ngày: May 2009
Đến từ: Hanoi University of Science and Technology
Bài gởi: 652
Thanks: 120
Thanked 249 Times in 181 Posts
Gửi tin nhắn qua MSM tới franciscokison Gửi tin nhắn qua Yahoo chát tới franciscokison
Trích:
Nguyên văn bởi tranbatphong View Post
1. Thuật toán sinh kế tiếp xâu ở sau xâu $a $ có độ dài $n $:
Xét từ cuối dãy về đầu, tìm gặp số 0 đầu tiên:
+) Nếu thấy thì thay bởi 1 và thay các phần tử phí sau bởi 0.
+) Không thấy thì dừng lại, đây là cấu hình cuối cùng.

2. Thuật toán sinh kế tiếp tổ hợp chập $k $ của tập $n $ số tự nhiên:
Xét từ cuối dãy về đầu, tìm phần tử $x_i $ chưa đạt tới $n-k+i $:
+) Nếu thấy thì tăng $x_i $ đó lên 1 và đặt tất cả các phần tử phía sau bằng giới hạn dưới.
+) Không thấy thì dừng lại, đây là cấu hình cuối cùng.

3. Thuật toán sinh kế tiếp hoán vị của tập $n $ số tự nhiên:
Xác định đoạn cuối giảm dần dài nhất, tìm phần tử $x_i $ đứng liền trước đoạn cuối đó:
+) Nếu tìm thấy thì trong đoạn giảm dần, tìm phần tử $x_k $ nhỏ nhất thỏa mãn $x_k>x_i $; đảo $x_k $ và $x_i $ rồi lật ngược đoạn cuối (từ $x_{i+1} $ đến $x_k $) giảm dần thành tăng dần.
+) Không thấy thì dừng lại, đây là cấu hình cuối cùng.

Các bạn check dùm!
3. Thuật toán sinh hoán vị kế tiếp:
Code:
procedure Next_Permutation; // sinh hoán vị kế tiếp theo thứ tự từ điển của tập n phần tử
begin:
     //Tìm j là chỉ số lớn nhất thỏa mãn $a_j <a_{j+1} $
     j:=n-1;
     while $a_j > a_{j+1} $ do j:=j-1;
     /*Tìm đến $ a_k $ nhỏ nhất còn lớn hơn $a_j $ ở bên phải nó */
     k:=n; 
     while $a_j>a_k $ do k:=k-1;
     Swap($a_j,a_k $);// Đổi chỗ $a_j $ cho $a_k $
     /*Lật ngược đoạn từ $a_{j+1} $ đến $a_n $*/
     r:=n;
     s:=j+1;
     while r>s do
         begin:
             Swap(a_r,a_s);
             r:=r-1;
             s:=s-1;
         end;
end;
Tóm tắt thuật toán:
- Duyệt từ phải qua trái, tìm j là chỉ số lớn nhất thỏa mãn $a_j <a_{j+1} $
- Tìm đến $ a_k $ nhỏ nhất còn lớn hơn $a_j $ ở bên phải nó
- Đổi chỗ $a_j $ với $a_k $
- Lật ngược đoạn từ $a_{j+1} $ đến $a_n $

2. Liệt kê tập con m phần tử của tập n phần tử (chỉ nêu thuật toán thôi, code cũng tương tự )
- Tìm từ bên phải dãy $a_1,a_2,..,a_m $ phần tử $a_j \neq n-m+i, $
- thay $a_j $ bởi $a_{j+1} $
- Thay $a_i $bơi $a_j+i-j $ với $i=j+1,j+2,...,m $

1. Liệt kê tất cả các dãy nhị phân độ dài n, thuật toán sinh kế tiếp như sau:
Code:
procadure Next_Bit_String;
begin:
     i:=n;
     /* Duỵệt từ bên phải sang trái thỏa mãn $b_i $ =0
     Sau đó đảo gán các bit bên phải $b_i $ bằng 0 */
     while $b_i $=1 do 
        begin
            b_i=0;
            i:=i-1;
         end;
      endwhile;
      b_i=1; 
end;

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]
 
__________________
SvBk
[Only registered and activated users can see links. ][Only registered and activated users can see links. ]
$\begin{math}
\heartsuit\heartsuit\heartsuit
\end{math}. $
[Only registered and activated users can see links. ]
franciscokison is offline   Trả Lời Với Trích Dẫn
The Following User Says Thank You to franciscokison For This Useful Post:
thinhptnk (19-05-2012)
Trả lời Gởi Ðề Tài Mới

Bookmarks

Ðiều Chỉnh
Xếp Bài

Quuyền Hạn Của Bạn
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is Mở
Smilies đang Mở
[IMG] đang Mở
HTML đang Tắt

Chuyển đến


Múi giờ GMT. Hiện tại là 07:57 PM.


Powered by: vBulletin Copyright ©2000-2024, Jelsoft Enterprises Ltd.
Inactive Reminders By mathscope.org
[page compression: 93.49 k/105.93 k (11.74%)]