PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

搜尋不在陣列中的元素

看板Prob_Solve (計算數學 Problem Solving)作者ptthuey (天秤守望者)時間11年前 (2013/09/23 18:22)推噓0(0推 0噓 2→)

留言2則, 2人參與討論串1/1

1) The element being searched for is not in an array of 100 elements. What is the average number of comparisons needed in a sequential search to determine that the element is not there. a) the elements are completely unordered. b) the elements are ordered from smallest to largest. c) the elements are ordered from largest to smallest. 2) The element being searched for is not in an array of 100 elements. What is the average number of comparisons needed in a sequential search to determine the position of the if the elements are completely unordered. 以下是變化題 3) The element being searched for is not in an array of 100 elements. What is the maximun number of comparisons needed in a sequential search to determine that the element is not there. a) the elements are completely unordered. b) the elements are ordered from smallest to largest. c) the elements are ordered from largest to smallest. 4) The element being searched for is in an array of 100 elements. What is the average number of comparisons needed in a sequential search to determine that the position of the element? a) the elements are completely unordered. b) the elements are ordered from smallest to largest. c) the elements are ordered from largest to smallest. 我在想有沒有在array中的差別應該是能不能指定要看在特定位置上的元素，所以在4)array中有排序的話應該可以用binary search之類的搜尋方法， 1)的a 因為沒有排序只能一個個全部找過一遍，所以是100， 1)的b c 因為有依大小排，可以隔一格取，看兩邊邊界就可以知道包含的範圍，所以我想可以只找一半的elements，所以是50 2) 的部分就有點不確定了，我看到的答案上是寫 75，不過不知道是用什麼方法 3）的部分 a)一定是100 b跟c我想不太到 maximum 跟 average 的差別，應該都是要找50次吧 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.109.19.171 ※ 編輯: ptthuey 來自: 140.109.19.171 (09/23 18:23)