Hỏi: bài toán sắp xếp mảng trong Pascal

A

Trương Vĩnh Bình
(Asteroid_tvb)

New Member
Bài toán Pascal cần giúp đỡ.


Cho ma trận A vuông cấp n, Hãy sắp xếp lại ma trận A biết các phần tử trong mảng sắp xếp lại theo thứ tự thao hình xoáy ốc từ theo chiều kim đồng hồ tăng dần. ( Phần tử trong cùng là nhỏ nhất, theo chiều soáy ốc ra ngoài tăng dần.
Hu hu, em đang cần gấp, bác nào giúp đỡ nào
 
ma trận cấp n là n x n í hả ?
Thực tế thì bài này và bải sort dãy số tương tự nhau, không có gì khác nhau cả. Em tưởng tượng ma trận thực tế là một dãy số được xếp xoắn lại thôi (một bên là con rắn nằm ngang, một bên là con rắn cuộn tròn :D ). Thế nên em cứ sort các phần tử trong ma trận như trên một dãy số. Sau đấy em tạo một cai procedure để điền cái ma trận đã sort lại theo yêu cầu.
 
Anh nói khó hiểu quá,có phải là :
Có 1 cái ma trận A và 1 cái mảng khác , phần tử của nó lộn xộn,bây giờ xếp phần tử đó vào A theo hình xoáy ốc,chiều tăng dần.

Nếu đúng thế thì cũng ko khó,mà ma trận 4x4 thì ô nào là "trong cùng" nhỉ?

Ý tưởng thì thế này:
-Xếp lại cái mảng theo chiều giảm dần.
-Từ ô 1,1 xếp ngang mấy cái phần tử mảng,hết chiều ngang thì chạy dọc,hết dọc lại ngang ---> thành xoáy ốc. :))
 
Vấn đề của bài toán được chia làm 2 phần :
1. Sắp xếp theo thứ tự tăng dần 1 dẫy số được stock trong 1 matrix [n,n]
2. In ra màn hình theo hình xoắn ốc cái dẫy số đã được sort.
======================================

1. Vấn đề này anh hy vọng không có vấn đề gì chứ? Để đơn giản hóa vấn đề chú có thể copy 1 sang 1 array 1 chiều ví du D[m] (trong đó m=nxn), sau đó sort cái array đấy /:) Có khá nhiều cách làm, thử đi, nếu vẫn ko được thì cứ ới anh tiếng :p

2. Vấn đề in ra màn hình cái array kia.

- Vị trí trung tâm của matrix là:
[n/2;n/2] nếu n chẵn
[(n+1)/2;(n+1)/2] nếu n lẻ
- Từ vị trí trung tâm đấy, chạy sang bên phải, rồi kể từ đấy nếu không rẽ phải được(tức là ô bên phải đã đi qua rồi, hay là đã có cái gì trong đấy rồi) thì đi thẳng :D Cứ thế cho đến khi nào không đi được nữa thì cũng là lúc hết matrix :D

* Nếu ngại cái vị trí trung tâm kia thì cũng có thể làm thế này: Bắt đầu từ vị trí trên cùng bên trái (1;1) (hay (0;0) ý nhỉ? :-s) chạy xuống dưới, gặp chướng ngại vật (bao gồm cả "tường") thì rẽ trái, còn không cứ chạy thẳng :D Cho đến lúc nào không đi được nữa thì thôi :p

Thử đi, good luck :p
 
Chỉnh sửa lần cuối:
Anh ơi nhưng vấn đề bây h là n<=100 000, anh stock sao vào 1 cái mảng 1 chiều nxn thì tuyệt quá, chỉ em với nhé ;)
 
Tấn Thành đã viết:
Anh ơi nhưng vấn đề bây h là n<=100 000, anh stock sao vào 1 cái mảng 1 chiều nxn thì tuyệt quá, chỉ em với nhé ;)
Nhấn để mở rộng...

lớn rồi suy nghĩ chút đi b-( Anh là anh chỉ đưa ra đường hướng giải quyết vấn đề, còn nếu n = 100 000 thì :p :-s thì stock vào [n;n] đi :) stock theo thứ tự nào thì nhớ mà tí nữa còn lôi ra :D Anh hy vọng là parcourir 1 chiều với parcourir 2 chiều đối với chú Thành không có trở ngại gí chứ? ;;) (2 cái "for" lồng vào nhau thôi muh :p)
 
