[問題] 不使用乘法的計算與排序問題

看板C_and_CPP作者 (sigh)時間9年前 (2015/04/15 00:42), 9年前編輯推噓8(8推 0噓 24→)
留言32則, 10人參與, 最新討論串1/1
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) GCC 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 問題(Question)： Q1. 不使用乘法如何有效率計算 X*Y 的結果 Q2. 已知兩個array，裡面的元素都已經是排序好的順序，不使用 教科書裡面的經典的排序方法(如:quick sort, merge sort 等) 把兩個array裡面的所有元素合併到另外一個新的array內 所有元素也是排序後的順序 餵入的資料(Input)： Q1. X, Y 兩個整數，不需考慮overflow的問題 Q2. A[] = {1,3,4}, B[]={2,5,7}，二者都可能是動態大小的資料量 預期的正確結果(Expected Output)： Q1. 達成正常乘法的效果，但是用更有效率的方法 Q2. C[] = {1,2,3,4,5,7} 錯誤結果(Wrong Output)： N/A 程式碼(Code)：(請善用置底文網頁, 記得排版) 抱歉，程式能力不好，想來這邊請教"想法"就好 Q1. 我有兩個想法 法1. X*Y = X + X + ...+ X，自加Y次，所以可以用一個簡單迴圈配合加法完成 法2. 把Y轉成2進位表示，例如 3*12 = 3*(1100) = 3<<3 + 3<<2 所以可以用mask的方式知道Y裡面有那幾個bit是1，便可以對X做位移後加法 不過直接寫起來，code似乎又臭又長 -_-，且如果遇到負數的話不知是否適用? 請益是否有更聰明的方法 Q2. 我起先想到的是空桶排序，設計一個空的array，size = A B array中元素的最大值 例如: X[7]={0} 然後把兩個array裡面每一個元素放到值所相對應的位置 即 X[a[i]] = a[i]; X[b[j]] = b[j]; 全部都放好後，把X裡面非0的元素取出來就會是排好的結果 但是，一想完之後發現缺點百出 -_- 1. 如果A B array裡面有0值的元素，這個想法就gg 2. 如果A Barray裡面有重複值的元素，這樣排可能會出錯 補充說明(Supplement)： 希望各位大大提供想法即可 如果違反版規，不適合在此發問的話請不吝告知，感謝 ^^ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.161.13.98 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1429029731.A.246.html
推
04/15 00:45, , 1F
看起來像是作業題...是作業的話建議問 Q2 的限制範圍
04/15 00:45, 1F
→
04/15 00:45, , 2F
不然單講不能用傳統方法一來太籠統, 二來排序也就這些方法
04/15 00:45, 2F
→
04/15 00:46, , 3F
這看起來像是要你們回答某種特定的演算法出來的樣子
04/15 00:46, 3F
→
04/15 00:47, , 4F
Q1 其實你的想法就差不多了, 仔細考慮一些細節就能寫的出來
04/15 00:47, 4F
→
04/15 00:47, , 5F
LPH66大：是面試題(汗) 空白卷自由發揮，所以想法不
04/15 00:47, 5F
→
04/15 00:47, , 6F
要你們不用直接相乘, 計算步驟就會變多這很自然的
04/15 00:47, 6F
→
04/15 00:48, , 7F
拘 XD 所以沒有特別強調 限制條件
04/15 00:48, 7F
→
04/15 00:49, , 8F
面試題嗎...是我的話我會當場問面試官這個範圍在哪
04/15 00:49, 8F
→
04/15 00:49, , 9F
bucket sort 也是許多教科書裡會提到的排序
04/15 00:49, 9F
→
04/15 00:50, , 10F
算不算「傳統做法」其實是可以吵(?)一下的 XD
04/15 00:50, 10F
→
04/15 00:51, , 11F
恩 對阿，題目上面只有提到不使用 quick sort, merge
04/15 00:51, 11F
→
04/15 00:51, , 12F
sort, 但是又多加一個, etc 實在讓人困惑
04/15 00:51, 12F
→
04/15 00:52, , 13F
大概是自己經驗不夠，應該要及時反問這個疑問 XD
04/15 00:52, 13F
※ 編輯: signdecoded (118.161.13.98), 04/15/2015 00:52:48
→
04/15 00:54, , 14F
題目只有暗示可以善用兩個array都已經是排序好的特性
04/15 00:54, 14F
推
04/15 01:05, , 15F
Q1 和你一樣, 用 shift 和加法 , Q2 已排序好的話可保證
04/15 01:05, 15F
→
04/15 01:06, , 16F
是 O(m+n) , 就只有考 array index 控制.
04/15 01:06, 16F
→
04/15 02:10, , 17F
Q1 X*Y = X*(Y/2) + X*(Y-(Y/2)) 遞迴
04/15 02:10, 17F
推
04/15 05:46, , 18F
乘法不一定慢，要看cpu周期
04/15 05:46, 18F
→
04/15 05:48, , 19F
不用教科書的排序，你以為我是天才，發明的出來
04/15 05:48, 19F
推
04/15 07:13, , 20F
方法2
04/15 07:13, 20F
→
04/15 22:17, , 21F
http://codepad.org/rDMUxxMS Q1 方法2寫起來不一定
04/15 22:17, 21F
→
04/15 22:17, , 22F
又臭又長
04/15 22:17, 22F
→
04/15 22:59, , 23F
感謝cismjmgoshr, 這方法看起來也不賴 清楚易懂
04/15 22:59, 23F
→
04/15 23:00, , 24F
感謝大家的意見，又學到了觀念RRR(程式果然要再加強)
04/15 23:00, 24F
推
04/16 12:28, , 25F
Q2用2個index分別指到2個陣列的頭，每次比較兩邊被指到的值
04/16 12:28, 25F
→
04/16 12:29, , 26F
把比較小的那個填到放結果的陣列裡；被選到的index再往後++
04/16 12:29, 26F
→
04/16 12:31, , 27F
....這樣好像是mergesort...抱歉0rz....
04/16 12:31, 27F
→
04/16 23:17, , 28F
萬惡的etc.
04/16 23:17, 28F
推
04/19 21:22, , 29F
其實覺得 Q1 的題目要求很無理，要比指令等級的乘法快幾乎
04/19 21:22, 29F
→
04/19 21:22, , 30F
沒可能吧？
04/19 21:22, 30F
推
04/19 21:33, , 31F
阿 眼殘看錯題目 Sorry
04/19 21:33, 31F
推
08/23 16:21, , 32F
08/23 16:21, 32F
‣ 更多 signdecoded 的文章
文章代碼(AID): #1LBKDZ96 (C_and_CPP)