Thuật Toán Tạo Và Tìm Xâu đối Xứng | VFO.VN

Forum

• 
• Diễn đàn
• Mới nhất
• Công nghệ
• Điện thoại
• Máy tính
• Xe
• Thủ Thuật
• Hỏi đáp

Đăng nhập News Feed

Tìm kiếm

Mọi thứ Chủ đề Diễn đàn này Chủ đề này Chỉ tìm trong tiêu đề Bởi: Tìm Tìm kiếm nâng cao… Menu Đăng nhập Đăng ký Install the app Cài đặt You are using an out of date browser. It may not display this or other websites correctly.You should upgrade or use an alternative browser.

• Lập Trình - Đồ họa - Web
• Lập trình
• Pascal

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

• phamthanhnhan
• 23/7/16

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 ạ. P

phamthanhnhan

(｡◕‿‿◕｡) づ

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

tengiday

Happy life

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 = S[j]. F[i, j] = min(F[i + 1, j], F[i, j - 1]) + 1 nếu S <> 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. P

phamthanhnhan

(｡◕‿‿◕｡) づ

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 = S[j]. F[i, j] = min(F[i + 1, j], F[i, j - 1]) + 1 nếu S <> 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. Nhấn để mở rộng...

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 ? T

tengiday

Happy life

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

phamthanhnhan

(｡◕‿‿◕｡) づ

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ợ ạ T

tengiday

Happy life

phamthanhnhan: 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ợ ạ Nhấn để mở rộng...

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. P

phamthanhnhan

(｡◕‿‿◕｡) づ

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 = 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 <> 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 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. Nhấn để mở rộng...

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 ạ ? T

tengiday

Happy life

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 ạ ? Nhấn để mở rộng...

- Đầ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. Sửa lần cuối: 25/7/16 P

phamthanhnhan

(｡◕‿‿◕｡) づ

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++ T

tengiday

Happy life

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, trong khi của mình tới O(n^2) lận. Sửa lần cuối: 25/7/16 P

phamthanhnhan

(｡◕‿‿◕｡) づ

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 ạ Đăng nhập bằng tài khoản VFO hoặc Facebook Google

Bài viết mới nhất

• Kho truyện ngắn cực hay
  • shopoga
  • 17:22
• Sách Hay Mỗi Ngày
  • shopoga
  • 17:21
• Samsung công bố dòng sản phẩm màn hình mới
  • NTTH
  • 14:14
• T Xiaomi đã chọn ngày ra mắt Redmi Note 14 series tại Việt Nam
  • Tin Tức
  • 11:40
• Xiaomi ra mắt Redmi Note 14 Pro+ phiên bản quốc tế
  • Tuấn Hà
  • 11:22

Thống kê

Chủ đề 102,145 Bài viết 469,728 Thành viên 340,376 Thành viên mới nhất remy

Bài viết được quan tâm nhiều

• T Lộ diện Samsung Galaxy A06 5G
  • Tin Tức
  • 10:19
• T Xiaomi đã chọn ngày ra mắt Redmi Note 14 series tại Việt Nam
  • Tin Tức
  • 11:40
• T Lộ diện realme GT 7: màn hình AMOLED 1.5K, camera chính 50MP
  • Tin Tức
  • 09:27
• T Lộ diện realme 14 Pro 5G và 14 Pro+ 5G
  • Tin Tức
  • 08:51
• Samsung công bố dòng sản phẩm màn hình mới
  • NTTH
  • 14:14

Top