+2

[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 xy 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.

ありがとうございます。


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.