@gelix1267

Количество комбинаций чисел JavaScript?

Как найти количество комбинаций чисел из строки от 4 до 12 символов. Условие: количество разделяющих точек - 3, символов между точками от 1 до 3, цифры местами не меняются. Например, Строка '1234'. Возможные комбинации: '1.2.3.4' Количество комбинаций = '1. Строка '12345'. Возможные комбинации: '1.2.3.45', '1.2.34.5', '1.23.4.5', '12.3.4.5' Количество комбинаций = '4'
  • Вопрос задан
  • 785 просмотров
Пригласить эксперта
Ответы на вопрос 3
alekseyHunter
@alekseyHunter
Android developer
1) Юзай формулу из теории вероятности, чтобы найти количество комбинаций.
2) Можешь рекурсией сделать. Выход из неё - количество вызовов равно количеству комбинаций. В хвост добавляй получившуюся строку.
Ответ написан
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
В тупую можно подсчитать 2-мя вложенными циклами.

ans = 0;
for (i = 1; i <= 3; ++i) {
  for (j = 1; j <= 3; ++j) {
    mn = max(n - i - j - 3, 1);
    mx = n - i - j - 1;
    if (mn <= mx)
      ans += mx - mn + 1;
  }
}


Работает так - перебираем сколько символов в первом и втором блоке. После этого считаем, сколько минимально и максимально может быть символов в третьем блоке (оставляя на последний от 1 до 3 символов). Прибавляем к ответу количество возможных вариантов для длины третьего блока.

Но это если у вас параметры фиксированные (4 блока 1-3 символа). Если параметры могут меняться, то решение - динамическое программирование f(i,k) - сколько способов разбить первые i символов на k блоков.

База: f(0,0) = 1, f(0, k>0) = 0, f (i>0, 0) = 0;
Пересчет: f(i,k) = sum_{l=min_length...min(max_length, i)}(f(i-l,k-1)).
Ответ: f(n, num_blocks).
Ответ написан
Комментировать
Griboks
@Griboks
Можно почитать учебник математики и составить на бумажке формулу, затем реализовать её не js.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы