Re: [問題] 針對一些考題的疑問。

看板C_and_CPP作者EdisonX (閉上眼的魚)時間12年前 (2012/01/08 18:58)推噓2(2推 0噓 5→)

留言7則, 6人參與討論串3/6 (看更多)

2012/01/10 修正範例錯誤,新增三份註解 ※ 引述《Arton0306 (Ar藤)》之銘言：我只是想針對 Q2 做一點意見。 : : Q2.寫一個檢查輸入為3倍數的函數，但不能使用除法和餘數。 : : 除了使用 : : while(input>2){input-=3 check=input}if(check)... : : 這種算法外，還有更好的算法嗎? : 這方法不錯了 : 不然利用3倍數的特性寫一個function 把原數字轉字串後取出每個位的數字求和 : 看是否大於9 是的話 recursive 不是的話若數字是0 3 6 9那就是3倍數之前某論壇也是看到這題，目前大多都放在這解法上，後來想到另一解法。看一下這特性 - 97 mod 3 = (64+32 + 1) mod 3 = 1 mod 3 = 1 這特性是花五分鐘觀查出來的，我也不保證這是最快的方式， (面試的時候可能是很久的時候，所以第一次看到可能會想不到) 2^n + 2^(n+1) 必為 3 之倍數所以用 shift right + and gate 可做一點加速，效率會不會比較快留著待分析 ( 和布斯乘法器一樣，有些情況會比較慢 ) 類似觀念可以變成用 3bits、4bits 方式分析，(3 bits 可能不好做或不能做) ( 就像是改善形的布斯乘法器 ) unsigned Mod3(unsigned x) { unsigned sum; do{ sum = 0; while(x) { sum+=x&0x3; // 取最後 2 bits x>>=2; } x = sum; }while(sum>3); return sum==3 ? 0 : sum; // 最後等於 3 額外判斷 } 這應也不是最快的方式，在猜想最快的方式應該是用 floating multi. 去做，可能一、二行就出來了，只是那個 magic number 可能面試的時候時間有限，找不出來吧。 ----- 這兩天網路掛掉，想加註解都沒辦法，下面提供一點其他想法。 [註1] sum+=x&0x3 ，其實可直接寫類似 sum+= ( (x&0x3==0x3) ? 0 : x&0x3 ); 直接將 3 跳過，傳回值也比較直覺 return sum; [註2] 如 bleed1979 大所云 (#1F2Pr4Of)，後來也覺得 shift right 是否不合題意，此處若不用 shift right, div, mod ，想到的方式是改用 shift left (變乘法了) + 0x03 mask (也是配合 shift left) 完成, 枝節不多細磨, 有興趣亦可實作。 [註3] 其實觀查出來是很單純的列出數列 1 2 4 8 16 32 64 ... 後來也觀查出任意數 n 之解法，chubiei 大推導漂亮 (#1F2Q6CBz)，有興趣之網友可繼續詳參該文之討論。 -- If there is no tomorrow, I want to see u last time. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.76.201

推

Arton0306

01/08 20:07, , 1^F

01/08 20:07, 1^F

→

EdisonX

01/08 20:11, , 2^F

01/08 20:11, 2^F

→

DEATHX

01/08 21:29, , 3^F

01/08 21:29, 3^F