Bài tập cho các mem rèn luyện

[nhilangdinh]

Với yêu cầu Nguyên đưa ra + cách biến đổi như thế thì chắc là 1 lần phải biến đổi hết các kí tự trong bước đó chứ không thể biến đổi 1 kí tự 1 được, nếu biến đổi 1 kí tự 1 thì bài toán lại trở nên quá đơn giản với những ai đã có biết qua về đồ thị. Cái mình chưa hiểu là Nguyên làm thế nào biến đổi nhiều kí tự 1 lúc, chọn cách biến đổi các kí tự cái nào trước cái nào sau để số bước ít nhất.

[phiphi91]

Nhưng theo mình nghĩ thì nếu là thực hiện biến đổi một tập hợp gồm các kí tự cùng loại cùng lúc thì bài toán lại quá rắc rối, vì quá trình biến đổi của tập kí tự này còn phụ thuộc vào quá trình biến đổi của tập kí tự khác!

Mình lấy ví dụ nhé! Cho xâu ban đầu là "ac", bạn cần biến đổi thành "ca" và bạn có các phép biến đổi như sau: a -> b, b -> c, c -> e, e -> a. Như thế này thì sẽ phải dùng lần lần lượt các phép biến đổi sau:

a -> b | ac -> bc
c -> e | bc -> be
e -> a | be -> ba
b -> c | ba -> ca

Như ví dụ trên thì rõ ràng quá trình biến đổi các kí tự là đan xen nhau. Như vậy thuật toán sẽ rất rắc rối (và có thể sẽ là không có thuật toán cho bài toán như vậy)! Nếu dùng phép biến đổi thẳng a -> b -> c thì sẽ không thể biến đổi thành công được.

Còn một vấn đề nữa như thế này mà ta cũng có thể nhìn ra dễ dàng: Có phải cách biến đổi ngắn nhất bao giờ cũng tốt?

Bạn Nguyên gì đó đâu rồi??? Mau vào đây giúp bọn mình với [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[hoathachthao]

Đúng là rất rắc rối khi bài toán như vậy, nhưng bạn nghĩ xem, nếu là biến đổi từng kí tự 1 thì bài toán có phải trở nên "trẻ con" quá không, đơn giản chỉ là tìm đường đi từ 2 đỉnh trong 1 đồ thị, và lặp lại quá trình tìm như vậy với từng kí tự đang duyệt.
Nguyên cho ý kiến về bài tập của bạn đi, biến đổi từng kí tự hay là nhiều kí tự?

[evashopping]

Với yêu cầu Nguyên đưa ra + cách biến đổi như thế thì chắc là 1 lần phải biến đổi hết các kí tự trong bước đó chứ không thể biến đổi 1 kí tự 1 được, nếu biến đổi 1 kí tự 1 thì bài toán lại trở nên quá đơn giản với những ai đã có biết qua về đồ thị. Cái mình chưa hiểu là Nguyên làm thế nào biến đổi nhiều kí tự 1 lúc, chọn cách biến đổi các kí tự cái nào trước cái nào sau để số bước ít nhất.

Tại bạn nghĩ phức tạp quá, đề của mình khá là đơn giản mà [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG], chỉ đơn giản là biến đổi từng ký tự thôi. Nếu 1 lúc biến đổi cả 2 ký tự thì tính là 2 lần không phải 1 lần đâu nhé!

[handucquan]

Tại bạn nghĩ phức tạp quá, đề của mình khá là đơn giản mà [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG], chỉ đơn giản là biến đổi từng ký tự thôi. Nếu 1 lúc biến đổi cả 2 ký tự thì tính là 2 lần không phải 1 lần đâu nhé!

Có thế này thôi mà cũng phải cãi nhau mãi. [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
Lần sau Nguyên post đề rõ hơn chút nhé, không lại mất thời gian, nhức đầu lắm đấy.