Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: Số Tập Hợp Con Của 1 Tập Hợp !

  1. #1
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Mặc định Số Tập Hợp Con Của 1 Tập Hợp !

    Hôm trước Mem nào hỏi kid bài này . Kid bảo search giúp mà kid cũng không thấy đâu chắc là kém rồi. Tuy nhiên hôm nay viết lên thế này vì câu hỏi của bạn còn mập mờ quá kid không biết trả lời sao cho thấu đáo vì năng lực có hạn .

    Ví như số phần tử là một số cố định kid giả sử là 4 thì đơn giản bạn có thể làm như sau :

    Cho 4 còn for chạy từ 0 -> 4 với các biến là i ,j,k,l nếu mà i,j,k,l này khác nhau thì đó là 1 hoán vị cần tìm và cậu sẽ in ra được đúng 24 hoán vị .

    Tuy nhiên nếu người ta yêu cầu là đến 10 phần tử thì sao số hoán vị chắc chắn là rất lớn 10! và đặc biệt thuật toán trên mắc nhiều sai sót .

    Điều đó vẫn chưa là ghê ghớm và bi giờ thì người ta nói rằng tui thích nhập bi nhiêu là quyền của tui thì chúng ta lại càng bối rối vì không thế biết mà dùng bao nhiều vòng for được. Kid cũng có suy nghĩ đến cái thuật toán như thế này . Không biết là giúp gì được U đọc và coi thử nhé . Nói trước là kid không viết code ra được chắc là nhờ anh em .

    Giả sử ta có mảng 4 phần tử ( bi nhiêu cũng được không quan trọng )
    Ta sẽ có một ma trận như sau :
    Tớ giả sử các chỉ mục của mảng là từ a[1] -> a[4] để cậu dễ hiểu .

    PHP Code:
    1 2 3 4
    2 3 4 1
    3 4 1 2
    4 1 2 3 
    Để tạo cái ma trận này thì đơn giản thôi đúng không >
    Giờ tiếp tục nè ta thấy là số hoán vị của a[4] lúc này sẽ bằng tổng số hoán vị của từng hàng trong ma trận cộng lại đúng không ?
    Cụ thể là !A[4] = !M[1][] + !M[2][] + !M[3][] + !M[4][] ;

    Xét một hàng bất kì ví dụ là hàng thứ nhất M[1][] ;

    Ta có số hoán vị trong đó sẽ như sau :

    M[1][1] + !M[1][2 -> 4];

    Mà số hoán vị từ M[2 -4] sẽ là tổng số hoán vị của 1 ma trận : Cụ thể như sau :
    PHP Code:
    2 3 4
    3 4 2
    4 2 3 
    Mà số hoán vị của ma trận này lại bằng số hoán vị của tất cả các dòng của nó .

    Cậu có thấy là nó lặp lại không nào ! Hãy thử suy nghĩ và viết ra code nhé . Cuối cùng tớ sẽ dùng cách trên để liệt kê số hoán vị của 3 phần tử . Coi thử nhé .

    int a[3] ;

    PHP Code:
    0 1 2
    1 2 0
    2 0 1 
    Hoán vị của 0 1 2 Gồm :
    0 +
    1 2
    2 1

    = 0 1 2 và 0 2 1

    Tiếp tục hoán vị của 1 2 0 là ....
    Tổng hợp lại ta sẽ có 6 hoán vị là : ....

    Hi vọng là có cách khác hay hơn hoặc có anh em nào hiện thực thành code hoặc là bạn quyết định không viết bài này nữa he he
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #2
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    - Số tập con của một tập hợp: Mỗi một tập con của tập có n phần tử có thể được mô tả bằng một chuỗi nhị phân s độ dài n theo quy ước s[i]=1 nghĩa là phần tử thứ i trong số n phần tử có nằm trong tập con này. có 2^n chuỗi khác nhau như vậy--> có 2^n tập con
    -
    Điều đó vẫn chưa là ghê ghớm và bi giờ thì người ta nói rằng tui thích nhập bi nhiêu là quyền của tui thì chúng ta lại càng bối rối vì không thế biết mà dùng bao nhiều vòng for được
    Có thể dùng đệ quy để giải quyết, sau đó khử đệ quy chỉ còn lại while và for
    - Cách bạn trình bày để suy nghĩ thêm đã

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Lâu lắm mới thấy bác HaiLoc lên ! Thật là vui quá đi .

  4. #4
    Ngày gia nhập
    07 2006
    Bài viết
    166

    Số tập con của một tập n phần tử là 2^n (lí thuyết tập hợp rồi), chả làm gì phải tính toán cho mất công )

  5. #5
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Em cố một bài này cũng về tập hợp nhưng không biết phải giải quyết như thế nào. Người ta cho một chuỗi có n chữ cái ví dụ như "Xin_Chao". Các hoán vị của chuỗi này có tính thứ tự nghĩa là có thể nói "Xin_Chao" > "Chao_Xin" (kiểu như so sánh chuỗi vậy). Như vậy toàn bộ các hoán vị của chuỗi trên sẽ tạo nên một dãy sắp xếp tăng. Đề bài yêu cầu: cho vào 1 chuỗi là hoán vị của chuỗi đã cho ban đầu, hãy tìm vị trí của nó trong chuỗi các hoán vị đã sắp xếp kia.

  6. #6
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Mặc định Số Tập Hợp Con Của 1 Tập Hợp !

    Số tập con của một tập n phần tử là 2^n (lí thuyết tập hợp rồi), chả làm gì phải tính toán cho mất công )
    Không vấn đề Vinhie47 nói thì ko đúng ý của mình . Mình đang hỏi là số hoán vị và liệt kê tất cả các hoán vị của nó . Nếu giải quyết được câu hỏi này thì có thể trả lời cho câu của HaiLoc.

  7. #7
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Xét về dạng bài thì tím số phần tử (nghĩa là chỉ cần trả lời 2^n) thuộc vào lớp bài toán đếm, còn tìm từng phần tử ra là lớp bài toán liệt kê. Cụ thể bài liệt kê hoán vị này có được nói đến trong giáo trình DASP ( cái này em đã đưa lên ở mục Những tài liệu cần thiết để học giải thuật bên box Giải thuật ). Tuy nhiên vì phương pháp liệt kê dễ dẫn đến bùng nổ tổ hợp nên đó là giải pháp cuối cùng cho cấc bài tỏ hợp. Bài toán em đưa ra chính là ví dụ như vậy. Cái khó không phải là không tìm được cách giải quyết mà là có quá nhiều cấu hình cần phải xét. Chỉ một chuỗi độ 10 chữ cái cũng có đến 10! hoán vị.

  8. #8
    Ngày gia nhập
    07 2006
    Bài viết
    166

    Trích dẫn Nguyên bản được gửi bởi hailoc12 Xem bài viết
    Em cố một bài này cũng về tập hợp nhưng không biết phải giải quyết như thế nào. Người ta cho một chuỗi có n chữ cái ví dụ như "Xin_Chao". Các hoán vị của chuỗi này có tính thứ tự nghĩa là có thể nói "Xin_Chao" > "Chao_Xin" (kiểu như so sánh chuỗi vậy). Như vậy toàn bộ các hoán vị của chuỗi trên sẽ tạo nên một dãy sắp xếp tăng. Đề bài yêu cầu: cho vào 1 chuỗi là hoán vị của chuỗi đã cho ban đầu, hãy tìm vị trí của nó trong chuỗi các hoán vị đã sắp xếp kia.
    Chả hiểu ý này lắm, nếu một khi đã sắp xếp được rồi thì tìm kiếm nhị phân thôi. Hay ý cậu là liệt kê ra các hoán vị của chuỗi theo thứ tự (tăng, giảm)?

  9. #9
    Ngày gia nhập
    04 2007
    Bài viết
    16

    Em cố một bài này cũng về tập hợp nhưng không biết phải giải quyết như thế nào. Người ta cho một chuỗi có n chữ cái ví dụ như "Xin_Chao". Các hoán vị của chuỗi này có tính thứ tự nghĩa là có thể nói "Xin_Chao" > "Chao_Xin" (kiểu như so sánh chuỗi vậy). Như vậy toàn bộ các hoán vị của chuỗi trên sẽ tạo nên một dãy sắp xếp tăng. Đề bài yêu cầu: cho vào 1 chuỗi là hoán vị của chuỗi đã cho ban đầu, hãy tìm vị trí của nó trong chuỗi các hoán vị đã sắp xếp kia.
    Đây là bài toán không khó mà. Mình nói thế này để bạn thử cài đặt nhé: giả sử có hoán vị mở đầu là 123, khi đó số hoán vị mà có 1 đứng đầu tiên là 2! = 2, trong các hoán vị đó, số hoán vị có 2 đứng thứ 2 là 1! = 1.... nghĩa là mình sẽ xét vị trí thứ từ trái sang i, tính xem có bao nhiêu hoán vị nếu vị trí ấy mang ký tự j rồi trừ dần đi, cuối cùng sẽ biết hoán vị thứ k là hoán vị nào.
    Hoàn toàn tương tự, nhưng ngược lại với việc từ một hoán bị s bất kỳ tìm vị trí của nó.
    Bài toán này không phải sinh tất cả các hoán vị rồi sắp xếp để tìm kiếm.

  10. #10
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    To Vinhie47: Vấn đề chính là không thể liệt kê rồi sắp xếp và tìm kiếm được vì số cấu hình rất lớn. Với một chuỗi đơn giản 10 kí tự sẽ có tới 10!=3628800 chỉ duyệt qua một mảng như vậy chưa cần thực hiện bất cứ phép toán nào cũng mất mấy giây rồi.
    To hd_kinh_can: Cám ơn bác đã gợi ý, em đã làm đựơc rồi tuy nhiên theo một hướng hơi khác chút ít. Ví dụ xét chuỗi hello, em sắp xếp lại các chữ cái của nó theo thứ tự sau: ehll0. Sau đó xét từ trái sang phải chuỗi hello ban đầu. Ta thấy trước chữ h có 1 chữ e do đó để đến cấu hình bắt đầu bằng h thì phải trải qua tất cả 4! cấu hình bắt đầu bằng e. Ta cộng thêm 4! vào vị trí của chuỗi cần tìm, đồng thời xoá h ra khỏi danh sách đã sắp xếp trên. Làm đến hết cộng thêm 1 ta có được vị trí cấu hình cần tìm.
    Dưới đây em gửi kèm chương trình đã cài đặt. Một chương trình viết theo phương pháp liệt kê, một chương trình viết theo phương pháp trên. Các bác xem thử, so sánh tốc độ để hiểu rõ thêm về baì toán này.
    Attached Files Attached Files
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn