30/09/2018, 18:50

Sắp xếp mảng có VÀI TỶ PHẦN TỬ theo thứ tự tăng dần

đọc vào từ 1 file
hàng đầu là số n (n rất lớn, vài tỷ)
n dòng, mỗi dòng là 1 số nguyên từ 0 đến 2000
in ra màn hình theo thứ tự từ nhỏ đến lớn những con số xuất hiện trong file đó và lặp lại bao nhiều lần.
mọi người giúp em bài này nhé! cám ơn nhiều!

hacked viết 21:06 ngày 30/09/2018

Giải thuật:
Bạn sử dụng một mảng có kích thước từ 2001 phần tử kiểu long (c++) hoặc kiểu longint (pascal).
Đầu tiên khởi tạo các phần tử của mảng có giá trị là 0.
Đọc file, đọc được số nào thì tăng giá trị của số đó trong mảng.
Xuất kết quả, duyệt từ 0 đến 2001, cứ một số, in số lần xuất hiện của số đó.

Code bằng pascal

var
    a: array[0..2000] of longint;
    fi,fo: text;
    x,i,j: longint;
begin
    //mở file
    readln(fi,n);
    fillchar(a,sizeof(a),0);
    for i:=1 to n do
    begin
        read(fi,x);
        inc(a[x]);
    end;
    for i:=0 to 2000 do
    begin
        for j:=1 to a[i] do writeln(fo,i);
    end;
    //đóng file
end.

Đạt Đỗ viết 20:55 ngày 30/09/2018

eo thứ tự từ nhỏ đến lớn những con số xuất

Số nguyên từ 0 đến 2000 thì dùng binsort ok rồi

Đạt Đỗ viết 21:01 ngày 30/09/2018

longlong mang[2002];
for(int i=0;i<2002;i++) mang[i]=0;

long long tmp;
for(long long i =0;i<n;i++){
    cin>>tmp;
    mang[tmp]++;
}

// in ra
for(int i=0;i<2002;i++){
   cout << i << " so lan: " << mang[i] << endl;
}

Trần Lê Trọng Thức viết 20:50 ngày 30/09/2018

bạn ơi, số lượng phần tử rất lớn (tới vài tỷ lận). còn 0-2000 là giá trị của mỗi phần tử mà ?

Đạt Đỗ viết 20:59 ngày 30/09/2018

đúng rồi số lượng phần tử là vài tỷ, nên dùng mảng đếm đó.

Trần Lê Trọng Thức viết 21:02 ngày 30/09/2018

dùng mảng như vậy thì Ram chịu k nổi. còn cách nào k bạn ?

Đạt Đỗ viết 21:01 ngày 30/09/2018

long long mang[2002] sao chịu không nổi, còn quá ít nữa chứ.

Trần Lê Trọng Thức viết 20:53 ngày 30/09/2018

Rồi. Mình đã hiểu thuật toán. Thanks bạn!

Trần Lê Trọng Thức viết 21:02 ngày 30/09/2018

thanks bạn!