[理工] 演算法 林立宇講義練習題

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