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

[hvcuong]

c đã chuyển thành d rồi, làm sao về lại c để chuyển thành e đây? Cái quan trọng ở đây là tìm cách biến đổi thế nào để những phần tử như c được quay vòng nhanh nhất.

[Mr_Dam]

Sacklove bảo bài tớ ra là đơn giản mà không thấy thuật toán là sao nhỉ?
Ở những topic mình lập, mình chỉ cần các bạn đưa ra được thuật toán và chứng minh được tính đúng đắn của thuật toán, còn chương trình không quan trọng, vì đọc chương trình khó hiểu mà không test thì không biết đúng sai.

[greenhome]

Sacklove bảo bài tớ ra là đơn giản mà không thấy thuật toán là sao nhỉ?
Ở những topic mình lập, mình chỉ cần các bạn đưa ra được thuật toán và chứng minh được tính đúng đắn của thuật toán, còn chương trình không quan trọng, vì đọc chương trình khó hiểu mà không test thì không biết đúng sai.

theo em thấy thì bài này chỉ là đưa 1 đoạn mã vào ma trận rồi in nó ra theo trình tự đã đặt và kích thước của bảng thôi mà .

[trihoinachantoan]

Sacklove nghĩ đơn giản quá rồi đó. Nếu chỉ đơn thuần là đưa vào bảng và in ra thì sẽ rất mất thời gian và cách xử lí cũng rất rắc rối. Liệu có còn cách nào khác đơn giản không?

[tipi.vn]

Sacklove và binhnguyen vẫn chưa trả lời câu hỏi của mình đó nha, và tại sao các bạn không trả lời câu hỏi của mình vẫn tham gia mạnh các topic khác? Hèm hèm, khó hiểu đó.

[nhimbien12]

Em chịu rồi . Anh cho thuật giải đi !

[huongtmbn]

Cách của sacklove là đúng đắn, nhưng cái mình cần lưu ý ở đây là các bạn có thể cải tiến đi 1 chút để tăng tốc độ cũng như độ phức tạp khi viết chương trình. Cách của sacklove là tạo bảng để điền kí tự cho đúng quy tắc đúng không? Cách của mình cũng thế thôi, nhưng không tạo bảng vì vừa tốn thời gian tạo, tốn thời gian lôi từ bảng ra từ để in, tốn bộ nhớ để khởi tạo bảng. Mình nhận xét rằng, vì chuỗi đã mã hóa theo câu 1) là chuỗi được đọc theo thứ tự từ trên -> dưới, từ trái -> phải, do đó, thấy rằng mỗi kí tự thuộc cùng 1 hàng (nếu bạn tạo bảng) nó sẽ cách nhau 1 m-1 kí tự với m là số dòng của bảng. Như vậy, việc bạn tách từ chuỗi đã mã hóa ra chuỗi trước khi mã hóa lại trở thành đơn giản: chọn m,n là 2 số nguyên có tích = độ dài chuỗi, với mỗi m đã chọn được, ta tiến hành tách từ theo nhận xét trên, và sau đó in ra. Công việc tách từ sẽ được đảm bảo rằng luôn tách đúng thứ tự trái phải trên dưới đúng như bảng m*n, do đó chỉ cần tách từ, in ra theo m thế là ổn. Thực tế thì n chỉ dùng để kiểm tra m,n nguyên chứ không phục vụ mục đích tách từ vì chỉ cần dùng tới m là đủ rồi.

[rubiethuy]

c đã chuyển thành d rồi, làm sao về lại c để chuyển thành e đây? Cái quan trọng ở đây là tìm cách biến đổi thế nào để những phần tử như c được quay vòng nhanh nhất.

Có vẻ không hiểu ý Nguyên lắm nhỉ, c->d, d->e không làm ảnh hưởng gì đến quá trình sau cả.
Chỉ đơn thuần là cách sử dụng để biến đổi thôi, một cách sử dụng nhiều lần cũng được [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]
vì vậy Nguyên mới nói là dùng Duyệt đồ thị

[tranbaokieu]

Nhưng điều quan trọng mình thắc mắc ở đây là khi ta đã biến đổi c-> 1 cái gì đó rồi thì con đường để những cái đó trở về e liệu sẽ thế nào với khi ta biến đổi c->e trước rồi mới biến đổi các cái khác sau. c->d được, c->e được, nhưng d muốn thành e phải qua 1 số bước trung gian, e muốn thành d cũng phải qua 1 số bước trung gian, như thế thì bạn chọn cách biến đổi thế nào? Chắc chắn quá trình này sẽ làm ảnh hưởng tới các phép biến đổi sau và sẽ làm thay đổi độ dài, số lần biến đổi.

[manhhuong]

Một bài dạng đồ thị: cho 2 từ nguồn và đích và cặp từ (không quá 250 cặp từ). Hãy đưa ra bước biến đổi ngắn nhất: bao gồm số bước và trình tự sử dụng cặp từ biến đổi nào, từ trong bước biến đổi. Ví dụ cặp từ p l có nghĩa là có thể chuyển từ từ p sang từ l.
Lưu ý: từ nguồn và đích độ dài bằng nhau, mỗi từ trong cặp từ nằm trong 26 chữ cái an-pha-bê. Không có cách biến đổi in 0.
Một ví dụ:
Input:
slide stick
a c
s l
l k
k t
d c
e s
c t
Output:
6
l k skide
k t stide
d c stice
e s stics
s l sticl
l k stick

Mình thì nghĩ là bạn binhnguyenLQD-kg nên nói rõ hơn về yêu cầu của bài toán, ở đoạn dùng cặp từ biến đổi là chỉ chọn một kí tự để biến đổi hay là phải biến đổi tất cả các kí tự giống nhau???

Để mình lấy ví dụ cho dễ hiểu nha, với từ ban đầu là "ace" chẳng hạn, và bạn có các phép biến đổi: a -> e, và e -> a. Và bạn phải biến đổi thành "eca". Lúc này thì xét theo hai yêu cầu khác nhau như mình nêu trên thì sẽ có hai đáp án khác nhau phải không?

Mình nghĩ là bạn o0Tieu0Long0o cũng có thắc mắc giống mình nhỉ? Hì. Mong bạn binhnguyenLQD-kg sớm hồi đáp cho bọn mình nhé!