Tìm số lớn nhất

#1

Nhâp vào số n, n dòng tiếp theo nhập mỗi dòng một số. Tìm số lớn nhất trong n số và xem số đó xuất hiện bao nhiêu lần.
Lưu ý: Giới hạn: 1<n<1 000 000 và 0<các số<100 000 000.
Mọi người cho em hỏi là nếu đề như trên thì làm thế nào ạ? Giới hạn to quá ạ.

#2

Đầu tiên viết hàm tìm giá trị lớn nhất. Sau đó viết hàm đếm số lần xuất hiện của số đó.

#3

Thế nhưng mà khoảng to thế kia thì khới tạo mảng kiểu gì ạ?

#4

Theo mình thì đó là ràng buộc của đề bài thôi, bạn nhập 10 số thôi cũng được mà?

#5

100000000 đối với kiểu long long cũng không vấn đề gì

#6

malloc :smiley: chứ sao. Bài này quan trọng là bao nhiêu số thôi.

1 Like
#7

Thế thì minh khai báo con trỏ ở kiểu long long hay long là ok ạ?

#8

long được rồi, 32 bit là đủ.

2 Likes
#9

Dùng 2 biến:

  • current_max (số lớn nhất hiện tại): khởi tạo = 0
  • count (đếm số lần xuất hiện): khởi tạo = 0

Dùng for từ 1 -> n:

  • Nếu số hiện tại < current_max thì bỏ qua
  • Nếu số hiện tại = current_max thì count++
  • Nếu số hiện tại > current_max thì gán current_max = số hiện tại, và count = 1

Thuật toán như vậy đúng ko ta?

2 Likes
#10

oops current_max = 0… do số dương nên count đặt tùy ý được vì sẽ bị reset sau bước lặp i=1 :slight_smile: chứng minh dưới đây có thể làm tương tự với bài trên.

Dùng quy nạp :smiley:
BB: 1 <= i < n
Đkt: Trước bước lặp thứ i, current_max chính là max(a[0…i-1]). Với i=1 nghiệm đúng, ta đi đến:
Đks: current_max = max(a[0…i]). Dễ thấy current_max >= max(a[0…i-1]) && a[i], suy ra theo tính bắc cầu.

Đó là một nửa bài toán. Còn count? max(range) luôn có mặt trong range ít nhất một lần (khác với cận trên :D) Ngoài ra current_max không giảm. Vậy count gán lại bằng 1 là đúng.

1 Like
#11

Vì điều kiện 0<các số<100 000 000 nên current_max = 0 cũng đúng mà?

Nói đúng hơn:

  • Nếu gán current_max = 0 thì khởi tạo count = 0
  • Nếu gán current_max = a[0] thì khởi tạo count = 1
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?