0

Задача в том, чтобы функция возвращала числа от 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 - значность

10
  • Можно пожалуйста, чуть более подробное описание задачи?
    – EzioMercer
    26 июн 2022 в 14:21
  • Вернуть массив, где [количество чисел, где каждая цифра не меньше предыдущей и их сумма равна n, а значность равна k; массив этих чисел] 26 июн 2022 в 14:24
  • В задаче надо было добавить три примера: 1)пример чисел на входе, 2) какой должен быть результат. В текущем виде непонятно зачем вообще возвращать [count, ...], когда он равен res.length и почему первая строка возвращает не массив а число. 26 июн 2022 в 14:33
  • 1
    Погодите минутку. Как число может быть 20-ти значным и причём каждая цифра меньше предыдущей? Цифр всего 10 штук у нас, не может быть 20-ти значного числа, так чтобы цифры были одна меньше предыдушего. Максимальное такое число - это 9876543210
    – EzioMercer
    26 июн 2022 в 14:37
  • И непонятно, что и как тут может работать. Когда первый цикл достигнет a==10, все вложенные циклы не сработают и a++ будет вертеться впустую. 26 июн 2022 в 15:07

3 ответа 3

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
1
  • Я переписал под JS, действительно эффективное решение) 27 июн 2022 в 15:27
0

Переписал решение 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)
    }
}
1
  • 1
    Учтите ещё, что для 20-значных чисел в JS понадобится использовать BigInt - видимо, curr * 10n + BigInt(d) и т.д.
    – MBo
    27 июн 2022 в 15:45
-2

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

2
  • Пожалуйста, старайтесь оставлять примеры кода при ответе на вопросы, насколько это возможно
    – EzioMercer
    26 июн 2022 в 14:45
  • может, например, 99999999999999999999, его сумма 180. К тому же брутфорс без оптимизации будет оооочень долгим 26 июн 2022 в 17:11

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.