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

[thutrang203]

Các mem thử làm bài này nhé, cũng đơn giản thôi, chủ yếu là hãy đưa ra cách làm nhanh nhất và tối ưu nhất
Tên: maluoi.
Cho 1 xâu gồm nhiều từ và 1 bảng M*N.
a) Yêu cầu là đưa các từ của xâu đó vào trong bảng sao cho ô 1,1 và m,n không được chứa dấu cách
b) Từ bản mã (là 1 xâu dịch từ bảng trên theo thứ tự đọc từ trên xuống dưới từ trái sang phải), hãy in ra tất cả các xâu ban đầu có thể, tương ứng với mỗi m,n vì mỗi m,n thì có 1 cách riêng. Yêu cầu là các từ trong xâu dịch được phải có ít nhất 1 từ trong k từ cho trước
VD: từ 1 xâu ban đầu như sau: CONG HOA XA HOI CHU NGHIA VIET NAM ta có bảng như dưới đây
C O N G _ H O A _
_ X A _ _ H O I _
C H U _ N G H I A
V I E T _ _ N A M
Như trên là bảng 4*9, _ là dấu cách để phân biệt các từ.
bản mã tương ứng bảng trên sẽ là: C_CVOXHINAUEG__T__N_HHG_OOHNAIIA__AM
Out put đưa ra các trường hợp m,n và xâu bạn dịch được từ xâu mã hóa thu được từ câu a.
Out có thể có nhiều cách đấy các bạn đừng hiểu 1 bảng chỉ thu được 1 kq nhé.
Quan trọng nhất bài này là câu 2 vì câu 1 khá đơn giản, nhưng cũng có thể đưa ra nhiều kết quả đấy [IMG]data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAA l21bKAAAAA1BMVEXh5PJm+yKVAAAAAXRSTlMAQObYZgAAAApJR EFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=[/IMG]

[giangnt]

chả hiểu đề . anh có thể cho rõ in / out ko ? chứ đọc thế này thì loạn quá .

[trinhhiep.camera]

INP:
C CVOXHINAUEG T N HHG OOHNAIIA AM
5
CONG
XA
C
AS
AS
out:
m=1;n=36
C CVOXHINAUEG T N HHG OOHNAIIA AM
m=4;n=9
CONG HOA XA HOI CHU NGHIA VIET NAM
m=12;n=3
CGO O C H VTN O A X I HNI I A NH AH UGA E M
m=36;n=1
C C V O X H I N A U E G T N H H G O O H N A I I A A M
Test của câu b thôi đấy nhé.

[tindienthoai]

vậy thì cũng khá đơn giản ............

[buiminhphuong]

làm bằng PasCal hả bác, không ai post C lên zậy ta

[haudinhads]

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

[vthao93hp]

vậy thì cũng khá đơn giản ............

bài này là để rèn luyện kĩ năng lập trình nên cũng đơn giản thôi mà, cái quan trọng là các mem tìm ra cách nhanh nhất để làm bài này
Bạn lehongtrinh: đây là box Pascal thôi bạn, C ở box khác.
binhnguyen: bài này cũng khá phức tạp nhỉ, nguyên đưa ra thuật toán xem sao

[cushinthang]

bài này là để rèn luyện kĩ năng lập trình nên cũng đơn giản thôi mà, cái quan trọng là các mem tìm ra cách nhanh nhất để làm bài này
Bạn lehongtrinh: đây là box Pascal thôi bạn, C ở box khác.
binhnguyen: bài này cũng khá phức tạp nhỉ, nguyên đưa ra thuật toán xem sao

Suy nghĩ đơn giản tí, xây dựng ma trận 26x26 tương ứng các chữ a, b, c, d.... z. Bao gồm chỉ là 0 hoặc 1. Nếu từ a có thể chuyển sang b thì đánh số 1..... Ta được một đồ thị có hướng và thuật toán bây giờ là tìm đường đi ngắn nhất từ một tọa độ đến một tọa độ. Mỗi lần tìm đường đi là một chữ cái và cộng dồn lại ta được số lần biến đổi ít nhất. (nhớ lưu cách đổi)

[seochoikiemgao]

Đơn giản thế thôi hả? Nếu cách biến đổi từ a -> b phải qua các bước như a - c - d - b, và để biến c -> e phải qua các bước như c - d - e, thì làm thế nào đây? Bạn sẽ chọn chuyển a->b hay từ c->e?

[Thắng Lợi Group]

Đơn giản thế thôi hả? Nếu cách biến đổi từ a -> b phải qua các bước như a - c - d - b, và để biến c -> e phải qua các bước như c - d - e, thì làm thế nào đây? Bạn sẽ chọn chuyển a->b hay từ c->e?

Tùy từ nguồn và đích, thật ra đây là bài toán loang. Ví dụ như từ a->b:
a c
c d
d b
k b
e k
c e
a->c->d->b và a->c->e->k->b thì cách cần tìm là cách đầu tiên, loang rồi giữ lại mảng đánh dấu và in ra.