在Javascript中查找奇怪的數字

一個奇怪的數字是一個數字，其自除數的總和大于該數字本身，并且沒有任何自除數的子集與該數字相加。

例子：

70 是一個奇怪的數字，因為它的真除數（1、2、5、7、10、14 和 35）之和為 74，即大于 70，并且這些數字的總和不等于 70。

18 并不是一個奇怪的數字，因為它的真除數 (1, 2, 3, 6, 9) 之和為 21，它大于 18，但 3、6 和 9 之和為 18。

我正在嘗試撰寫一個 JavaScript 函式，從 1 to 100

我在條件 #2 下苦苦掙扎，沒有適當除數的子集總和等于該數字。

更新：我可以獲得條件 #2 的這么多邏輯

 // assuming we put all the divisiors in an array.
36 => [1,2,3,4,6,9,12,18]

// we take first two numbers
[1,2] 
// are they less than 36?
yes

arr.forEach(n,idx){
  let k = arr[idx]   arr[idx 1]
  if(k<36){
    let sum = 0
    sum = k   arr[idx 2]
  }
}

我可以弄清楚它背后的邏輯，但我無法解決它。

function magicNum(){
  let arr = []
  for(let i =0;i<=100;i  ){
    arr.push(i)
  }
  arr.forEach(n=>{
  let sum = 0
  for(let i = 1 ; i<n ; i  ){
    if(n%i===0){
      sum =i
      }
    }
  if(sum > n){
      console.log(n) // I could get the first condition
    }
  })
}

magicNum()

uj5u.com熱心網友回復：

您可以通過對值使用位掩碼來檢查每個可能的組合。

const
    check = (value, array) => {
        let n = 1 << array.length;
        while (n--) {
            if (value === array.reduce((s, v, i) => s   v * !!(1 << i & n), 0)) {
                return true;
            }
        }
        return false;
    };

console.log(check(18, [1, 2, 3, 4, 6, 9]));
console.log(check(70, [1, 2, 5, 7, 10, 14, 35]));

uj5u.com熱心網友回復：

編輯：更新以檢查豐富性。

我會用三個可重用的函式來做到這一點。 divisors列出一個數的所有除數，powerset列出一個集合（也作為陣列給出）的所有子集（作為陣列），并sum添加一個數字串列。

然后我們可以通過取除數來組合它們，去除最后一個（原始數），然后取該集合的所有子集，并檢查這些子集中的任何一個是否與初始數相加。它看起來像這樣：

const divisors = (n, i = 1, inc = [], dec = []) =>
  i * i > n 
    ? [...inc, ...dec .reverse ()]
  : n % i == 0 
    ? divisors (n, i   1, [...inc, i], i * i == n ? dec : [...dec, n / i])
  : divisors (n, i   1, inc, dec)

const powerset = ([x, ...xs]) =>
  x == undefined
    ? [[]]
    : powerset (xs) .flatMap (ss => [ss, [x, ...ss]])
    
const sum = (ns) => 
  ns .reduce ((a, b) => a   b, 0)

const weirdNumber = (n) => { 
  const factors = divisors (n) 
  return sum (factors) > 2 * n &&
         ! powerset (factors .slice (0, -1)) .some (ss => sum (ss) == n)
}

console .log (weirdNumber (70))
console .log (weirdNumber (18))

sum是微不足道的，powerset是一個足夠簡單的遞回。 divisors有點棘手，因為我們同時累積增加的小除數和減少的大除數，最后將它們合并在一起。因此，在檢查時，divisors (72)我們將在遞回步驟中使用這些值：

然后，因為9 * 9大于72，我們完成并反轉dec并回傳其與 的串聯inc。

特殊處理i * i == n ? ...是處理數字為完全平方數的情況。在divisors (49)比如，我們不希望包含7在這兩個inc和dec。

main 函式很簡單，some用于測驗任何子集是否有匹配的和，并否定結果。

