作者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/cn.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