很莫名的, 3 的倍數面試問題筆者看過兩次,限制有點不同,仔細想想後,拿來當面試題目一點都不過份。

 

Q1. 如何「只用加減乘除法」判斷整數是否為 3 的倍數?

Q2. 如何「不用除法與取模」判斷整數是否為 3 的倍數?

 

Q1 是某碩士班面試題目,Q2 是某科技業面試題目。

為了簡化說明,我們先把範圍調到「正整數 x」,這假設也不過份,只是單純的 if-else 取絕對值,如果要用 bitwise hacker 取絕對值也無妨。

 

int input;
int x1 = (input >= 0) ? input : -input; // better
int x2 = (unsigned)input & ~( 1U<< (sizeof(input)*CHAR_BIT));

 

 

減法判斷

 

一種較低效但通用的方法是,進行連減判斷。

 

while(x>2) x-=3;
if(x==0) puts("yes");
else puts("no");

 

可推到判斷 n 之倍數。無庸致疑,非常低效。

 

乘法判斷

 

在可以進行乘法之情況下很容易,只要除 3 再乘 3 判斷就行。

 

if(x/3*3==x) puts("yes");
else puts("no");

 

可推到判斷 n 之倍數。

 

不用除法與取模

 

Q2 題意敘述有些爭議,有些網友認為,left shift operator 與 and operator 本身便是一種除法與取模之運算,如果這二個 operator 也被禁用的話,那就慢慢從減法判斷吧。

這裡假設可用 shift operator 與 and operator。

看到這題目 5 分鐘後 (很可惜,若是面試的話面試官不會等我 5 分鐘 ),想到以 binary 方式思考。

97 mod 3 = (64+32 + 1) mod 3 = 1 mod 3 = 1

一個莫名不知定理的東西推出來了:  2n + 2(n+1) 必為 3 之倍數

鑑於此思考模式之範例碼如下。

 

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 額外判斷
}

 

 很遺憾的,這方式雖比累減高,但效率比起其他方式,算很低。

另 3(dec) = 11 (bin),轉個念頭思考,判斷 10 進位之 3 ,和判斷 2  進位之 11 頗為相似,而題意只是要判斷「是否」為3之倍數,而不是真的要求「mod 3 之結果」,可以拿來做應用。

 

#include <stdio.h>
unsigned IsMulti3(unsigned x)
{
    unsigned i, remain=x;
    unsigned c0, c1;
    do{        
        c0 = c1 = 0U;
        // 偶位數 1 個數 : c0
        for(i=remain; i; i>>=2) c0+=(i&1U);
        // 奇位數 1 個數 : c1
        for(i=remain>>1; i; i>>=2) c1+=(i&1U);
        // c0-c1
        remain = (c0>=c1) ? c0-c1 : c1-c0;
    }while(remain > 3);
    return (remain==3 || remain==0);
}
int main()
{
    unsigned x=0;
    while(scanf("%u", &x)==1)
        printf("%u%u\n", IsMulti3(x), (x%3==0));
    return 0;
}

 

 

數學味頗濃的推廣..

 

不知道有沒有人發表過期刊,這問題可推廣到 「求 mod 任意數之值」,但推導過程實在有些煩鎖。

 

先以「只適用奇數」為例,令輸入為 x ,以 mod 5 而言

 

step 1 : 

1   mod 5 = 1 , 2   mod 5 = 2, 4 mod 5 = 4, 8 mod 5 = 3 
16 mod 5 = 1 , 32 mod 5 = 2, ....

每經過 4 bits 後,餘數開始循環。weight[4] = {1, 2, 4, 3}。

 

step 2 : 

x 第 0, 4, 8, 12, ... 之位元加總得 s0
x 第 1, 5, 9, 13, ....之位元加總得 s1 
x 第 2, 6, 10, 14, ....之位元加總得 s2
x 第 3, 7, 11, 15, ....之位元加總得 s3

 

step 3 : 

x = s0 * weight[0] + s1 * weight[1] + s2 * weight[2] + s3 * weight[3]。

 

step 4 :

若 x 小於 5 ,結束;否則回到 step 2。

 

 

既然奇數可以推的出來,偶數也可以拿來用。假設一個偶數 n 被拆成 n = 2*x,

實際上 n 和  x  的循環週期是一樣的 ,至於偶數的推法,留給有興趣之讀者。

edisonx 發表在 痞客邦 PIXNET 留言(1) 人氣()


留言列表 (1)

發表留言
  • Cypresslin
  • EdisonX前輩您好:
    此處的「... ,和判斷 10 進位之 11 頗為相似」
    我想應該是:「判斷 2 進位之 11」 的筆誤?
  • 確實為筆誤,謝謝您的指正 :)

    edisonx 於 2012/11/23 22:22 回覆

您尚未登入,將以訪客身份留言。亦可以上方服務帳號登入留言

請輸入暱稱 ( 最多顯示 6 個中文字元 )

請輸入標題 ( 最多顯示 9 個中文字元 )

請輸入內容 ( 最多 140 個中文字元 )

請輸入左方認證碼:

看不懂,換張圖

請輸入驗證碼