Trang 1 của 2 12 CuốiCuối
Kết quả 1 đến 10 của 12
  1. #1
    Ngày tham gia
    Aug 2015
    Bài viết
    0

    Thuật toán tạo và tìm xâu đối xứng

    Thế nào là xâu đối xứng?
    - Xâu đối xứng là khi sau đó và một xâu viết ngược lại của xâu đó bằng nhau
    - VD : RADAR, TOT, GEDFDED, ... là các xâu đối xứng
    - Xâu chuỗi 'TOMATO' không phải là xâu đối xứng (TOMATO <> OTMAOT)
    - Ta có thể tạo được sau đối xứng với chuỗi tomato nếu thêm vào các kí tự hợp lí
    - VD: TOMATOOTMAOT (thêm OTMAOT vào phía sau), hoặc TOTMAMTOT (thêm T , M ,T vào các vị trí thích hợp)

    Đề bài: Hãy viết một chương trình để nhận biết xâu có phải là đối xứng hay không, nếu không thì cần thêm vào ít nhất bao nhiêu kí tự để xâu thành xâu đối xứng

    Em không suy nghĩ ra được giải thuật nào tối ưu hết ngoài vét cạn, nhưng như vậy rất tốn thời gian trong khi chuỗi lại có tối 255 kí tự, các bác có ai có thuật toán hay mong được chỉ giáo ạ.

  2. #2
    Ngày tham gia
    Dec 2015
    Bài viết
    5
    có thớt nào giúp em với ạ, em vô cùng biết ơn [IMG]images/icons/1.gif[/IMG]

  3. #3
    Ngày tham gia
    Apr 2016
    Bài viết
    42
    Mình nghĩ bài này có thể giải bằng quy hoạch động. Đây là ý tưởng của mình.
    F[i, j] = Số ký tự ít nhất cần thêm vào xâu S[i..j] để nó thành 1 xâu đối xứng.
    Ta có công thức như sau:
    F[i, i] = 0.
    F[i, j] = F[i + 1, j - 1] nếu S[i] = S[j].
    F[i, j] = min(F[i + 1, j], F[i, j - 1]) + 1 nếu S[i] <> S[j].

    Kết quả sẽ được lưu ở F[1, n], với n là chiều dài của chuỗi S.

  4. #4
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Đấy chỉ là ý tưởng của mình thôi vì mình đang bận, ko test kĩ đc.
    - F[i,i] = 0: cái này chắc dễ hiểu. Chuỗi có 1 ký tự luôn là đối xứng.
    - Nếu S[i] = S[j] (i < j), thì chúng ta có thể mở rộng chuỗi từ S[i + 1 .. j - 1] mà chuỗi vẫn là đối xứng.
    - Nếu S[i] <> S[j] (i < j), thì mình nghĩ có 2 trường hợp: mở rộng từ S[i + 1 .. j] hoặc S[i .. j - 1]; còn mình + 1 là do sự khác nhau giữa S[i] và S[j].

    Nếu chiều dài tối đa của S là 255 thì có thể dùng mảng 2 chiều này được (có thể dùng array of byte), nếu thiếu bộ nhớ thì cấp phát động thêm tí xíu chắc là chạy được. Nếu không thì bạn có thể dùng 3 mảng 1 chiềuu để lưu trữ.
    - Muốn in kết quả cụ thể ký tự nào thì khó hơn. Mình nghĩ chắc là phải lưu lại mảng dấu tại mỗi bước điền vào F. Khi đó phải cấp phát động mới đủ bộ nhớ. Đương nhiên, nếu dùng Free Pascal sẽ không bị sao cả.

    Bạn hiểu ý tưởng rồi góp ý cho mình.

  5. #5
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    em dùng pascal ạ, nên không cấp phát động [IMG]images/icons/1.gif[/IMG]
    còn việc dùng mảng để lưu char thì cũng đang xem xét, tuy vậy cũng có chút khó khăn ngay cả nhập từ bàn phím hay từ file ạ
    p/s: em đang test giải thật của bác, thanks bác đã hỗ trợ ạ

  6. #6
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi phamthanhnhan
    em dùng pascal ạ, nên không cấp phát động [IMG]images/icons/1.gif[/IMG]
    còn việc dùng mảng để lưu char thì cũng đang xem xét, tuy vậy cũng có chút khó khăn ngay cả nhập từ bàn phím hay từ file ạ
    p/s: em đang test giải thật của bác, thanks bác đã hỗ trợ ạ
    Pascal từ năm 1989 có cấp phát động mà. Bạn thử nhé:
    Mã:
    type arrayChar = array[0..255] of char;
    var a : ^arrayChar;
    begin
        new(a);
        a^[0] := '1';
        dispose(a);
    end.

  7. #7
    Ngày tham gia
    Sep 2015
    Bài viết
    410
    Trích dẫn Gửi bởi tengiday
    Mình nghĩ bài này có thể giải bằng quy hoạch động. Đây là ý tưởng của mình.
    F[i, j] = Số ký tự ít nhất cần thêm vào xâu S[i..j] để nó thành 1 xâu đối xứng.
    Ta có công thức như sau:
    F[i, i] = 0.
    F[i, j] = F[i + 1, j - 1] nếu S[i] = S[j].
    F[i, j] = min(F[i + 1, j], F[i, j - 1]) + 1 nếu S[i] <> S[j].

    Kết quả sẽ được lưu ở F[1, n], với n là chiều dài của chuỗi S.
    em cảm ơn nhiều lắm, nhưng mà em chưa hiểu rõ lắm, các giải thích thêm tí cho em tí nha, tại sao là mảng 2 chiều vậy bác ? [IMG]images/smilies/troll2/gach.png[/IMG]

  8. #8
    Ngày tham gia
    Nov 2015
    Bài viết
    0
    Trích dẫn Gửi bởi tengiday
    Đấy chỉ là ý tưởng của mình thôi vì mình đang bận, ko test kĩ đc.
    - F[i,i] = 0: cái này chắc dễ hiểu. Chuỗi có 1 ký tự luôn là đối xứng.
    - Nếu S[i] = S[j] (i < j), thì chúng ta có thể mở rộng chuỗi từ S[i + 1 .. j - 1] mà chuỗi vẫn là đối xứng.
    - Nếu S[i] <> S[j] (i < j), thì mình nghĩ có 2 trường hợp: mở rộng từ S[i + 1 .. j] hoặc S[i .. j - 1]; còn mình + 1 là do sự khác nhau giữa S[i] và S[j].

    Nếu chiều dài tối đa của S là 255 thì có thể dùng mảng 2 chiều này được (có thể dùng array of byte), nếu thiếu bộ nhớ thì cấp phát động thêm tí xíu chắc là chạy được. Nếu không thì bạn có thể dùng 3 mảng 1 chiềuu để lưu trữ.
    - Muốn in kết quả cụ thể ký tự nào thì khó hơn. Mình nghĩ chắc là phải lưu lại mảng dấu tại mỗi bước điền vào F. Khi đó phải cấp phát động mới đủ bộ nhớ. Đương nhiên, nếu dùng Free Pascal sẽ không bị sao cả.

    Bạn hiểu ý tưởng rồi góp ý cho mình.
    bác cho em hỏi là I, J chạy vòng lặp như thế nào ạ, và lúc khởi tạo thì i=1 hay i= length(s) div 2 ạ ?

  9. #9
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    em đã tìm ra thuật toán rồi ạ, thanks chủ thớt đã gợi ý, em dùng hai cái repeat until (trong c++ là do while) riêng biệt là xong ạ [IMG]images/icons/4.gif[/IMG]

  10. #10
    Ngày tham gia
    Aug 2015
    Bài viết
    0
    Trích dẫn Gửi bởi phamthanhnhan
    bác cho em hỏi là I, J chạy vòng lặp như thế nào ạ, và lúc khởi tạo thì i=1 hay i= length(s) div 2 ạ ?
    - Đầu tiên bạn nên khởi tạo F[i,i] = 0.
    - Sau đó xử lý trường hợp chuỗi S[i..i+1] (tức là chuỗi có chiều dài là 2).
    - Tiếp theo, để điền mảng F, bạn cần chạy theo "chiều dài của chuỗi bắt đầu từ 3" và "vị trí bắt đầu". Ví dụ code như thế này:
    Mã:
    for len := 3 to n do   // chiều dài của chuỗi cần xét, chuỗi có chiều dài từ 3 ký tự đến toàn bộ chuỗi
       for i := 0 to n - len     // vị trí bắt đầu xét
          F[i, i + len - 1] .....   // xét từ vị trí S[i], chuỗi con có chiều dài 'len'.
    Cuối cùng, kết quả sẽ nằm ở F[0, n-1].
    Ý tưởng là như thế, index của mình có thể bị lệch vì mình chuyển từ C++ sang, bạn kiểm tra lại giúp mình nhé. Để có thể thấy rõ hơn, tại mỗi bước 'len', chúng ta có thể in mảng F ra.

    PS: Một cách khác là nghĩ theo hướng xâu con chung có độ dài lớn nhất, gọi là K, như vậy kết quả là N - K. Cách làm này cũng sẽ dùng quy hoạch động.

 

 
Trang 1 của 2 12 CuốiCuối

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
Múi giờ GMT +7. Bây giờ là 02:17 PM.
Diễn đàn sử dụng vBulletin® Phiên bản 4.2.5.
Bản quyền của 2024 vBulletin Solutions, Inc. Tất cả quyền được bảo lưu.
Ban quản trị không chịu trách nhiệm về nội dung do thành viên đăng.