|
|
|
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é ! * 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 |
| Ðiều Chỉnh | Xếp Bài |
05-06-2011, 06:39 AM | #1 |
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? |
05-06-2011, 06:59 AM | #2 |
+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! $ thay đổi nội dung bởi: Galois_vn, 05-06-2011 lúc 07:03 AM |
05-06-2011, 08:57 PM | #3 |
Banned Tham gia ngày: Apr 2011 Bài gởi: 165 Thanks: 220 Thanked 48 Times in 30 Posts | |
05-06-2011, 09:04 PM | #4 | |
Administrator | Trích:
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 | |
The Following User Says Thank You to huynhcongbang For This Useful Post: | tranbatphong (05-06-2011) |
05-06-2011, 11:02 PM | #5 |
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! thay đổi nội dung bởi: tranbatphong, 05-06-2011 lúc 11:19 PM |
06-06-2011, 09:00 AM | #6 |
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? thay đổi nội dung bởi: tranbatphong, 06-06-2011 lúc 06:08 PM |
06-06-2011, 10:53 AM | #7 |
+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ài này, dùng cách đơn giản nhất (= ngu nhất )6 vòng for . thay đổi nội dung bởi: Galois_vn, 06-06-2011 lúc 11:03 AM |
The Following User Says Thank You to Galois_vn For This Useful Post: | tranbatphong (06-06-2011) |
06-06-2011, 06:09 PM | #8 |
Banned Tham gia ngày: Apr 2011 Bài gởi: 165 Thanks: 220 Thanked 48 Times in 30 Posts | |
06-06-2011, 06:46 PM | #9 | |
+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:
ps: Như tui nói, cách này ko hay! thay đổi nội dung bởi: Galois_vn, 06-06-2011 lúc 06:53 PM | |
19-05-2012, 03:22 PM | #10 | |
+Thành Viên+ | Trích:
PHP Code: Có thuật toán in đệ qui: PHP Code: __________________ [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 | |
19-05-2012, 04:19 PM | #11 | |
+Thành Viên+ | Trích:
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; - 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; | |
The Following User Says Thank You to franciscokison For This Useful Post: | thinhptnk (19-05-2012) |
Bookmarks |
Ðiều Chỉnh | |
Xếp Bài | |
|
|