[Algorithms] Tìm số nhỏ nhất trong 3 số không dùng phép so sánh

Đề bài: Viết chương trình (C) để tìm số nhỏ nhất trong 3 số.

1. Đơn giản nhất, dùng phép so sánh.

#include <stdio.h>

int smallest(int x, int y, int z)
{
  if (x>y){
    return y>z?z:y;
  }
  else{
    return x>z?z:x;
  }
}

int main()
{
   int x = 12, y = 15, z = 5;
   printf("%d", smallest(x, y, z));
   return 0;
}

2. Nhưng không được dùng phép so sánh thì sao?

2.1. Sử dụng phương pháp trừ dần

Ta sử dụng 1 biến counter c, khởi tạo c = 0, chúng ta sẽ trừ dần giá trị đồng thời của x, y, z cho 1, với mỗi lần như vậy ta tăng c lên 1. Số nhỏ nhất trong 3 số x, y, zsẽ bằng 0 đầu tiên khi trừ dần như vậy. Và giá trị của c sẽ là giá trị của số đó.

#include <stdio.h>

int smallest(int x, int y, int z)
{
  int c = 0;
  while ( x && y && z )
  {
      x--;  y--; z--; c++;
  }
  return c;
}

int main()
{
   int x = 12, y = 15, z = 5;
   printf("%d", smallest(x, y, z));
   return 0;
}

Nhưng cách này không sử dụng được với số âm.

2.2. Sử dụng phép chia

Ta để ý rằng trong C, 0 == false, do vậy, nếu y < x thì y/x == 0 == false. Lợi dụng việc đó ta viết lại smallest như sau:

#include <stdio.h>

int smallest(int x, int y, int z)
{
  if(!(y/x)){
    return !(z/y)?z:y;
  }else{
    return !(z/x)?z:x;
  }
}

int main()
{
   int x = 12, y = 15, z = 5;
   printf("%d", smallest(x, y, z));
   return 0;
}

Phương pháp này không sử dụng được khi 1 trong 3 giá trị của x, y, z bằng 0

2.3. Sử dụng dịch bit và phép trừ

Ta nhận thấy rằng đối với 2 số x, y ta có INT_MIN <= (x-y) <= INT_MAX Ta sẽ có giá trị min của x và y là:

min = y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))

Giải thích như sau: ta thấy rằng phép dịch giá trị (x-y) sang phải 31 bits (CHAR_BIT*4 - 1) sẽ cho ta biết (x-y) > 0 hay (x-y) < 0. Trong trường hợp (x-y) > 0 vậy bit thứ32sẽ bằng 0 (bit 32 là bit dấu, 0 là dương, 1 là âm), ngược lại (x-y) < 0 thì bit 32 sẽ bằng 1 (bit dấu bằng 1). Vậy, trong trường hợp (x-y) > 0 hay x > y:

min = y + (x-y)&0 // min == y

Ngược lại,

min = y + (x-y)&1 // min == x

Từ đó ta implement hàm tìm min 2 số như sau:

#define CHAR_BIT 8
int min(int x, int y){
  return y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)));
}

Từ đó ta có hàm tìm min 3 số như sau:

#include <stdio.h>
#define CHAR_BIT 8

int smallest(int x, int y, int z)
{
  return min(x,min(y,z));
}

int min(int x, int y){
  return y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)));
}

int main()
{
   int x = 12, y = 15, z = 5;
   printf("%d", smallest(x, y, z));
   return 0;
}

Trên đây là 3 cách để tìm min 3 số mà không dùng phép toán so sánh. Cảm ơn các bạn đã theo đọc hết bài. Hẹn gặp lại trong những thử thách thú vị khác.