kết quả từ 1 tới 12 trên 12

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

  1. #1
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

    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 ạ.
    Quick reply to this message Trả lời       

  2. Đã cảm ơn phamthanhnhan:


  3. #2
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

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

    có thớt nào giúp em với ạ, em vô cùng biết ơn

  4. #3
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    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.
    LCD: 13.3" 1920x1080 IPS
    CPU: Intel i7 - 4700MQ (2.4 GHz - 3.4 GHz)
    GPU: Nvidia GTX 765m with GDDR5 2GB
    RAM: 2x8GB G.Skill 2133
    HDD: Samsung SSD 850 Pro 512 GB
    2 kg.

  5. 2 thành viên đã cảm ơn tengiday:


  6. #4
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

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

    Trích Nguyên văn bởi tengiday Xem bài viết
    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 ?

  7. Đã cảm ơn phamthanhnhan:


  8. #5
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Đấ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.

  9. Đã cảm ơn tengiday:


  10. #6
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

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

    em dùng pascal ạ, nên không cấp phát động
    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ợ ạ

  11. #7
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Trích Nguyên văn bởi phamthanhnhan Xem bài viết
    em dùng pascal ạ, nên không cấp phát động
    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.

  12. Đã cảm ơn tengiday:


  13. #8
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

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

    Trích Nguyên văn bởi tengiday Xem bài viết
    Đấ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 ạ ?

  14. #9
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Trích Nguyên văn bởi phamthanhnhan Xem bài viết
    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.

  15. Đã cảm ơn tengiday:


  16. #10
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

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

    mình đã test nhưng kết quả không như mong muốn, có thể mình sai ở chỗ nào đó
    tiện thể bác gửi cho em code của C++ được không ạ? Em cũng hiểu code c++

  17. #11
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 56897
    Giới tính: Nam
    Bài gửi
    881

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

    Mình viết nó như thế này:
    Mã:
    short palindrome(char * s, short len) {
        if (len == 1) return 0;
        short ** F = new short*[len];
        for (short i = 0; i < len; ++i) {
            F[i] = new short[len];
            F[i][i] = 0;
        }
    
        for (short i = 0; i < len - 1; ++i)
            if (s[i] == s[i + 1])
                F[i][i + 1] = 0;
            else
                F[i][i + 1] = 1;
        for (short i = 3; i <= len; ++i)
            for (short j = 0; j <= len - i; ++j)
                if (s[j] == s[j + i - 1])
                    F[j][j + i - 1] = F[j + 1][j + i - 2];
                else
                    F[j][j + i - 1] = min(F[j + 1][j + i - 1], F[j][j + i - 2]) + 1;
         
        short result = F[0][len - 1];
    
        for (short i = 0; i < len; ++i)
            delete[] F[i];
        delete[] F;
        return result;
    }
    Còn đây là test của mình. Có 62 ký tự khác nhau được lặp lại 80 lần. Kết quả là 4801.
    Mã:
    char * s = new char[4960];
    for (short i = 0; i < 80; ++i)
       for (short j = 33; j < 33 + 62; ++j)
        s[i * 62 + j - 33] = char(j);
    printf("\n%d\n", palindrome(s, 4960));
    delete[] s;
    Về tốc độ thì khá là tối ưu O(n^2), còn về memory thì vẫn chưa. Tối ưu về space phải là O(n), trong khi của mình tới O(n^2) lận.

  18. Đã cảm ơn tengiday:


  19. #12
    Ðến Từ
    TP. Hồ Chí Minh
    Thành Viên Thứ: 261001
    Giới tính: Nam
    Bài gửi
    1.008

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

    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 ạ