最常出現的面試考題(1) – 找出2數之最大公因數(FIND GCD OF PHP)

Home / PHP / 最常出現的面試考題(1) – 找出2數之最大公因數(FIND GCD OF PHP)

最常在面試中碰到的考題就是給2個數,從這2個數字中找出最大公因數,請將此方式撰寫為程式。
這是很常出現的題目之一,代表也是很經典的考題,縱使很簡單,但也常讓人家突然間不知如何下筆。首先必須要先知道是什麼是最大公因數,最大公因數(Greatest Common Divisor,簡寫為G.C.D.;或Highest Common Factor,簡寫為H.C.F.),指某幾個整數共有因數中最大的一個。
求兩個整數最大公因數主要的方法:

  1. 列舉法:各自列出因數,再找出最大的公因數。
  2. 質因數分解法:兩數各作質因數分解,然後取出共有的項乘起來。
  3. 短除法
  4. 輾轉相除法(擴展版):常使用於直觀上不容易判別公因數的場合。

其實用PHP的寫法找出最大公因數是非常的簡單,只需要1行的程式:

但這個程式需要用到2個觀念,1是MOD (取餘數)、2是recursive (遞迴)

1、MOD

取餘數,不管哪一種程式語言中都會有的運算子,最簡單的就例如判斷 $counter是否是偶數,我們就可以用 $counter除上2,若餘數為0則代表是偶數,為1則代表是奇數:

2、Recursive

所謂的遞迴函式, 簡單地說就是一個呼叫自己的函式。那什麼樣的問題適合用遞迴函式來解決呢?
一個問題如果可以拆解成規模較小但是性質和原問題完全一樣的問題的時候, 就可以考慮用遞迴函式來處理。 例如:

  1. 連加
  2. 連乘(階乘)
  3. 輾轉相除
  4. 搜尋
  5. 排序
  6. 老鼠走迷宮

如果你熟悉數學歸納法的話, 就會發現這簡直就是利用標準的數學歸納法來得到的,不過一般來說, 遞迴演算法是一種用程式來實現 Divide and Conquer 策略的重要方法。

所謂的 Divide and Conquer 是我們常常用來解決問題的一種策略, 就是將一個大的問題先拆解為規模較小的幾個問題來分別對付, 如果新的問題和原來的問題性質完全相同的話, 就可以用遞迴函式來製作了, 例如: 由一疊考卷中尋找某一位同學的考卷時, 我們可以把一疊考卷均分為兩部份, 先在第一部份中尋找, 再去第二部份中尋找, 這裡每一個尋找的動作都完全相同, 只是資料的多寡不同而已, 也就是上面所說的 “性質完全相同的問題”。

了解以上2點後,我們拿個實例來看看,從8與36中找最大公因數:

step1:

$a = 8, $b = 36,先由8 mod 36,得到餘數36,餘數不為0,故此時運用遞迴再呼叫自己,但變數改變為 gcd(36,8)

step2:

此時$a = 36, $b = 8,此時 36 mod 8得到餘數4,餘數不為0,故此時運用遞迴再呼叫自己,但變數改變為 gcd(8,4)

step3:

此時$a = 8, $b = 4,此時 8 mod 4得到餘數0,故最大公因數為此時的$b,即為4

進階運用

以下則是示範如何從一群(array)數字中,找出這群數字的最大公因數

 

7675 全部 2 今日

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *

*