Đến nội dung

Hình ảnh

Cần bao nhiêu lượt để xác định $a_i$?

- - - - -

  • Please log in to reply
Chủ đề này có 1 trả lời

#1
chuyenndu

chuyenndu

    Trung sĩ

  • Thành viên
  • 177 Bài viết

Các số $a_1,a_2,...,a_{2022}$ là một hoán vị của 1,2,...,2022 và An không biết giá trị của các số $a_i$. Ở mỗi lượt, An có quyền chia các số trên thành $1011$ cặp theo ý cậu ấy muốn và Bình sẽ cho An biết ở mỗi cặp thì số nào có giá trị lớn hơn. Hỏi An cần bao nhiêu lượt để xác định được các số $a_i$?


Bài viết đã được chỉnh sửa nội dung bởi chuyenndu: 19-11-2022 - 11:01


#2
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4990 Bài viết

Không biết đề hỏi số lượt chính xác hay sao. Mình tìm được một chặn trên như sau.

Xét trên trường hợp tổng quát cho $n$ số $a_1, a_2, \ldots, a_n$, nếu có lẻ số khi nhóm cặp thì ta coi như không đánh giá số đó. Đề bài tương đương với sắp xếp các số đã cho theo thứ tự tăng dần.

Gọi $S(n)$ là số lượt ít nhất cần có để sắp xếp $n$ số bất kỳ với trợ giúp của bạn Bình. Ta xây dựng một thuật toán như sau:

Đầu tiên, ta đánh giá các cặp $(a_1, a_2), (a_3, a_4), \ldots$ và chọn ra hai tập $B=\{b_1, b_2, \ldots\}$ và $C=\{c_1,c_2,\ldots\}$ với $B$ là tập các số nhỏ hơn và $C$ là tập các số lớn hơn.

Tiếp theo, ta sắp xếp các tập $B,C$ theo thuật toán cho $\frac{n}{2}$. Mà chú ý rằng, Bình có thể thực hiện các phép so sánh trên cả $B$ lẫn $C$ đồng thời, nên ta chỉ cần tổng cộng $S\left(\frac{n}{2}\right)$ bước.

Sau đó, ta cần $T\left(\frac{n}{2},\frac{n}{2}\right)$ bước để "nhập" hai tập $B,C$ đã sắp xếp.

Một thuật toán "ngây thơ" để nhập hai dãy đồng điệu tăng dần có độ dài lần lượt $m_1, m_2$ sẽ cần tối đa $m_1 + m_2$ bước.

Do đó:

\[S\left( n \right) \le 1 + S\left( {\frac{n}{2}} \right) + T\left( {\frac{n}{2},\frac{n}{2}} \right) \le 1 + S\left( {\frac{n}{2}} \right) + n\]

Tới đây ta thấy việc "chia để trị" quen thuộc trong các thuật toán. Bạn đọc có thể "trực tiếp" thi triển vế phải liên tục cho đến khi có $n=1$, hoặc mở rộng $n$ lên một lũy thừa bậc 2.

Dù sao đi nữa, ta cũng sẽ thu được một chặn trên như sau:

\[S\left( n \right) \le \left\lceil {{{\log }_2}n} \right\rceil  + 2n\]

 

Tất nhiên, chặn trên này chưa phải là tối ưu :D Nếu làm chặt $T\left( {\frac{n}{2},\frac{n}{2}} \right)$ thì hy vọng ta sẽ có \[T\left( {\frac{n}{2},\frac{n}{2}} \right) \le \frac{n}{2} \]

Khi ấy:

\[S\left( n \right) \le \left\lceil {{{\log }_2}n} \right\rceil  + n\]

Và biết đâu có thể làm mạnh hơn? :)


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.




1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh