Đệ quy

[08520001]

Trong lập trình thuật toán có 1 kĩ thuật quan trọng là đệ quy
Đây là bài tập cơ bản để các bạn thử nghiệm:
Cho một xâu S chỉ gồm các chữ cái in hoa, 1 <= độ dài <= 9.

Yêu cầu:

1: Có bao nhiêu cách hoán vị các chữ cái của xâu S

2: Liệt kê các hoán vị đó theo thứ tự từ điển do lot.
Input

Gồm 1 dòng duy nhất chứa xâu S
Output

Dòng 1: Ghi số lượng hoán vị tìm được (K)

K dòng tiếp theo, mỗi dòng ghi một xâu hoán vị của xâu S theo đúng thứ tự từ điển
Example

Input:
ABAB
Output:
6
AABB
ABAB
ABBA
BAAB
BABA
BBAA

[08520001]

Đây là tài liệu về kỹ thuật đệ quy, các bạn có thể tham khảo tìm hiểu thêm

125.234.239.108/~hienlth/C/Ebooks/DocThem/GT_De_quy.ppt
http://vi.wikipedia.org/wiki/%C4%90%E1%BB%87_quy quan ao tre em.

[08520001]

Những bạn còn thắc mắc về kỹ thuật đệ quy thì hãy post ở đây để mọi người nghiên cứu nhé. quan ao.

[10520061]

chưa có ai giải nữa à.(

[11520673]

làm sao để ko trùng kết quả nếu có ký tự giống nhỉ =.=!

[08520059]

trong STL của c++ có hàm liệt kê các hoán vị
next_permutation(array, array+n) //với n là số phần tử của mảng.

Xem chi tiết tại đây.

[08520001]

Vì độ dài của chuỗi <= 9 nên có tối đa là 362880 chuỗi balo. Bạn có thể lưu lại để xem xét chuỗi vừa tạo ra đã có chưa.

[08520059]

làm sao để ko trùng kết quả nếu có ký tự giống nhỉ =.=!

Dùng STL set đi em. Nó không chứa các chuỗi giống nhau, đồng thời lưu theo thứ tự từ điển nữa.

[10520085]

nhưng như vậy là sử dụng hỗ trợ của C++.
Vậy có được không nhỉ

[08520001]

Được em ah. STL của C++ được phép sử dụng trong các kì thi mà tui xach.

[11520673]

em chỉ biết pascal thôi chưa rành C. Vậy sao cho ko trùng nhau đc, còn xếp theo ký tự từ điển nữa =.= ?? giờ mò sách C+ hả mấy a

[08520001]

Vậy em phải tự code 1 cấu trúc dữ liệu tên là binary search tree. Hoặc là em học C để làm bài này.vay dam. Vì trước sau j cũng phải học C mà.

[08520059]

em chỉ biết pascal thôi chưa rành C. Vậy sao cho ko trùng nhau đc, còn xếp theo ký tự từ điển nữa =.= ?? giờ mò sách C+ hả mấy a

Dùng STL vì nó đã có sẵn các cấu trúc dữ liệu mình cần nên rất tiện lợi. Nếu không có STL thì cách làm vẫn vậy nhưng phải code thêm cấu trúc dữ liệu thôi.

-dùng 1 mảng char 2 chiều để lưu các hoán vị (vì đề ra chỉ có 9 ký tự -> tối đa là 9! hoán vị)
-sinh ra tất cả các hoán vị, với mỗi hoán vị kiểm tra xem đã nằm trong mảng chưa, nếu chưa thì add vô.
--kiểm tra bằng cách duyệt từng vị trí của hoán vị đang xét với các hoán vị đã có trong mảng.
-sắp xếp theo thứ tự từ điển thì cũng như sort 1 mảng số nguyên tăng dần, nhưng ở đây mình so sánh các hoán vị với nhau, nếu hv1 > hv2 thì swap(hv1, hv2).

Những thao tác trên đây thì STL của C++ đã code sẵn rồi, nên tiện lợi là ở chỗ này.

[10520085]

trong STL của c++ có hàm liệt kê các hoán vị
next_permutation(array, array+n) //với n là số phần tử của mảng.

Xem chi tiết tại đây.

Dùng cách này mà liệt kê thì hình như hơi lâu thì phải

[08520001]

Hi. Không lâu đâu em. Tại vì độ dài chỉ có 9 là tối đa thôi. Không tin em có thể thử mà thoi trang nam.