Мячик прыгает по лестнице, расчитать кол-во вариантов
Здраствуйте, не могу решить задачу:
Даны два числа n - кол-во ступенек и m - максимальная длина прыжка мячика. Мячик начинает вверху лестницы и прыгает вниз на не более чем m ступенек. Нужно расчитать кол-во возможных вариантов перемещения этого мячика по лестнице. Помогите, пожалуйста :) |
Перебор вариантов равных определённому числу и максимумом
Cubbat,
для медитации не самый рациональный вариант ... пример для 5 ступенек и максимума 3 <script> function fn(f, g) { for (var h = [], k = 0;; k++) { var d = k.toString(g), c = f - d.length; if (0 > c) break; for (var b = "", a = 0, e = 0; e < d.length; e++) c = parseInt(d[e], g) + 1, b += c, a += c; a = f - a; 0 <= a && (b = Array(++a).join("1") + b, h.push(b)) } return h.sort(function(a, b) { return a - b }) }; document.write(fn(5,3).join('<br>')+ "<br>Всего: "+ fn(5,3).length); </script> |
а причем тут собственно JavaScript? Задача из раздела комбинаторики и решаться должна тамошними формулами с использованием прикладных вычислительных пакетов (Maple, MatLab). https://en.wikipedia.org/wiki/Partit...ate_functio n
|
готовые алгоритмы https://www.quora.com/Algorithm-to-s...riginal-number или http://math.stackexchange.com/questi...ative-integers. Надо немного модифицировать, с учетом ограничения m
|
Цитата:
<script> function fn(b, d) { for (var a = Array(b + 1).join("1").split(""), c = []; a[0] != b;) a.reduce(function(a, b) { return a + +b }, 0) < b ? a.push(1) : (a.every(function(a) { return +a <= d }) && c.push(a.slice()), a.pop(), a[a.length - 1]++); return c.sort(function(a, b) { return +a.join('') - +b.join('') }) }; document.write(fn(5,3).join('<br>')+ "<br>Всего: "+ fn(5,3).length); </script> |
Часовой пояс GMT +3, время: 18:11. |