Bài toán tìm số chính trong 1 file

Cho một file text gồm rất nhiều số nguyên (không thể lưu vào mảng được) mỗi số cách nhau bởi ít nhất một dấu cách hay tab hay xuống dòng. Bạn hãy tìm một số có số lần xuất hiện quá nửa. Số này gọi là số chính của file đã cho. Nếu file không có số chính thì in ra NO, nếu có in ra số đó.

Bài toán này thuộc kiểu không dựa vào thuật toán căn bản nào cả (Dijkstra, Floyd, Đệ quy, QHD …). Ta phải dựa vào phân tích logic và kiến thức toán học để giải.

Gọi số số nguyên trong file đã cho là N, ta có nhận xét quan trọng sau đây:

Giả sử file có số chính là x, vậy thì nếu bỏ đi M số (M chẵn, M < N) trong đó có M/2 số bằng k và M/2 số còn lại khác k, thì còn lại (N – M) số và x vẫn là số chính của (N – M) số còn lại này.

Chứng minh: gọi số lần xuất hiện của x trong file là P thì 2 * P > N, ta có:

  • Nếu k = x, khi đó trong dãy còn lại x xuất hiện (P – M / 2) lần, rõ ràng 2 * (P – M / 2) = 2 * P – M > N – M nên x vẫn là số chính trong dãy này.
  • Nếu k != x, vậy thì trong số (M / 2) số khác k, nếu có x thì số lần xuất hiện của x trong đó cũng không vượt quá (M / 2), gọi là T và T <= M / 2, khi đó trong dãy còn lại x xuất hiện (P – T) lần, dễ thấy: 2 * (P – T) = 2 * P – 2 * T > N – 2 * M / 2 = N – M

Vậy trong cả 2 trường hợp ta đều có x vẫn là số chính của dãy còn lại.

Từ nhận xét trên ta có thuật toán:

Xét số thứ nhất cho bằng x, có 1 biến count = 1, xét sang số thứ 2, nếu bằng x thì count++, nếu khác x thì count--, cứ như thế sang số thứ 3, thứ 4, … khi nào count = 0 thì dừng lại, lúc này ta đã ngắt được 1 dãy và yên tâm rằng số chính (nếu có) thì đang nằm phía sau chờ ta, ta lại duyệt như thế tiếp, vậy thì số x cuối cùng là số chính (có thể thôi) và ta phải duyệt lại từ đầu 1 lần nữa để xem x có đích thực là số chính hay không.

Sau đây là code toàn bộ:

#include <stdio.h>
#include <conio.h>

void solve() {
  FILE* f = fopen("MAINNUM.INP", "rt");
  int N, i, ok = 1, t, x, count;
  fscanf(f, "%d", &N);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &t);
    if (ok) { // bắt đầu 1 đoạn mới
      x = t;
      count = 1;
      ok = 0; // mới méo gì nữa, cũ rồi
    } else {
      if (x == t) count++;
      else count--;
      if (count == 0) ok = 1; // hết đoạn
    }
  }
  rewind(f); // về đầu tệp
  fscanf(f, "%d", &N);
  count = 0;
  // đếm lại xem x có phải số chính
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &t);
    if (t == x) count++;
  }
  fclose(f);
  if (2 * count > N)
    printf("Main number is: %d", x);
  else
    printf("NO");
}

void main() {
  clrscr();
  solve();
  getch();
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s