作者mistel (Mistel)
看板Grad-ProbAsk
標題[理工] 演算法 林立宇講義練習題
時間Mon Sep 2 00:57:30 2019
第13題，divide&conquer
題目
https://i.imgur.com/Q1Vn4K5.jpg
我的寫法
https://i.imgur.com/Wkwzcd4.jpg
主要是想問
1.我這樣的答題格式可以嗎？
2.我發現上面105年交大他有可能找不到最大值，所以試著修改了一下，但發現我的寫法wor
st case會變O(n)，這樣扣分會很嚴重嗎@@
還是我完全寫錯了...？
感謝問題板
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.219.48 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1567357052.A.956.html
1F：推 mathtsai: 1.設計演算法不是要你寫程式09/02 01:11
2F：→ mathtsai: 沒有人喜歡看程式 應該用文字&圖 說明你的方法09/02 01:12
原來如此@@！之前不知道
3F：→ mathtsai: 2.你的寫法是錯的 舉例 7 8 1 2 3 4 5 609/02 01:13
4F：→ mathtsai: 1<2 但是你卻會去找右半邊 這樣是不對的09/02 01:13
5F：→ mathtsai: 觀察一下每次二分搜的時候會有什麼性質09/02 01:14
6F：→ mathtsai: 這題是十分簡單的題目09/02 01:14
7F：→ mathtsai: 然後啊 如果你的code真的這樣寫 會噴error09/02 01:20
8F：→ mathtsai: 理由是mid-1,mid+1不一定能在Arr的宣告裡面09/02 01:20
瞭解，我原本想說用mod應該就不會了，但剛剛想想其實還是會...orz
9F：→ mathtsai: 應該要加一些邊界判斷之類的 (mid=1,mid=n => 回傳mid)09/02 01:21
請教m大，因為我一開始是卡在沒有key做binary search
剛剛想到，如果我是拿A[low],A[mid],A[high]這三個來做比較不知道是否可行呢？
像是這樣
https://i.imgur.com/bcjYe0U.jpg
10F：→ mistel: 我又忘記加上bound check QQ09/02 07:50
※ 編輯: mistel (114.136.219.48 臺灣), 09/02/2019 07:51:37
11F：→ JKLee: 先把array的頭尾接在一起形成一個環09/02 08:06
12F：→ JKLee: 要把環分開成兩個部分要切斷兩個點09/02 08:06
13F：→ JKLee: 你的演算法23451會出錯09/02 08:10
14F：→ JKLee: 先暫時不要去想array的index。09/02 08:14
15F：→ JKLee: 如果有一個環， 09/02 08:14
16F：→ JKLee: 環上的數字已經sort好了， 09/02 08:14
17F：→ JKLee: 你會怎麼找最大的數字? 09/02 08:14
J大，我知道要找兩個點切割子問題，但我真的想不通要怎麼切才會確定最大的值會在我留
下來的那一塊...
※ 編輯: mistel (114.136.219.48 臺灣), 09/02/2019 12:22:22
18F：→ Ricestone: 你新的想法沒錯吧，就是每次都看這一半正不正常09/02 12:58
19F：→ Ricestone: 差在該怎麼停下來，所以確認mid是不是斷點，斷在左邊還 09/02 13:05
20F：→ Ricestone: 是右邊09/02 13:05
21F：→ mathtsai: 新的一樣是錯的 4 5 1 2 就錯了09/02 13:38
22F：→ mathtsai: 然後你新的寫法一樣是在寫程式 09/02 13:38
23F：→ Ricestone: 就是要先確認斷點啊09/02 13:39
24F：→ mathtsai: 分成一些case寫下來 (1)...(2)...(3)... 09/02 13:42
25F：→ mathtsai: 條列式就能說明你的方法了 教授也一目瞭然 09/02 13:43
26F：→ mathtsai: 這題如果我沒猜錯 元素應該都不能重複 09/02 13:46
27F：→ mathtsai: 不然 1 1 1 1 1 1 1 1 1 5 1 這樣子根本不能二分搜 09/02 13:48
28F：→ mistel: 我懂了，我應該再檢查mid這個點的左右鄰居，確認最大的點 09/02 14:46
29F：→ mistel: 我會記住用這種答題方式答題，感謝m大J大跟R大!!!! 09/02 14:50
30F：→ mathtsai: 不對 你的回答表示你沒有懂 09/02 15:04
我的意思是遞迴的中斷條件修改成：
若中點確實大於左右端點，
那我再檢查中點是否大於左鄰居跟右鄰居，
成立，則中點最大；
否則，若左鄰居比中點大，遞迴搜尋左半邊；
否則，右鄰居大，遞迴搜尋右半邊；
我想法是數列是遞增的，
所以如果中點是最大，那它一定大於端點且大於左右鄰居（代表左半數列跟右半數列都比中
點小），如果中點不是最大，那必然左鄰居跟右鄰居有一個比中點大，我就往那一邊繼續搜
尋
所以我只要兩個條件都成立，這個就是最大 ...
請問這樣子想法還是不對嗎，其實我不知道我到底是方向就錯了還是細節就錯了，請再指點
一下，麻煩了
※ 編輯: mistel (114.136.219.48 臺灣), 09/02/2019 16:51:39
31F：→ mathtsai: 還是不對啊 7 8 1 2 3 4 5 6 這個例子一樣不會過 09/02 19:17
32F：→ mathtsai: 你可以動手舉幾個例子 09/02 19:19
33F：→ mathtsai: 看看最大的在左半和右半的時候 會有什麼樣的性質 09/02 19:20
34F：→ Ricestone: 為什麼又跑回去了？判斷該往哪一半就是你前一個想法啊 09/02 21:19
35F：→ Ricestone: 停止條件就是mid左右有沒有斷點，斷點就是後面比前面小 09/02 21:20
36F：→ Ricestone: 如果到最後都找不到就是沒斷點（也可以一開始就判斷） 09/02 21:21
37F：→ Ricestone: 反正不管是哪個部份，左端比右端小，數列就是正常 09/02 21:26
38F：→ Ricestone: 判斷mid左右有沒有斷點，其實就是在確認子數列的端點有 09/02 21:26
39F：→ Ricestone: 沒有發生斷點 09/02 21:27
40F：→ mistel: 好的，瞭解，要判斷的是mid左右是不是有斷點 09/03 08:44
41F：→ mathtsai: 我覺得"判斷左右"這句 你又要跑去檢查+1,-1了... 09/03 14:13
42F：→ mathtsai: 把數列切半，觀察哪一半有發生左端比右端大的狀況 09/03 14:14
43F：→ mathtsai: 如果左右都沒有這種狀況，代表左右都sort好了 09/03 14:15
44F：→ mathtsai: 那麼左右兩半的右端比較大的就是最大元素 09/03 14:15
45F：→ mathtsai: 哪一半的左端>右端，就繼續遞迴找那一半 09/03 14:16
46F：→ mathtsai: 短短幾句話不就解決了嗎... 09/03 14:17
47F：→ mistel: 真的太菜了QQ我理解這個問題會發生的狀況跟性質了 感謝你 09/03 14:53
48F：→ Ricestone: 檢查斷點跟一次兩子列都檢查是兩種不同的做法而已 09/03 16:24
49F：→ Ricestone: 只是只檢查左子列+判斷左斷點跟一次檢查兩子列的差異 09/03 16:26