Sắp xếp mảng 2 chiều xoắn ốc pascal
đi xuo^'ng duo*'i (do`ng ta(ng da^`n) ne^'u đu.ng maxY thi` gia?m maxY đi 1 & đo^?i tha`nh đi qua tra'i đi qua tra'i (co^.t gia?m da^`n) ne^'u đu.ng minX thi` ta)ng minX the^m 1 & đo^?i đi le^n tre^n (do`ng gia?m da^`n) ne^'u đu.ng minY thi` ta(ng minY the^m 1 & đo^?i tha`nh đi qua pha?i Đã gửi 26-01-2010 - 22:43 Đề như thế này: Cho mảng hai chiều mxn. Hãy sắp xếp các số trong mảng theo chiều xoắn ốc cùng chiều kim đồng hồ từ ngoài vào trong sao cho dãy số tăng dần. Viết chương trình sắp xếp mảng vuông hai chiều (n hàng, n cột) theo hình xoắn ốc như sau: Dữ liệu vào file: XOANOC.INP dòng đầu chứa n, các dòng sau chứa mảng vuông 2 chiều n hàng, n cột Dữ liệu ra file: XOANOC.OUT chứa mảng 2 chiều n hàng, n cột đã sắp xếp VD: Chú ý: Có thể yêu cầu sắp xếp như sau: code 1uses crt; var i,j,k,t,s,n: integer; begin clrscr; write('Nhap n: '); readln(n); i:=1; j:=0; s:=n; t:=1; k:=0; for k:=1 to n*n do begin case t of 1 : j:=j+1; 2 : i:=i+1; 3 : j:=j-1; 4 : i:=i-1; end; gotoxy(j*3,i+2); write(k); if k=s then begin n:=n-(t mod 2); t:=t+1; s:=s+n; if t=5 then t:=1; end; end; readln end. code 2 var i,j,k,t,s,n,m,tem: integer; a: array[1..50,1..50] of integer; b:array[1..2500]of integer; F:text; begin {---doc file ra mang mot chieu b-} assign(F,'xoanoc.inp');reset(F); read(F,n); k:=1; for i:=1 to n do for j:=1 to n do begin read(f,b[k]); k:=k+1; end; close(F); for j:=1 to n*n do write(b[j],' '); {-- sap xep mang mot chieu-------} for i:=1 to n*n-1 do for j:=i+1 to n*n do if b[i]>b[j] then begin tem:=b[i]; b[i]:=b[j]; b[j]:=tem; end; //for j:=1 to n*n do write(b[j],' '); {-------------Dat mang b vào mang a theo hinh xoan oc----------------} m:=n-1;i:=1;j:=1;k:=1; while m>0 do begin for t:=1 to m do begin a[i,j]:=b[k]; j:=j+1; k:=k+1; end; for t:=1 to m do begin a[i,j]:=b[k]; i:=i+1; k:=k+1; end; for t:=1 to m do begin a[i,j]:=b[k]; j:=j-1; k:=k+1; end; for t:=1 to m do begin a[i,j]:=b[k]; i:=i-1; k:=k+1; end; i:=i+1; j:=j+1;m:=m-2 end; if m=0 then a[n div 2+1,n div 2+1]:=b[n*n]; {-- xuat file ------} assign(F,'XOANOC.OUT'); rewrite(F); for i:=1 to n do begin for j:= 1 to n do write(f,a[i,j]:5); writeln(f); end; close(F); end. Thuật toán gán các số tự nhiên liên tiếp vào mảng 2 chiều theo hình xoáy trôn ốc: 1. Sử dụng mảng có kích thước N+2 (bao gồm các biên ảo ở bốn phía). Khởi tạo mảng gồm toàn các số 0, riêng các giá trị chặn ở biên của mảng thì gán 1 2. Bắt đầu gán từ số 1 (i=1), vị trí bắt đầu là hàng 1, cột 0, hướng sang phải 3. Từ vị trí hiện tại, nếu tiếp tục đi theo hướng đang sử dụng sẽ gặp một ô có giá trị khác 0 (là ô đã được gán giá trị hoặc là ô chặn biên), thì đổi hướng theo vòng tròn như sau: sang phải -> xuống dưới -> sang trái -> lên trên -> lặp lại sang phải 4. Chuyển hướng di chuyển theo (3) nếu phải chuyển hướng, đi theo hướng lựa chọn 1 ô, gán giá trị i vào ô đó, tăng i lên 1 đơn vị 5. Vòng lặp dừng khi i=NxN Bài ví dụ: const dir: array [0..3, 1..2] of shortint = ((0,1), (1,0), (0,-1), (-1,0)); { 4 hướng di chuyển } var a: array [0..20, 0..20] of integer; i, n: integer; x, y, d: integer; begin write('Nhap N = '); readln(n); { khởi tạo mảng a } fillchar(a, sizeof(a), 0); { khởi tạo mảng a gồm toàn số 0 } a[1,n+1]:=1; a[n+1,n]:=1; a[n,0]:=1; a[0,1]:=1; { giá trị biên } { tạo ma trận } y:=1; x:=0; d:=0; { vị trí và hướng bắt đầu } for i:=1 to n*n do begin if a[y+dir[d,1], x+dir[d,2]] <> 0 then d:=(d+1) mod 4; { đổi hướng } y:=y+dir[d,1]; x:=x+dir[d,2]; a[y,x]:=i; end; { in ra ma trận } for y:=1 to n do begin for x:=1 to n do write(a[y,x]:4); writeln; end; readln; end. Chú ý: 1. Mảng dir: array [0..3, 1..2] chứa 4 véctơ tương ứng với 4 hướng di chuyển sang phải, xuống dưới, sang trái và lên trên - dùng để di chuyển trong mảng 2 chiều A 2. Hàm fillchar dùng để gán hàng loạt giá trị 0 vào mảng A, có thể thay bằng vòng lặp duyệt toàn mảng A và gán giá trị 0 3. a[1,n+1]:=1; a[n+1,n]:=1; a[n,0]:=1; a[0,1]:=1; là 4 ô chặn 4 hướng di chuyển đầu tiên để tạo thành vòng ngoài cùng của hình xoáy trôn ốc 4. if a[y+dir[d,1], x+dir[d,2]] <> 0 then d:=(d+1) mod 4; Kiểm tra nếu như đi theo hướng hiện tại gặp 1 ô đã gán giá trị (hay gặp 1 ô chặn) thì đổi sang hướng kế tiếp 5. Để in cho đẹp với màn hình 80 cột thì chỉ nên nhập các giá trị N<=19 |