[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Cho hai xâu kí tự S1 và S2, cho phép thực hiện các phép biến đổi sau đối với xâu:
– Luật 1: Thay thế một kí tự trong xâu bằng một kí tự khác.
– Luật 2: Đổi chỗ hai kí tự liền nhau.
– Luật 3: Chèn vào một kí tự.
– Luật 4: Xoá bớt một kí tự.
Ta gọi khoảng cách giữa hai xâu S1 và S2 là số nhỏ nhất các lần thực hiện biến đổi theo một trong bốn luật nêu trên để biến xâu S1 thành xâu S2.
Ví dụ: giả sử S1 = ‘Barney’, S2 = ‘brawny’. Khoảng cách giữa hai xâu là 4. Dãy các phép biến đổi cần thực hiện là:
– Thay 1 kí tự của S1 (kí tự ‘B’) bởi ‘b’ (luật 1). S1 thành ‘barney’
– Đổi chỗ hai kí tự thứ 2 (‘a’) và thứ 3 (‘r’) (luật 2). S1 thành ‘braney’
– Chèn kí tự ‘w’ vào sau kí tự thứ 3 (luật 3). S1 thành ‘brawney’
– Xoá kí tự thứ 6 ‘e’ (luật 4). S1 thành S2 = ‘brawny’
S1 lần lượt sẽ là:
‘Barney’ >>> ‘barney’ >>> ‘braney’ >>> ‘brawney’ >>> ‘brawny’
Cần lập bảng mô tả các bước thực hiện để biến S1 thành S2 theo quy ước sau:
Dòng đầu tiên ghi số lượng các phép biến đổi cần sử dụng K.
K dòng tiếp theo mô tả phép biến đổi sử dụng ở lần thứ i (1 ≤ i ≤ K): đầu tiên ghi chỉ số của luật biến đổi sử dụng; tiếp đến:
– Nếu là phép biến đổi theo quy luật 1, cần chỉ ra vị trí của kí tự cần thay và kí tự thay thế;
– Nếu là phép biến đổi theo quy luật 2, cần chỉ ra vị trí của hai kí tự cần đổi chỗ;
– Nếu là phép biến đổi theo quy luật 3, cần chỉ ra vị trí của kí tự mà sau nó cần chèn một kí tự và kí tự cần chèn;
– Nếu là phép biến đổi theo quy luật 4, cần chỉ ra vị trí của kí tự cần xoá.
(Biết rằng vị trí của kí tự trong xâu đang xét là chỉ số của nó trong xâu theo quy ước của Pascal).
Với vị dụ trên, bảng mô tả các bước thực hiện để chuyển ‘Barney’ thành ‘brawny’ sẽ là:
_____________
4
1 1 b
2 2 3
3 3 w
4 6
_____________
* Yêu cầu: cho xâu S1=’yoinchyeh’ ; S2=’Thichuyen’
Em hãy lập bảng mô tả các bước thực hiện theo luật đã cho sao cho để biến S1 thành S2, sao cho số lần biến đổi là ít nhất.
– Luật 1: Thay thế một kí tự trong xâu bằng một kí tự khác.
– Luật 2: Đổi chỗ hai kí tự liền nhau.
– Luật 3: Chèn vào một kí tự.
– Luật 4: Xoá bớt một kí tự.
Ta gọi khoảng cách giữa hai xâu S1 và S2 là số nhỏ nhất các lần thực hiện biến đổi theo một trong bốn luật nêu trên để biến xâu S1 thành xâu S2.
Ví dụ: giả sử S1 = ‘Barney’, S2 = ‘brawny’. Khoảng cách giữa hai xâu là 4. Dãy các phép biến đổi cần thực hiện là:
– Thay 1 kí tự của S1 (kí tự ‘B’) bởi ‘b’ (luật 1). S1 thành ‘barney’
– Đổi chỗ hai kí tự thứ 2 (‘a’) và thứ 3 (‘r’) (luật 2). S1 thành ‘braney’
– Chèn kí tự ‘w’ vào sau kí tự thứ 3 (luật 3). S1 thành ‘brawney’
– Xoá kí tự thứ 6 ‘e’ (luật 4). S1 thành S2 = ‘brawny’
S1 lần lượt sẽ là:
‘Barney’ >>> ‘barney’ >>> ‘braney’ >>> ‘brawney’ >>> ‘brawny’
Cần lập bảng mô tả các bước thực hiện để biến S1 thành S2 theo quy ước sau:
Dòng đầu tiên ghi số lượng các phép biến đổi cần sử dụng K.
K dòng tiếp theo mô tả phép biến đổi sử dụng ở lần thứ i (1 ≤ i ≤ K): đầu tiên ghi chỉ số của luật biến đổi sử dụng; tiếp đến:
– Nếu là phép biến đổi theo quy luật 1, cần chỉ ra vị trí của kí tự cần thay và kí tự thay thế;
– Nếu là phép biến đổi theo quy luật 2, cần chỉ ra vị trí của hai kí tự cần đổi chỗ;
– Nếu là phép biến đổi theo quy luật 3, cần chỉ ra vị trí của kí tự mà sau nó cần chèn một kí tự và kí tự cần chèn;
– Nếu là phép biến đổi theo quy luật 4, cần chỉ ra vị trí của kí tự cần xoá.
(Biết rằng vị trí của kí tự trong xâu đang xét là chỉ số của nó trong xâu theo quy ước của Pascal).
Với vị dụ trên, bảng mô tả các bước thực hiện để chuyển ‘Barney’ thành ‘brawny’ sẽ là:
_____________
4
1 1 b
2 2 3
3 3 w
4 6
_____________
* Yêu cầu: cho xâu S1=’yoinchyeh’ ; S2=’Thichuyen’
Em hãy lập bảng mô tả các bước thực hiện theo luật đã cho sao cho để biến S1 thành S2, sao cho số lần biến đổi là ít nhất.