2.3 Robot Một Robot được lập trình để di chuyển trên mặt phẳng tọa độ xoy chia lưới đơn vị. Chương trình điều khiển Robot được viết dưới dạng xâu gọn như trong bài Xâu gọn và gồm dãy lệnh với ý nghĩa như sau: Gn – đi thẳng n bước qua các điểm nguyên, Rn – quay phải n lần 45 độ, Ln – quay trái n lần 45 độ. Robot được đặt tại vị trí xuất phát là gốc tọa độ, mặt hướng theo trục oy. Yêu cầu: Xác định tọa độ (x,y) nơi Robot dừng chân sau khi thực hiện chương trình ghi trong string s. Thí dụ, Sau khi thực hiện chương trình s = "(GR3(G2L)2(L5G)0)2G3" Robot sẽ dừng chân tại vị trí (10,4) trên mặt phẳng tọa độ.
Thuật toán
Pha 1 hoàn toàn giống bài Xâu thu gọn. Riêng với pha 2 ta cần thay lệnh hiển thị bằng việc tính vị trí của Robot sau khi thực hiện mỗi dòng lệnh. 
Vì có 8 hướng nên nếu Robot đang hướng mặt về hướng h thì sau khi quay phải k lần hướng mặt của Robot sẽ là h = (h+k) mod 8, còn khi quay trái k lần ta sẽ có h = (h + n(k mod 8)) mod 8. Bạn để ý rằng phép trừ k đơn vị trên vòng tròn n điểm sẽ được đổi thành phép cộng với nk.
Độ phức tạp Cỡ n, trong đó n là số kí tự trong xâu input.
(* Robot.pas *)
uses crt;
const mn = 500; BL = #32; NL = #13#10; xx = 0; yy = 1;
huong: array[0..7,0..1] of integer
= ( (0,1), (1,1), (1,0), (1,-1),
(0,-1), (-1,-1), (-1,0), (-1,1) );
ChuSo = ['0'..'9']; ChuCai = ['A'..'Z'];
type mi1 = array[0..mn] of integer;
mc1 = array[0..mn] of char;
var M, T, R, st: mi1; { M: so lan lap; T: tu; R: luu, st: stack }
c: mc1; { Lenh }
p: integer; { ngon stack }
s: string;
v: integer; { chi dan cua s }
n: integer; { so dong lenh }
x,y: integer; { Toa do Robot }
h: integer; { huong di chuyen cua Robot }
procedure Cach; begin while (s[v] = BL) do inc(v); end;
function DocSo: integer;
var so: integer;
begin so := 0; Cach;
if Not (s[v] in ChuSo) then begin DocSo := 1; exit; end;
while (s[v] in ChuSo) do
begin
so := so*10 + (Ord(s[v]) - ord('0'));
inc(v);
end;
DocSo := so;
end;
procedure LenhDon(ch: char);
var so: integer;
begin
inc(v); so := DocSo;
if so = 0 then exit;
inc(n); C[n] := ch; M[n] := so;
end;
procedure NapNgoac;
begin inc(v); inc(p); st[p] := n+1 end;
procedure LenhLap;
var tu, so: integer;
begin
inc(v); tu := st[p]; dec(p);
so := DocSo;
if (so = 0) then n := tu-1;
if (so < 2) then exit;
inc(n); C[n] := '#'; M[n] := so; T[n] := tu; R[n] := so;
end;
procedure ThucHien(i: integer);
begin
case C[i] of
'G': begin x:=x+M[i]*huong[h,xx];y:=y+M[i]*huong[h,yy] end;
'R': h := (h + M[i]) mod 8;
'L': h := (h + 8 - (M[i] mod 8)) mod 8;
end;
end;
procedure Pha2;
var i: integer;
begin
x := 0; y := 0; h := 0;
for i := 1 to n do
begin
write(NL,i,'. ',C[i],BL,M[i],BL);
if C[i] = '#' then write(T[i],BL,R[i]);
end;
i := 1;
while (i <= n) do
begin
if (C[i] = '#') then
begin
dec(R[i]);
if (R[i] = 0) then begin R[i] := M[i]; inc(i) end
else i := T[i];
end
else
begin
ThucHien(i); { thuc hien dong lenh i }
inc(i);
end;
end;
end;
procedure Go(var s: string);
begin
s := s + '#'; v := 1; p := 0;
while (s[v] <> '#') do
begin
if (s[v] in ChuCai) then LenhDon(s[v])
else if (s[v] = '(') then NapNgoac
else if (s[v] = ')') then LenhLap
else inc(v);
end;
write(NL,s , ' = ');
Pha2;
end;
BEGIN
s := '(GR3(G2L)2(L5G)0)2G3';
Go(s);
writeln(NL,NL,'Ket qua (x,y) = ',x,BL,y); { (x,y) = (10,-4) }
readln;
END.
// DevC++: Robot.cpp
#include
#include
#include
using namespace std;
// D A T A A N D V A R I A B L E
const int mn = 500;
const char BL = 32;
char C[mn]; // noi dung lenh
int M[mn]; // so lan lap
int T[mn]; // lap tu dong lenh nao
int R[mn]; // luu gia tri M
int n; // con dem dong lenh
char s[mn]; // xau thu gon
int v; // chi so duyet s
int st[mn]; // stack
int p; // chi so ngon stack st
int x, y; // Toa do (x,y) cua Robot
const int xx = 0, yy = 1;
int step[8][2] = {{0,1},{1,1},{1,0},{1,-1},
{0,-1},{-1,-1},{-1,0},{-1,1}};
int h; // huong di chuyen cua Robot
// P R O T O T Y P E S
void Go(char *);
void LenhDon(char);
void LenhLap();
int DocSo();
void Cach();
bool LaChuSo(char);
bool LaChuCai(char);
void Pha2();
void ThucHien(int);
// I M P L E M E N T A T I O N
int main(){
strcpy(s,"(GR3(G2L)2(L5G)0)2G3"); // (x,y) = (10,-4)
Go(s);
cout << endl << x << " " << y;
cout << endl; system("PAUSE");
return EXIT_SUCCESS;
}
bool LaChuCai(char c) { return (c >= 'A') && (c <= 'Z'); }
bool LaChuSo(char c) { return (c >= '0') && (c <= '9'); }
void Cach() { while (s[v] == BL) ++v; }
int DocSo() {
int so = 0;
Cach();
if (!LaChuSo(s[v])) return 1;
while (LaChuSo(s[v])) {
so = so*10 + int(s[v]-'0'); ++v;
}
return so;
}
void LenhDon(char ch) {
int so;
++v; so = DocSo();
if (so == 0) return;
++n; C[n] = ch; M[n] = so;
}
void LenhLap() {
int so;
++v; // bo qua dau )
so = DocSo();
int tu = st[p--];
if (so == 0) { n = tu-1; return; }
if (so == 1) return;
++n; C[n] = '#'; M[n] = R[n] = so; T[n] = tu;
}
void Go(char *s ) {
cout << endl << "input: " << s;
// init
p = 0; n = 0;
for (v = 0; s[v];) {
if (LaChuCai(s[v])) LenhDon(s[v]);
else if (s[v] == '(') { st[++p] = n+1; ++v; }
else if (s[v] == ')') LenhLap();
else ++v;
}
Pha2();
}
void ThucHien(int i) {
switch(C[i]) {
case 'G': x += M[i]*step[h][xx]; y += M[i]*step[h][yy]; break;
case 'R': h = (h+M[i]) % 8; break;
case 'L': h = (h+8-(M[i]%8)) % 8; break;
}
}
void Pha2() {
int i;
cout << endl << s << " = ";
x = y = 0; h = 0; i = 1;
while (i <= n) {
if (C[i] == '#') {
--R[i];
if (R[i] == 0) { R[i] = M[i]; ++i; }
else i = T[i];
}
else {
ThucHien(i); // thuc hien dong lenh i
++i;
}
}
}
Chia sẻ với bạn bè của bạn: |
