Tần số

tần số

Cho dãy số nguyên dương, số lần xuất hiện của một số được gọi tần số của số nguyên đó. Hãy tìm số nguyên dương có tần số cao nhất và tần số tương ứng của nó.
Dữ liệu vào: Cho từ file văn bản MAX.INP bao gồm:
Dòng đầu tiên chứa một số nguyên N( 1≤ N ≤ 10000) là số lượng các số nguyên trong dãy.
Mỗi dòng trong N dòng tiếp theo chứa số nguyên M( 1≤ M ≤ 1000) trong dãy.
Kết quả: Ghi ra file văn bản MAX.OUT, gồm 2 số nguyên viết trên một dòng, số thứ nhất ghi số nguyên có tần số cao nhất, số thứ 2 là tần số của nó( trong trường hợp có nhiều số nguyên có tần số cao nhất bằng nhau, hãy đưa ra số nguyên nhỏ nhất và tần số của nó). Hai số cách nhau một ký tự trắng.

MAX.INP
MAX.OUT

MAX.INP
MAX.OUT

9
1
2
5
6
3
7
2
5
2
2 3

7
2
4
6
7
7
2
4
2 2


 Hướng dẫn giải.
* nghiên cứu cấu trúc dữ liệu cần có để lưu trử nó - Dòng đầu tiên chứa một số nguyên N( 1≤ N ≤ 10000) là số lượng cỏc số nguyên trong dãy. Dựa vào đây ta thấy dãy này có tối da 10.000 phần tử --> có thể khai báo một mảng 1 chiều gồm 10.000 phần tử - Mỗi dòng trong N dòng tiếp theo chứa số nguyên M( 1≤ M ≤ 1000) trong dãy. Các số đó là số nguyên có giá trị từ 1->1000. Từ đó suy ra đây là mảng các phần tử nguyên có giá trị lớn nhất là 1000 Như vậy nếu dùng Pascal thì sẻ là Var A:array[1..10000] of integer; Tổng bộ nhớ này mới chỉ dùng đến 20.000Byte ~ 20KB thôi (Pascal mặc định cho phép khai báo chỉ là 64KB) Như vậy chúng ta đã khai báo để lưu được dữ liệu đầu vào * Thuật toán: Với bài này thì có nhiều cách C1: Bạn đếm số lượng của từ số có trong mảng vừa đọc được, rồi tìm ra số có tần số xuất hiện nhiều nhất C2: Bạn sử dụng 1 mảng tiếp với quy tắc: Phần tử thứ I lưu trử số lần xuấn hiện của số I. Vì số I chỉ chạy từ 1-->1000 nên ta cũng chỉ cần khai báo mảng gồm 1000 phần tử, giá trị xấu nhất có thể lớn nhất là 10.000 = số lượng phần tử (cái này mà khai báo kiểu longint thì dùng phê luôn) Như vậy có thêm mảng B:array[1..1000] of longint; Mảng B mất thêm 1000*4=4.000Byte ~ 4KB nữa (vẫn dư chán). Và đây là thuật toán với cách 2
Code:
For i:=1 to N do
B[A[ i ]]:=B[A[ i ]]+1;
Thuật toán tính tần số chỉ có vậy thôi các bạn nà Giải thích: A[ i ] là một số nguyên trong dãy có giá trị từ 1-->1.000 Như vậy khi duyệt từ đầu dãy đến cuối dãy gặp phần tử nào thì tăng giá trị mảng B tại phần từ đó Như vậy sau khi vòng for đó chạy xong thì các giá trị trong mảng B chính là tần số của chỉ số đó Khi có Tần số rồi thì ta thực hiện tìm Max thôi Đoạn còn lại thì đơn giản. Tinh chỉnh hơn chút nữa: Đó là chúng ta không đọc vào mảng mà là tính trực tiếp luôn trừ tệp
Code:
Var B:Array[1..1000] of Longint;
N,I:longint;
tg:integer;
f,f1:text;
csmax:integer;
Begin
assign(f,`Max.INP`); reset(f);
readln(f,N);
for I:=1 to N do
Begin
readln(f,tg);
B[tg]:=B[tg]+1;
End;
csmax:=1;
for i:=1 to 1000 do
if B[csmax] assign(f1,`Max.OUT`); rewrite(f1);
write(f1,csmax,` `,B[csmax]);
close(f);