# GÓC SÁNG TẠO > Khu vực lập trình > Pascal/Delphi/Kylix >  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.

----------


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


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é!

----------


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

----------

