Tạo dãy số ngẫu nhiên không trùng trong C/C++

Tạo dãy số ngẫu nhiên không trùng trong C++

Làm sao để tạo dãy số ngẫu nhiên không trùng nhau trong C/C++? Hãy cùng Nguyễn Văn Hiếu đi giải quyết bài toán sinh số ngẫu nhiên không trùng trong bài viết này nhé. Mình sẽ hướng dẫn các bạn hai cách khác nhau để tạo dãy số ngẫu nhiên không trùng lặp. Bắt đầu nào…

1. Tạo dãy số ngẫu nhiên không trùng

Nếu bạn chưa đọc bài viết hướng dẫn tạo số ngẫu nhiên, bạn có thể đọc trước để hiểu về hàm tạo số ngẫu nhiên trong bài viết này.

Bài này mình sẽ không giải thích chi tiết cách hàm tạo số ngẫu nhiên hoạt động. Mình sẽ tập trung giải thích cách để tạo các số ngẫu nhiên không trùng lặp.

Bài toán 1: Hãy in ra 10 số nguyên ngẫu nhiên khác nhau trong đoạn [1, 100]

Bài toán 2: Hãy xáo trộn vị trí các phần tử trong mảng số nguyên có n phần tử. Hiểu cụ thể hơn chính là xáo trộn dãy chỉ số từ [0, n-1] .

Mình sẽ hướng dẫn các bạn 2 cách khác nhau, hãy cùng đi vào cụ thể từng cách nào.

2. Tạo dãy số ngẫu nhiên khác nhau sử dụng map

Đây là một cách trâu bò, ý tưởng của chúng ta là sinh số ngẫu nhiên, kiểm tra nó đã có hay chưa? Nếu chưa có thì mới lấy. Như vậy, cuối cùng ta sẽ thu được dãy số có các giá trị khác nhau.

Cấu trúc dữ liệu map cho chúng ta thực hiện kiểm tra với độ phức tạp là O(1). Điều này giúp code chúng ta chạy nhanh hơn.

Lưu ý: Số lượng số cần random phải >= số lượng số có thể random. Do vậy, mình cần check như sau:

Nếu vi phạm, code sẽ bị lặp vô tận vì không tìm được số thỏa mãn.

Kết quả chạy thử:

Trong trường hợp số lượng số cần random ít hơn số lượng giá trị có thể random thì đây là cách tốt nhất mà mình biết. Tất nhiên, trong trường bằng nhau như mình chạy thử phía trên thì cũng không quá lâu đâu. Nhiều trường hợp vẫn nhanh hơn cách thứ 2 đấy.

Tuy nhiên, đây không thực sự là cách tối ưu vì có thể phải chờ rất lâu mới có được những kết quả random cuối cùng. Các bạn hãy thử dùng cách 2 và so sánh giúp mình nhé.

3. Tạo dãy số ngẫu nhiên không trùng với mảng

Thư viện algorithm trong C/C++ có một hàm giúp chúng ta xáo trộn các phần tử của mảng. Đó chính là hàm random_shuffle():

Để dễ hình dung, chúng ta sẽ đi ngay vào ví dụ cụ thể nhé.

Giả sử bạn cần sinh 50 số ngẫu nhiên có giá trị trong phạm vi [100, 1000000]. Bạn hãy tạo cho mình một mảng đủ để chứa 1000000 - 100 + 1 phần tử(100, 101, 102, …. 1000000). Chúng ta có thể làm như sau:

Tiếp đến, ta cần xáo trộn mảng này. Sau đó, việc của bạn rất đơn giản, lấy 500 phần tử đầu tiên của mảng.

Code hoàn chỉnh của tất cả các bước như sau:

Kết quả chạy thử:

Mình chạy thử với code trên và số liệu như trên thì thấy chậm hơn nhiều so với cách số 1. Có vẻ là cách số 1 vẫn sẽ vô đối nếu như số lượng số cần random là nhỏ hơn nhiều so với số giá trị có thể random. Có lẽ thuật toán shuffle ~ 1 triệu phần tử mất nhiều thời gian.

Kết luận

Mình nhờ các bạn đánh giá độ phức tạp của hai giải thuật này. Hoặc nếu các bạn có cách làm khác, hãy để lại trong phần bình luận để mọi người cùng trao đổi.

Mình cũng tin rằng sau khi đọc hết bài chia sẻ này, các bạn đã có thể tự giải quyết hai bài toán mình đặt ra ở phần đầu. Do đó, mình sẽ không giải 2 bài tập đó nữa 😀

Hi vọng bài chia sẻ đã giúp các bạn có thể tạo dãy số ngẫu nhiên không trùng lặp sử dụng C/C++. Chúc các học tập tốt!

avatar
  Subscribe  
Notify of