Как сделать рекурсию, которая работает как вложенные циклы?

Question

Задача в том, чтобы функция возвращала числа от 3-х до 20-ти значности. При чём число нужно обрабатывать по каждой цифре, а потом "склеивать" в одно число (цифра должна быть не менее предыдущей).

Получилось создать работающий код, но проблема в том, что нужно сделать много вложенных циклов (решение O(n^n) приблизительно, хотя для n^3 выдаёт 109 итераций), а моё решение не обрабатывает "вложенность" и работает только при ручном изменении количества циклов. Объясните, пожалуйста, как создать такой код

function find(n, k) {
  if (n < k) return 0
  const res = []
  let count = 0
  for (let a = 1; a <= n / k; a++) {
    for (let b = a; b < 10; b++) {
      for (let c = b; c < 10; c++) {
        if (a <= b && b <= c && a + b + c === n) {
          res.push(a * 100 + b * 10 + c)
          count++
        }
      }
    }
  }
  return [count, res]
}

n - сумма цифр числа, k - значность

Answer 1

число состоящее из 20 знаков вы будете решать очень долго. И по логике вашего ответа выше ваше число не может быть больше 10 знаков, так как иначе не выполняется условие что каждая последующая цифра числа больше предыдущей. Если вы хотите решать данную задачу в лоб, то просто заведите один цикл фор внутри которого сделайте цикл while который будет определять количество цифр в вашем числе. Для этого делите ваше число которое вы проверяете на 10 и запоминайте остаток от деления, который и будет вашим числом, после чего проверяйте полученные числа на выполнение условия вашей задачи. Таким образом Вам не нужна будет рекурсия и вы все сделаете с использованием всего двух циклов. Но вообще данная задача должна решаться иметь решение без прямого перебора.

Answer 2

Рекурсивное решение действительно очень простое. Вот как оно может выглядеть на Python. Вместо создания списка чисел здесь я их просто вывожу.

На каждом уровне рекурсии наша задача - создать число с суммой цифр summ и количеством цифр num, начинающееся с цифры не менее dmin.

Если принцип понятен, то на JS перевести, наверное, нетрудно (у меня с лёту не заработало, как в JS вообще отлаживать?)

def buildSum(summ, num, dmin, curr):
    if num == 0:
        if summ == 0:
            print(curr)
    else:
        for d in range(dmin, min(summ, 9) + 1):
            buildSum(summ - d, num - 1, d, curr*10 + d)

buildSum(10, 3, 1, 0)

118
127
136
145
226
235
244
334

Answer 3

Переписал решение MBo на JS, вдруг, кому понадобиться

function buildSum(summ, num, dmin, curr) {
    if (!num && !summ) console.log(curr)
    for (let d = dmin; d < Math.min(summ, 9) + 1; d++) {
      buildSum(summ - d, num - 1, d, curr * 10 + d)
    }
}

БЛОГ НА HUSL

Как сделать рекурсию, которая работает как вложенные циклы?

Ответы (3 шт):