Diễn Đàn MathScope - Một số thuật toán tìm phần tử kế tiếp

Diễn Đàn MathScope (http://forum.mathscope.org/index.php)

- Logic, Tập Hợp, Toán Rời Rạc (http://forum.mathscope.org/forumdisplay.php?f=132)

- - Một số thuật toán tìm phần tử kế tiếp (http://forum.mathscope.org/showthread.php?t=20278)

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?

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! $

Trích:

Nguyên văn bởi Galois_vn (Post 98438)

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.

Trích:

Nguyên văn bởi tranbatphong (Post 98436)

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. :hungry:

[Only registered and activated users can see links. Click Here To Register...]

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!

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?

Trích:

Nguyên văn bởi tranbatphong (Post 98681)

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 .

Trích:

Nguyên văn bởi Galois_vn (Post 98697)

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?

Trích:

Nguyên văn bởi tranbatphong (Post 98762)

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!

Trích:

Nguyên văn bởi tranbatphong (Post 98681)

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<= L <=999 do
             while 0<= R <=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 X, int 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;

Trích:

Nguyên văn bởi tranbatphong (Post 98646)

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;
      
      k:=n; 
      while $a_j>a_k $ do k:=k-1;
      Swap($a_j,a_k $);// Đổi chỗ $a_j $ cho $a_k $
      
      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ự :D)
- 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;
      
      while $b_i $=1 do 
         begin
             b_i=0;
             i:=i-1;
          end;
       endwhile;
       b_i=1; 
 end;