創作內容

0 GP

ZeroJudge - e189: 3的倍數 - 面試題 解題心得

作者:Not In My Back Yard│2019-04-24 12:48:50│贊助:0│人氣:51
題目連結:


題目大意:
在不使用除法、取餘運算子(「/」和「%」)的情況下,給定一非負整數 n (0 ≦ n ≦ 2, 147, 483, 647),判斷 n 是否可否被 3 整除。



範例輸入:
1
2
3


範例輸出:
NO
NO
YES


解題思維:
本問題有個特別的性質:在二進位表示法之下,判斷一數是否可被 3 (十進位的 3 )整除的方法跟在十進位之下判斷是否可以被 11 整除的方法是一樣的。

也就是將一數的位數交叉相加相減(第一位 - 第二位 + 第三位……即奇位數之和 - 偶位數之和)之後的結果判斷是否可以被 11 整除。而這個位數和又可以套用同樣的方法再遞迴下去,直到可以直接判斷。

而所有 D 進位的數字,判斷是否是 D + 1 的倍數之方法都是一樣的。原因如下:

設一個 D 進位的數字 N = …… A ,其中 A 代表 N 的其中一個位數且 0 ≦ A < D。則 N = …… A × D ^ 3 + A × D ^ 2 + A × D ^ 1 + A × D ^ 0

因此,我們可以推得出 N 取 D + 1 的餘數 ≡ …… - A + A - A + A (因為 D ≡ -1 (mod D + 1)),也就推出「判斷 N 是否為 D + 1 的倍數」與「判斷其奇位數和 - 偶位數和(或是偶位數和 - 奇位數和)是否為 D + 1 的倍數」是等價的。

因為本題是要判斷是否可以被 3 整除,而我們可以只使用位元運算(左移 << 、右移 >> 運算子)便將一數的二進位表示法找出來。再將奇偶位數分開相加再相減,然後套用相同的策略。直到可以直接判斷是否為 3 的倍數(n = 0 ~ 2 的時候)。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=4369895
All rights reserved. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:程式題目解題心得|數論

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★inversion 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:ZeroJudge - ... 後一篇:ZeroJudge - ...

追蹤私訊

作品資料夾

killhannr親愛的巴友
實況影片持續更新,有空來小屋逛逛,歡迎訂閱YT頻道ヽ(*´∀`)ノ看更多我要大聲說5小時前


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】