获取给定数字的除数的所有子集，并检查它们是否违反了条件

Question

所以我有个问题，我不太明白。

我想了解问题的解决方法

想象一下以下场景：

你是一家公司的人力资源经理，有1000名员工，1到1000名员工。你的老板让你给员工一大笔圣诞奖金，但没有告诉你他们的名字。相反，他们给了你两个指示：

( 1)雇员号的适当除数之和(包括1，但不包括本身)大于雇员编号本身

2)这些除数的任何子集都不等于雇员号本身。

有多少员工有资格领取奖金?他们的人数是多少？

例如：- 12:适当的除数是1，2，3，4和6。和是1+2+3+4+6 = 16，它大于12并且匹配第一个条件。但是，违反第二个条件的子集2+4+6=12。

我的结论是：，我必须得到从1到1000的数字，其中数字的除数之和大于数字本身(，包括1，但它本身不包括)，但是没有一个除数子集可以与数字本身相等？

我的步骤是：

• 将从1到1000之间的数字的除数放入数组中。
• 当除数器的和(包括1而不是它本身)大于数字本身时，获取这些数字，并将数组的大小调整为仅这些数字。
• 我必须检查剩余数字的除数器的每个子集，并在除数子集与数字本身相等时删除这些除数。

如果这是一个好方法，你能帮我吗?或者你们中有谁知道一个更有效/更好的方法？

任何帮助都将不胜感激！

注:我不想让你解决它，我想要理解它！

Answer 1

到目前为止，我已经做到了这一点，这包括了我打算做的头两个步骤。最后一步是我所不知道的，但我也有解决办法。

这是我的密码：

<script type="text/javascript">
  function getDivisors(n){
    var divisors=new Array();

    for(var x=1;x<n;x++){
      if(n%x==0) divisors.push(x);
    }
    return divisors;
  }


  function getNumbers(n){
    var numbers=new Array(),
    sum=0;

    for(var x=1;x<=n;x++){
      sum=getDivisors(x).reduce((a, b) => a + b, 0);
      if(sum>x) numbers.push(x);
      // console.log("Number: "+x+" sum:"+sum);
    }
    return numbers;
  }

  var remainingNumbers = getNumbers(1000);
  console.log(remainingNumbers);

</script>

这是问题的答案：

​

var out = document.getElementById('outLine');
out.innerHTML += "X\t»\tSUM\tSUM-X\tLIST\r\n";
function isSubsetSum(set, n, sum)  { 
	if (sum == 0) { return true; }
	if (n == 0 && sum != 0) { return false; }
	if (set[n - 1] > sum) { return isSubsetSum(set, n - 1, sum); }
	return isSubsetSum(set, n - 1, sum) ||
		isSubsetSum(set, n - 1, sum - set[n - 1]); 
} 
function v1chNum(x) {
	var r = [1];
	var n = 0;
	var m = x/2;
	for(var i = 2; i <= m; i++ ) {
		if(x%i==0) {
			if(r.indexOf(i)==-1) {
				r.push(i);
				n += i;
			}
			m = x/i;
			if(r.indexOf(m)==-1) {
				r.push(m);
				n += m;
			}
		}
	}
	if( n > x ) {
		r.sort(function(a, b) {return b - a;});
		if(!isSubsetSum(r,r.length,x)) {
			out.innerHTML += x+"\t»\t"+n+"\t"+(n-x)+"\t"+r+"\r\n";
		} else { return false; }
	} else { return false; }
}
for(var x = 1; x<1000; x++) {
	v1chNum(x);
}

<pre id="outLine"></pre>

​

Answer 2

PHP方法：

$empList = [];

        for ($emp = 1; $emp <= 100; $emp++) {

            $multiples = [];
            $subset = [];
            $cond1 = false;
            $cond2 = false;

            // Get multiples.
            for ($i = 1; $i < $emp; $i++) {
                if ($emp % $i == 0) $multiples[]= $i;
            }

            // Condition 1
            if (array_sum($multiples) > $emp) $cond1 = true;


            foreach ($multiples as $num) {
                if ($num % 2 == 0) $subset[]= $num;
            }

            // Condition 2
            if (array_sum($subset) > $emp) $cond2 = true;

            if ($cond1 && $cond2) $empList[] = $emp;
        }

        echo "<pre>";
        var_dump($empList);
        echo "</pre>";

输出：

Array
(
    [0] => 24
    [1] => 36
    [2] => 40
    [3] => 48
    [4] => 60
    [5] => 72
    [6] => 80
    [7] => 84
    [8] => 96
)

Answer 3

我在python中的代码：

def getDivisors(n):
    div = []
    for i in range(1, n-1):
        if(n%i == 0):
            div.append(i)
    return div

def sumDivisors(arr):
    div_sum = 0
    for i in arr:
        div_sum += i
    return div_sum

def subLists(arr):
    lists = [[]]
    for i in range(len(arr)):
        orig = lists[:]
        new = arr[i]
        for j in range(len(lists)):
            lists[j] = lists[j] + [new]
        lists = orig + lists
    return lists

def sumSublists(lists, n):
    for i in range(len(lists)):
        sum_list = sum(lists[i])
        if (sum_list == n):
            return False
    return True

for num in range(100):
    arr = getDivisors(int(num))
    lists = subLists(arr)
    if ((sumDivisors(arr) > int(num))and(sumSublists(lists, int(num)))):
        print(str(num) + '/n')