Почему эта рекурсивная функция пропускает числа?

Я пытаюсь найти различные возможности равные 100 с цифрами 1-9. Эта функция дает желаемые результаты, но также и другие, которые я не предполагал. Другие результаты составляют до 100, но без некоторых из этих цифр, например, оставляют 3 или 6. Почему эти другие результаты включены?Почему эта рекурсивная функция пропускает числа?

var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]; 
    var signs = ["+", "-", "N"]; 
    var results = []; 
    find100("1"); 
    function find100(expr) { 
     if (eval(expr.replace(/N/g, "")) === 100) { 
      results.push(expr); 
     } else { 
      for (var i = eval(expr.substring(expr.length - 1, expr.length)) + 1; i <=  
      nums.length; i++) { 
      signs.forEach(function(sign) { 
       var expr2 = expr; 
       find100(expr2 += sign + i); 
      }); 
      } 
     } 
    }

Желаемый результат:

1+2+3-4+5+6+78+9, 
1+2+34-5+67-8+9, 
1+23-4+5+6+78-9, 
1+23-4+56+7+8+9, 
12+3+4+5-6-7+89, 
12+3-4+5+67+8+9, 
12-3-4+5-6+7+89, 
123+4-5+67-89, 
123+45-67+8-9, 
123-4-5-6-7+8-9, 
123-45-67+89

источник

2016-09-13 Gragh

eval()? почему вы используете eval? это почти всегда признак ужасного плохого дизайна. –

Можете ли вы включить то, что ваш выход и какие значения вы были или не ожидали? – leigero

Потому что я строю строку с +, - или ничего (N), которая будет позже оценена. – Gragh

Это добавление к нежелательным результатам, потому что ваши первые итерации цикла через каждый из оставшихся чисел и добавляет ЛЮБЫЕ результаты, которые оценивают в 100, даже если он пропустил ряд, чтобы сделать так. Если метод находит решение для числа, он добавляет решение к results - это правильно, однако, если он не находит решение, он все равно перемещается на следующий номер. Это источник пропущенных чисел. Если не было решения для числа, оно не должно продолжаться до следующего номера.

О том, как это исправить, это другой вопрос (но почему бы и нет ...)

Разница здесь в том, что вы можете только получить результат, если для любого числа существует такое выражение, которое использует все остальные номера.

var results = []; 
 
var operations = [ "+", "-", "" ]; 
 
var expected = 100; 
 
var limit = 10; 
 

 
function findExpression(expr, next) { 
 
    if (next === limit) { 
 
     eval(expr) === expected && results.push(expr); 
 
    } else { 
 
     operations.forEach(function(operation) { 
 
      findExpression(expr + operation + next, next + 1); 
 
     }); 
 
    } 
 
} 
 

 
$(document).ready(function() { 
 
    findExpression("1", 2); 
 
    for(var i=0; i<results.length; i++) { 
 
     $("#foo").append(results[i]+"<br />"); 
 
    } 
 
});

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.12.0/jquery.min.js"></script> 
 
<body> 
 
<div id="foo"></div> 
 
</body>

источник

2016-09-13 20:30:12 Tibrogargan

Но почему он пропускает номер для этого? – Gragh

Из-за вашей петли. Ваш код начинается с 1 итерации через каждое оставшееся число. Если он найдет решение для 2, он добавит его - это нормально, но если он не найдет решение для 2, он все равно перемещается на 3. Там, где твоя проблема исходит. Если не было решения для 2, он должен был остановиться. – Tibrogargan

Почему он не останавливается? Или почему он должен был остановиться? Для потомков, по крайней мере ... – Gragh

Причина, по которой некоторые цифры пропускаются в этом цикле:

for (var i = eval(expr.substring(expr.length - 1, expr.length)) + 1; i <=  
     nums.length; i++) {

На второй итерации будет увеличиваться, что последняя цифра в выражении, следовательно, которая будет создавать разрыв в продолжении рекурсии. Короче говоря, этого цикла не должно быть.

Я предлагаю решение без использования eval, но не потому, что это было бы как-то опасно, а потому, что оно отвечает за большой удар производительности.

Вместо этого вы можете сохранить числовую переменную, обновленную до того, что представляет выражение. На самом деле, я предлагаю использовать две такие переменные: одну для суммы предыдущих терминов, а другую для последнего термина, потому что это, возможно, нужно будет расширить с большим количеством цифр.

Чтобы облегчить различный способ воздействия знаков на выражение, я определил функцию для каждого знака: она принимает указанные числовые значения, а также последнюю цифру и возвращает обновленные значения.

Вот рабочий фрагмент (ES6 синтаксис), используя эту идею, и вы заметите значительное улучшение производительности:

function find100(digits, signs) { 
 
    const loop = (expr, i, [sum, value]) => 
 
     // Not yet all digits used? 
 
     i < digits.length ? 
 
      // Apply each of the signs in turn: 
 
      Object.keys(signs).reduce((results, sign) => 
 
       // Recurse, passing on the modified expression, the sum of the 
 
       // preceding terms, and the value of the last term. As '+' is 
 
       // not any different than '' before the first digit, skip '+': 
 
       sign != '+' || i ? 
 
        results.concat(loop(expr+sign+digits[i], i+1, 
 
             signs[sign](sum, value, digits[i]))) : 
 
        results, 
 
       []) : 
 
     // All digits were used. Did it match? 
 
     sum+value == 100 ? [expr] : []; 
 
    // Start recursion 
 
    return loop('', 0, [0, 0]); 
 
} 
 

 
var nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]; 
 
// define how each sign should modify the expression value: 
 
var signs = { 
 
    '+': (sum, value, digit) => [sum+value, digit], 
 
    '-': (sum, value, digit) => [sum+value, -digit], 
 
    '' : (sum, value, digit) => [sum, value*10 + (value<0 ? -digit : digit)] 
 
}; 
 
var results = find100(nums, signs); 
 

 
console.log(results);

Обратите внимание, что это также выводит следующее выражение:

-1+2-3+4+5+6+78+9

Это потому, что код также проверяет знаки перед первой цифрой. Я подумал, что было бы важно, чтобы это также включалось в результаты.

источник

2016-09-14 10:54:29 trincot

Почему эта рекурсивная функция пропускает числа?

ответ

Смежные вопросы