Kết quả 1 đến 10 của 12
-
07-23-2016, 10:03 AM #1Junior Member
- 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 ạ.View more random threads:
- Mong làm wen với các pạn gái ở phước long!!!
- Tạo hiệu ứng âm thanh trong turbo pascal
- Giúp em làm bài tập lập trình Pascal
- Cùng làm quen nhe
- Đề cương ôn tập Lập Trình Pascal thi Giữa Học Kì II (2) cho lớp 8 (2015-2016) Tham khảo
- Huyện Phước Long tổ chức thành công hội thi môi trường
- Nhờ các bác giúp cho lập trình pascal...
- Cùng tìm hiểu huyện phước long
- Bạn nào ở phước long vào đăng kí off tết nhé!
- ai giúp em 2 bài này với
-
07-23-2016, 04:08 PM #2Junior Member
- 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]
-
07-24-2016, 08:57 AM #3Silver member
- 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.
-
07-24-2016, 01:02 PM #4Junior Member
- 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.
-
07-24-2016, 02:00 PM #5Junior Member
- 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ợ ạ
-
07-24-2016, 02:16 PM #6Junior Member
- Ngày tham gia
- Aug 2015
- Bài viết
- 0
Gửi bởi phamthanhnhan
Mã:type arrayChar = array[0..255] of char; var a : ^arrayChar; begin new(a); a^[0] := '1'; dispose(a); end.
-
07-24-2016, 05:39 PM #7Silver member
- Ngày tham gia
- Sep 2015
- Bài viết
- 410
Gửi bởi tengiday
-
07-24-2016, 05:52 PM #8Junior Member
- Ngày tham gia
- Nov 2015
- Bài viết
- 0
Gửi bởi tengiday
-
07-25-2016, 08:06 AM #9Junior Member
- 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]
-
07-25-2016, 01:03 PM #10Junior Member
- Ngày tham gia
- Aug 2015
- Bài viết
- 0
Gửi bởi phamthanhnhan
- 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'.
Ý 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.
Pallet nhựa Trảng Bom giá rẻ chất lượng Pallet nhựa Trảng Bom là một sản phẩm chất lượng cao được sản xuất và phân phối tại địa bàn Trảng Bom, một huyện nằm ở tỉnh Đồng Nai, Việt Nam. Các pallet...
Pallet nhựa Trảng Bom giá rẻ chất...