Categories
JavaScript Телерик

Комбинации на числа по търсена сума

Това е решението на първата задача от изпита по JavaScript основи, проведен на 19 май 2014 година в Телерик Академия.

В задачата се иска да се намерят всички възможни варианти на автомобили, камиони и триколки, на които сумата на гумите да е равен на определено число.

Решението на задачата е само с цикли, без рекурсия. Използват се комбинации.

function findPermutations(n) {
    var tires = [3, 4, 10];
    var buffer = new Array(n + 1);
    for (var i = 0; i <= n; ++i)
        buffer[i] = new Array(tires.length + 1);
    for (var j = 1; j <= tires.length; ++j)
        buffer[0][j] = 1;
    for (i = 1; i <= n; ++i) {
        buffer[i][0] = 0;
        for (j = 1; j <= tires.length; ++j) {
            var value = buffer[i][j − 1];
            if (tires[j − 1] <= i)
                value += buffer[i − tires[j − 1]][j];
            buffer[i][j] = value;
        }
    }
    return buffer[n][tires.length];
}