Kênh Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
Monday, January 13, 2014



Sắp mảng rồi ghi tệp- gia sư tin học
               Sinh ngẫu nhiên n phần tử cho mảng nguyên a. Sắp a theo trật tự tăng dần rồi ghi vào một tệp văn bản có tên tuỳ đặt.
Gợi ý
Chương trình giới thiệu hai thủ tục sắp mảng là MinSortQuickSort. Theo phương pháp MinSort với mỗi i ta tìm phần tử nhỏ nhất a[j] trong đoạn a[i..n] sau đó ta đổi chỗ phần tử này với phần tử a[i]. Như vậy mảng được chia thành hai đoạn: đoạn trái, a[1..i] được sắp tăng, còn đoạn phải a[i + 1..n] chưa xử lí. Mỗi bước ta thu hẹp đoạn phải cho đến khi còn một phần tử là xong.
Theo phương pháp QuickSort ta lấy một phần tử x nằm giữa đoạn mảng cần sắp làm mẫu rồi chia mảng thành hai đoạn. Đoạn trái a[1..i] bao gồm các giá trị không lớn hơn x và đoạn phải a[j..n] bao gồm các giá trị không nhỏ thua x. Tiếp đến ta lặp lại thủ tục này với hai đoạn thu được nếu chúng chứa nhiều hơn một phần tử.
(*  Pascal  *)
(*---------------------------------------
      SAPTANG: Sap mang, ghi tep
----------------------------------------*)
program SapTang;
{$B-}
uses crt;
const
MN = 5000;
fn = 'saptang.out';
var
f: text;
a: array[1..MN] of integer;
n: integer;
(*------------------------------
sinh ngau nhien m phan tu
        cho mang nguyen a
--------------------------------*)
procedure Init(m: integer);
var i: integer;
begin
if (m < 0) or (m > MN) then exit;
n:= m;
randomize;
for i:= 1 to n do a[i]:= random(MN);
end;
(*-------------------------------------
            Sap nhanh doan a[d..c]
---------------------------------------*)
procedure QuickSort(d, c: integer);
var i, j, x, y: integer;
begin
i:= d; j:= c;
x:= a[(i+j) div 2];{lay tri mau x}
while i <= j do
begin
while a[i] < x do inc(i); {to chuc doan trai}
while a[j] > x do dec(j); {to chuc doan phai}
if (i <= j) then {doi cho neu can}
    begin
y:= a[i];
a[i]:= a[j];
a[j]:= y;
inc(i); dec(j);
    end;
end;
if (d < j) then QuickSort(d,j); {sap tiep doan trai}
if (i < c) then QuickSort(i,c); {sap tiep doan phai}
end;
(*------------------------------------
Tim chi dan m trong khoang d..c
            thoa a[m] = min(a[d..c])
--------------------------------------*)
function Min(d, c: integer): integer;
var i: integer;
begin
for i:= d+1 to c do
    if a[i] < a[d] then d:= i;
Min:= d;
end;
procedure MinSort;
var i, j, y: integer;
begin
for i:= 1 to n-1 do
begin
j:= Min(i,n);
{doi cho a[i] va a[j]}
y:= a[i];
a[i]:= a[j];
a[j]:= y;
end;
end;
(*----------------------------------
      Ghi tep, moi dong khong qua 20 so
-----------------------------------*)
procedure Ghi;
var i: integer;
begin
assign(f,fn); rewrite(f);
writeln(f,n);
for i:= 1 to n do
begin
write(f,a[i]:5);
if i mod 20 = 0 then writeln(f);
end;
close(f);
end;
procedure TestQuickSort;
begin
Init(MN);
QuickSort(1,n);
Ghi;
write('Fini Quick Sort'); readln;
end;
procedure TestMinSort;
begin
Init(MN);
MinSort;
Ghi;
write('Fini Min Sort'); readln;
end;
BEGIN
TestQuickSort;
{TestMinSort;}
END.

0 comments:

Post a Comment

Popular Posts