Получить все подмножества данного делителя числа и проверить, не нарушают ли они условия

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

PHP подход:

<code>$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 "

";

Вывод:

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

Answer 2

Я сделал это до сих пор, который охватывает первые два шага, которые я намеревался сделать.Последний шаг мне не известен, но у меня есть решение и для этого.

Это мой код:

<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);
}