iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 25
1
Software Development

使用JavaScript學習資料結構與演算法系列 第 25

Day25-解題-Perfect Number 完美數

今天要來解的題目是完美數,完美數是什麼呢?如果一個正整數的除了自己本身的其他因數總和剛好等於該正整數,則該數字稱為完美數。

因此這次的題目內容就是輸入一個正整數,判斷它是否是完美數,是的話回傳 true,不是的話回傳 false。

範例:

輸入: 28
回傳: True
原因: 28 = 1 + 2 + 4 + 7 + 14

理解題目後我們就來實作吧!

  1. 宣告一個 perfectNum() 函式,接著思考1是每個數字的因數,因此一開始因數總和 sum 變數可以設定為1

  2. 接著完成 for 迴圈的部分,i 可用來被傳入的整數除,而 迴圈執行條件是 i * i <= num ,因為假如找到 i 是某值 num 的因數,那麼 num 除以 i 的結果也是 num 的因數,因此不需要遍歷所有比 num 小的值
    ex:
    42的因數: [1, 42], [2, 21], [3, 14], [6, 7],6 * 6 = 36,7 * 7 = 49,遍歷到6其實就找到所有因數了。
    49的因數: [1, 49], [7, 7],遍歷到7就找到所有因數了。

function perfectNum(num) {
  let sum = 1; // 因為1一定是某個數的因數,因此預設sum先加一
  for(let i = 2; i * i <= num; i++) {
    
  }

}
  1. 接著完成迴圈內部的內容,當 num/i 和 i 值相同時,例如就像 49 = 7 * 7 一樣,因此 sum因數總和 只加一個 i 值就好。若 num 可以被 i 整除,就加上該 i 數和 num 除以 i 後的數。

  2. 最後若因數總和 sum 和 判斷的數 num 相同且不等於1,就代表它是完美數,回傳 true。

function perfectNum(num) {
  let sum = 1; // 因為1一定是某個數的因數,因此預設sum先加一
  for(let i = 2; i * i <= num; i++) {
    if (num / i == i & num % i == 0) {
      sum += i;
    } else if(num % i == 0) {
      sum += i;
      sum += (num / i);
    }

    if(sum > num) {
      return false;
    }
  }
  if(sum == num && num != 1) {
    return true;
  } else {
    return false;
  }
}

這次的程式碼在以下連結:
https://github.com/a90100/javascript-data-structure/blob/master/day25-perfect-number.js

明天我們將來實作"阿姆斯壯數"的數學問題!


上一篇
Day24-動態規劃-0/1背包問題
下一篇
Day26-解題-Armstrong number 阿姆斯壯數
系列文
使用JavaScript學習資料結構與演算法30

尚未有邦友留言

立即登入留言