MERGESORT

MERGESORT

MergeSort là một giải thuật hay, chia nhỏ dãy đầu vào,  sử dụng phương pháp trộn 2 dãy đã được sắp xếp. Ở đây mình xin giới thiệu source code kèm theo hướng dẫn.

CODE (C++)

void MergeSort(int A[], int L, int R)
          // *** Sắp xếp mảng A, gồm N phần tử bằng giải thuật MergeSort
          // *** Ý tưởng: Ta chia dãy số thành 2 dãy, sau trộn hai dãy này thành 1 dãy, dãy này là kết quả,
          //   hai dãy được chia phải được sắp xếp, để đảm bảo điều này,
          //      ta xem mỗi dãy là 1 dãy mới và cũng chia nhỏ như dãy ban đầu, đến khi dãy chia nhỏ đã sắp xếp
{
          if (L < R) // Nếu L == R, xem như dãy đầu vào có 1 phần tử, và dãy này đã được sắp xếp.
          {
                    int K = (L + R) / 2;
                    // Chia dãy đầu vào thành 2 dãy mới
                   MergeSort(A, L, K);
                   MergeSort(A, K + 1, R);
                  //Trộn hai dãy trên thành 1 dãy, trong đó trong đó vị trí phân cách giữa hai dãy
                  //                   ngầm định là K = (L + R) / 2
                  Merge(A, L, R);
          }
}

void Merge(int A[], int L ,int R)
          // *** Trộn hai dãy nằm kề nhau và được phân cách ngầm định là K = (L + R) / 2
          // *** Ý tưởng: Ta lần lượt duyệt các phần tử của cả hai dãy,
          //          ở mỗi lượt duyệt ta duyệt hai phần tử 1 của dãy I, 1 của dãy II
          //          so sánh 2 phần tử và lấy ra phần tử nhỏ hơn bỏ vào dãy Kết Quả,
          //          cứ như vậy 2 dãy được trộn với nhau
{
          // Vì trộn dãy không mang tính tự đổi chỗ, nên ta phải dùng một mảng trung gian,
          //          ở đây ta dùng mảng B là mảng chứa dãy cần trộn, A là mảng lưu dãy đã được trộn
          int B[MAXSL] = {};
          for (int u = L; u <= R; u++)
                    B[u] = A[u];

          int K = (L + R) / 2;
          int i = L;
          int j = K + 1;
          int t = L - 1;
          // Trộn hai dãy
          while (t < R)
          {
                    if ((B[i] <= B[j] || j == R + 1) && i != K + 1)
                    {
                              t++;
                              A[t] = B[i];
                              i++;
                    }
                    if ((B[i] > B[j] || i == K + 1) && j != R + 1)
                    {
                              t++;
                              A[t] = B[j];
                              j++;
                    }
          }
}

Các bạn có thể tải hoặc xem code tường minh hơn ở đây

Ngựa Sông

PHÉP CÔNG NHỊ PHÂN BẰNG PHÉP XOR

PHÉP CÔNG NHỊ PHÂN BẰNG PHÉP XOR

Chào mọi người! Hôm nay, mình xin giới thiệu giải thuật cộng 2 số nhị phân, lấy ý tưởng dựa trên các phép bit đơn giản (and, or, xor, not), cụ thể là phép XOR.

Phép XOR
Bảng chân trị:

Giá trị phép XOR bằng 0 khi cả hai chân trị đầu vào giống nhau, điều này đúng với N chân trị đầu vào có cùng chân trị, ví dụ: 0 xor 0 xor 0 ... xor 0 = 0, nhưng không đúng với 1 xor 0 xor 0 ... = ?

Bài toán phép cộng:
Khi ta cộng 2 số nhị phân, ta sẽ lần lượt cộng các số từ phải sang trái, dựa trên bản chân trị:

+ 0     1
0     0   1
1   1   10

Với 1 + 1 = 10 ta viết 0 và nhớ 1
Tức khi ký số KetQua[i] = A[i] + B[i] + Nho
nếu KetQua[i] >= 10 thì Nho = 1; KetQua[i] = KetQua[i] % 10; (%: chia lấy dư)
ngược lại Nho = 0;

Mối liên hệ giữa phép cộng Bit và Phép XOR

Ta có bản so sánh sau:

  Từ bản trên ta rút ra nhận xét:
KetQua[i] = A[i] xor B[i] xor Nho;
Nho = 1, nếu A[i] + B[i] + Nho > 1;
Nho = 0, ngược lại;

CODE (c++)

void Cong(bool A[], bool B[], bool KQ[])
{
  bool Nho = 0;
for (int i = SOBIT - 1; i > -1; i--)
{
KQ[i] = A[i] ^ B[i] ^ Nho; // Trong C++, phép XOR được ký hiệu là ^
if (A[i] + B[i] + Nho < 2)
Nho = 0;
else Nho = 1;
  }
}

Các bạn có thể xem code tường minh hơn ở đây.

Ngựa Sông