Trang 2 của 2 Đầu tiênĐầu tiên 12
Kết quả 11 đến 12 của 12
  1. #11
    Ngày tham gia
    Sep 2015
    Bài viết
    71
    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++

  2. #12
    Ngày tham gia
    Nov 2015
    Bài viết
    7
    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("
    %d
    ", 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.

 

 
Trang 2 của 2 Đầu tiênĐầu tiên 12

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