Рекурсия проверяет, дает ли серия операций заданное число
В книге Eloquent JS в разделе рекурсии дана программа:
Consider this puzzle: by starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. How would you write a function that, given a number, tries to find a sequence of such additions and multiplications that produce that number? For example, the number 13 could be reached by first multiplying by 3 and then adding 5 twice, whereas the number 15 cannot be reached at all.
У меня есть следующая программа, которая, похоже, проверяет ее, но я не знаю, как заставить ее печатать последовательность.
function tester (value, key) {
if (value == key) {
return 1;
}
else if (value > key) {
return 0;
}
else {
if ( tester(value+5, key) || tester(value*3, key) ) {
return 1;
}
return 0;
}
}
@ScottSauyet Всегда вводится значение = 1. Ключ - это номер, который нужно проверить. В Js нет параметров по умолчанию
В JS есть параметры по умолчанию, и они были в течение некоторого времени. Если это то, что вы хотите, вы можете написать function tester(key, value=1) { /* ... */ }.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 2
Вы можете сохранить последовательность, и, если она будет найдена, вычисление вернет последовательность.
function tester(key, value = 1, sequence = value) {
if (value > key) {
return false;
}
if (value === key) {
return sequence;
}
return tester(key, value + 5, '(' + sequence + ' + 5)')
|| tester(key, value * 3, sequence + ' * 3');
}
console.info(tester(15));
console.info(tester(11));
console.info(tester(24));
console.info(tester(37));Мне нравится ваш выходной формат ... почти. Почему вы решили заключить в скобки только добавление? Это кажется немного странным, хотя и законным. Очевидно, вы не можете делать только умножение по причинам распределения. Но оба кажутся яснее. И я пытаюсь решить, нравится ли мне это больше, чем моя запись шагов в виде массива.
@ScottSauyet, просто чтобы сохранить приоритет оператора.
Верно. Это то, что я хотел описать, когда сказал «по причинам распространения». Но, например, я считаю, что вывод tester(37) труднее читать, чем (((((1 * 3) * 3) * 3) + 5) + 5), но, возможно, это только я.
Ваша версия для меня немного странная, она возвращает 1 или 0, а не true или false. Вы в основном привыкли к языку, который объединяет логические значения с такими целыми числами? Но, похоже, должно работать.
Я бы написал немного иначе. Обычно я предпочитаю, чтобы моя рекурсия велась до меньшего количества входных данных. Вы можете написать простую функцию для проверки таких значений:
const m3a5 = (n) => n < 1
? false
: n == 1
? true
: m3a5(n - 5) || (n % 3 === 0 && m3a5(n / 3))
console.info(m3a5(13)) //=> true
console.info(m3a5(15)) //=> false
console.info(m3a5(18)) //=> trueЭто должно быть полностью эквивалентно вашему, по модулю различий boolean / int.
С его помощью вы можете довольно просто расширить его, чтобы вы могли фиксировать шаги:
const m3a5 = (n, steps = []) => n < 1
? false
: n == 1
? steps
: m3a5(n - 5, ['+5'].concat(steps))
|| (n % 3 === 0 && m3a5(n / 3, ['*3'].concat(steps)))
console.info(m3a5(13)) //=> ['*3', '+5', '+5']
console.info(m3a5(15)) //=> false
console.info(m3a5(18)) //=> ['*3', '+5, '+5', '+5']Обратите внимание, что это покажет один возможный путь, а не все из них. Например, ['+5', '*3'] - еще один возможный результат для m3a5(18), который вы получите, переключив основную ветвь на
: (n % 3 === 0 && m3a5(n / 3, ['*3'].concat(steps)))
|| m3a5(n - 5, ['+5'].concat(steps))
Но если вы хотите, чтобы пути все, это был бы существенно другой код.
Вау, отличный ответ! Мне очень нравятся тернарные операторы, и ваша реализация выглядит действительно круто: 3
Условные (тернарные) операторы для меня в основном способ использовать выражения, а не операторы, насколько это возможно в моем коде. Я почти полностью перестал использовать for, и все ближе к if.
Что вы вкладываете в эту функцию? Кажется, должен быть только один ...