[機統] 排列組合問題

[agnes12 (agnes)]

因為找不到分類，所以挑了機統，
第一次在數學版po文，有錯麻煩跟我說下~~

這題我和室友都想不出來，
他說我可以來這也許能解決我的問題~~

consider the following procedure for determine whether a
given name appears in an alphabetized list of n names.

Step1: Choose the name at the middle of the list.
(if n=2k, choose the kth name); if that is the given name, you are done.
if the list is only one namelong, you are done.
if you are not done, go to step 2.

Setp2: If the given name comes alphabetically before the name at the
middle of the list, apply Step1 to the first half of the list.
Otherwise, apply Step 1 to the second half of the list.

If n is very large, the maximum number of steps required by this procedure
is close to  lo _____

Ans: log(n), 以2為底

感謝大家!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 108.3.154.49
推 znkt49235781:n=1 時一次 n=2時兩次 n=4時三次 (加一倍多一次)
→ znkt49235781:n=2^m 時 m+1次 極限時約為log(2,n)