n <= 100 000 thì mảng nào cũng chả lưu được mà :(. Thôi thì cứ thế này , viết lên màn hình dòng chữ : "kiên nhẫn là đức tính tốt của con người" rồi cho máy nó treo :D . Thầy giáo em chắc cũng biết đường mà đợi ... đợi chán rồi cho luôn điểm mười :D hôm sau toe toét đến lớp vì mình có thêm một đức tính tốt.
 
Thôi nghĩ đi nghĩ lại thì trả lời kỹ càng tí không em nó tủi thân :D

1.Giống như cái bác gì bác ý nói ở trên ý , em cứ sort như sort mảng một chiều thôi. (còn nếu như mà thích nghịch với n lớn thì em làm sort trên con trỏ ).

2.Bước hai : out put ra mảng hai chiều : chỉ thay đổi tí so với bác gì ở trên, tức là không phải xác định điểm ở giữa cái màng hay gì gì đấy rất phức tạp . Em làm một cái procedure , trong đấy có một giá trị gọi là hướng. Và điền theo hướng đấy, đến khi bị chặn (ra rìa mảng hoặc gặp một ô điền rồi) thì thay đổi hướng theo chiều kim đồng hồ 90 độ . (E -->S --->W -->N --> E..)
 
Matrix 100.000 x 100.000 thì trỏ nào cho lại :)
 
Pham Duy Yen đã viết:
Thôi nghĩ đi nghĩ lại thì trả lời kỹ càng tí không em nó tủi thân :D

1.Giống như cái bác gì bác ý nói ở trên ý , em cứ sort như sort mảng một chiều thôi. (còn nếu như mà thích nghịch với n lớn thì em làm sort trên con trỏ ).

2.Bước hai : out put ra mảng hai chiều : chỉ thay đổi tí so với bác gì ở trên, tức là không phải xác định điểm ở giữa cái màng hay gì gì đấy rất phức tạp . Em làm một cái procedure , trong đấy có một giá trị gọi là hướng. Và điền theo hướng đấy, đến khi bị chặn (ra rìa mảng hoặc gặp một ô điền rồi) thì thay đổi hướng theo chiều kim đồng hồ 90 độ . (E -->S --->W -->N --> E..)
Nhấn để mở rộng...

"E -->S --->W -->N --> E" là cái gì đấy? :-?

bác gì ở trên bác ý cũng có ý giống chú đấy :D Nhưng mà yêu cầu bài toán là xếp theo chiều kim đồng hồ từ giữa xếp ra theo thứ tự tăng dần, tức là nếu xếp từ ngoài vào thì phải theo thứ tự giảm dần và ngược chiều kim đồng hồ :D
 
Ngô Nguyễn Duy đã viết:
Matrix 100.000 x 100.000 thì trỏ nào cho lại :)
Nhấn để mở rộng...

anh Duy cho phép em làm phép tính đơn giản 100k x 100k = 10^10

Nếu giả sử cái array đấy theo kiểu integer, tức là là mỗii ô chiếm 4 bytes trong bộ nhớ. Như vậy để chứa được cái matrix trên thì cần phải có : 4x10^10 bytes, tương đương với khoảng 40 000 Mb hay 40Gb memory :D :)>-

Thằng Thành INSA tự vả vào mồm đê [-x
 
chẹp thế cho nên suy cho cùng thì giải pháp viết lên màn hình "người thông minh là người biết chờ đợi" vẫn xem ra là hữu hiệu nhất nhỉ ?

----------

Mà INSA nằm ở chỗ nào thế thành nhỉ ? Thang 12 này tôi qua pháp , không biết có gặp được ông không ?
 
Thứ nhất: đây ko phải chỗ chat chit, mà là chỗ để cho em gì em í hỏi bài, thế nên là tôi ko thể trả lời ông đc, Yến ạ, nhưng mà nếu ông có xuống Lyon thì cứ gọi tôi, chúng ta làm phát rượu thôi, trời lạnh rồi!:-? :-?
Thứ 2: anh Hoàng, thằng Yến nó nói cái E N S W gì gì đấy là đông tây nam bắc anh ạ, thằng này học chuyên địa Ams, nên đc cái giỏi khoản này.
Thứ 3: nếu n<=100 000 thì chắc dùng tree là ok, hic con trỏ ko biết có chơi nổi ko nữa, cố chắc vẫn đc.
Em gì cần hỏi mà chả thấy đâu cả, nếu vấn đề của em đã đc giải quyết thì em vào báo mọi ng 1 câu, nhé:)
 