請注意divisors，powerset、 和sum都是可重用的函式。僅weirdNumber針對此問題。

另請注意，這是非常低效的。我們肯定可以找到一種更有效的方法來檢查關鍵模式，因為即使我們已經太大，它也會繼續求和。例如，如果我們想測驗 ，360我們需要找到其適當因子的所有子集并將它們中的每一個求和。我們當然可以在那里找到速度的改進。22323

uj5u.com熱心網友回復：

function magicNum(){
  function checkSubsets(idx, arr, curr, target) {
    if (curr === target) return true

    for (let i = idx; i < arr.length; i  ) {
      if (checkSubsets(i 1, arr, curr arr[i], target)) return true
    }
    return false
  }
  let arr = []
  for(let i =0;i<=100;i  ){
    arr.push(i)
  }
  arr.forEach(n=>{
  const divisors = []
  let sum = 0
  for(let i = 1 ; i<n ; i  ){
    if(n%i===0){
      divisors.push(i)
      sum  = i
      }
    }
  if(sum > n){
      console.log(n) // I could get the first condition
    }
  if (checkSubsets(0, divisors, 0, n)) {
    console.log("One of the subsets of "   n   "equals "   n)
  }
  })
}

magicNum()

我對 JavaScript 了解不多，如果這不是很干凈，很抱歉。大部分子集檢查演算法在checkSubsets.

  function checkSubsets(idx, arr, curr, target) {
    if (curr === target) return true

    for (let i = idx; i < arr.length; i  ) {
      if (checkSubsets(i 1, arr, curr arr[i], target)) return true
    }
    return false
  }

正如你所看到的，它采用當前專案的指標idx，所有適當的除數的陣列arr，當前子集的總和curr，而target這是n我們目前正在研究。

它通過將索引遞增 1 并將當前專案添加到當前總和來遞回呼叫自身。如果找到curr == target它回傳true。檢查所有組合后，如果沒有找到任何組合，則回傳false。

為了確保數字很奇怪，您需要進行如下測驗：

if (sum <= n && !checkSubsets(0, divisors, 0, n) {
  console.log(n   " is weired, because the sum of its proper divisors was smaller or equal to itself and no subset of its divisors was equal to it")... }

uj5u.com熱心網友回復：

該頁面指出：

“奇怪的數”是豐富的數（即真因數的總和大于該數）而不是偽完美的（即，沒有真因數的子集與數本身之和）。定義的偽完美部分意味著找到奇怪的數字是子集和問題的一個例子。

我下面的代碼沒有考慮偽完美子集。

我是如何解決這個問題的：

• 1 將始終添加：在代碼中，sum從 1 開始。
• 您只需要回圈可能奇怪的數字的下半部分，而是將除法器和結果都添加到總和中：在代碼中，只會回圈到half.
• 如果數字已經添加，您需要跟蹤，因為 5 * 14 小于 (70/2=) 35 并且將在可能奇怪數字的下部計算兩次 (5 14, 14 5) : 在代碼中，addedNumbers跟蹤它。

你可以用更短的方式寫這個，但我更喜歡有可讀的代碼。

function isWeird(number) {
  let half = parseInt(number / 2) - 1,
      sum = 1,
      evenNumber = -1,
      addedNumbers = new Set();
  
  for (let divider = sum 1; divider < half; divider  ) {
    evenNumber = parseInt(number/divider);
    
    if (!addedNumbers.has(divider) && number / divider == evenNumber) {
      sum  = divider   evenNumber;
      addedNumbers.add(divider);
      addedNumbers.add(evenNumber);
    }
  }
  
  let isWeird = sum > number;
  
  return {number, sum, isWeird}; 
}


let value = 70;

console.log(isWeird(value));

value = 10;

console.log(isWeird(value));

標籤：javascript 算法 搜索 数据结构

上一篇：Dijkstra演算法負邊緣

下一篇：演算法問題：尋找最便宜的航班