Tấn Thành đã viết:
Thứ 2: anh Hoàng, thằng Yến nó nói cái E N S W gì gì đấy là đông tây nam bắc anh ạ, thằng này học chuyên địa Ams, nên đc cái giỏi khoản này.
Thứ 3: nếu n<=100 000 thì chắc dùng tree là ok, hic con trỏ ko biết có chơi nổi ko nữa, cố chắc vẫn đc.
Em gì cần hỏi mà chả thấy đâu cả, nếu vấn đề của em đã đc giải quyết thì em vào báo mọi ng 1 câu, nhé:)
Nhấn để mở rộng...

ặc ặc chuyên Địa à :x thần tượng thía :x :x :D

pointer bản chất cũng là array thôi mà :D Chỉ có điều 1 cái dynamic (pointer) 1 cái static (array). Nếu vẫn làm theo algorithme cũ thì chắc chắn phải stock bớt vào HDD rồi (HDD > 40Gb nhá), không có thì kiếm đâu ra cho đủ 40Gb Ram thì kiếm :D
 
ặc ặc chuyên Địa à thần tượng thía

pointer bản chất cũng là array thôi mà Chỉ có điều 1 cái dynamic (pointer) 1 cái static (array). Nếu vẫn làm theo algorithme cũ thì chắc chắn phải stock bớt vào HDD rồi (HDD > 40Gb nhá), không có thì kiếm đâu ra cho đủ 40Gb Ram thì kiếm
Nhấn để mở rộng...
Dùng vitrual memory :)) :)) Viết vào file,mỗi file là 1 "block" của cái mảng :))

Theo ngu ý kiến của em thì tốt nhất xếp từ ngoài vào theo cái kiều đông tây nam bắc của "anh" yen.
 
nếu mà mảng cap n= 100000 thì chỉ cần lưu vào mảng 1 chiều rồi dùng 1 số mẹo viết ra màn hình là được...đầu tiền nhấp tất cả các phần từ vào mảng 1 chiều
con trỏ..100.000 phần tử.
sau đấy sort lại cái mảng này
viết ra = cách cứ sau n bước viết thì lại đổi kiểu viết (dùng gotoxy(x,y) để nhảy đến chỗ cần viết)
ví dụ mang n=5 gồm các số từ 1->25
sau khi viết 5 lần
1 2 3 4 5
thì gotoxy tới dòng tiếp theo phần tử cuối rồi viết tiếp n-k lần (sau mỗi lần tăng k lền 1)..
sau đấy se là
1 2 3 4 5
* * * * 6
* * * * 7
* * * * 8
* * * * 9
cứ như thế đến hết
em nói thế này hơi khó hiểu nhưng nếu dùng lệnh gotoxy(x,y) 1,2 lần là hiểu ngay..đây là cách làm mẹo..Anh nào có thời gian code thì post lên cho người ta..em đang ngoài hàng net :D..thế nên là ko làm được rì cả. :D
 
Chỉnh sửa lần cuối:
sort 40 GB vẫn sort được mà ?? đâu cứ phải load hết lên ram thì mới sort được đâu. Có rất nhiều thuật toán để sort dãy lớn build index file cũng là một cách. . tất nhiên thời gian thì không nhanh rồi :D .

to thành : ờ tôi học địa dốt lắm, chắc không biết đường xuống lyon đâu :D . Đùa chứ, nếu có cơ hội thì sẽ liên lạc với ông :D .
 
Nếu sắp xếp mà RAM không đủ chứa lượng dữ liệu đầu vào thì phải dùng phương pháp sắp xếp ngoài (external sorting). Cái này có thể tham khảo trong quyển : "The art of computer programming" tập 3 của D.Knuth hoặc tìm trên Google :D.
 
Chỉnh sửa lần cuối:
Em nhơ bài này học đội tuyển năm lớp 8 làm rồi, không biết giờ còn để code ở nhà không . Để em tìm lại nhé ...
 
Bạn phải đăng nhập hoặc đăng ký để phản hồi tại đây.
Back
Bên trên