Блог

Это не домашнее задание, а приложение реального мира, на котором я зацикливаюсь.

Лучший способ, которым я могу объяснить свою проблему, заключается в следующем:

Представьте, что у вас есть 3 свинарника A , B , и C и 10 свиней, которых нужно содержать. Ручки имеют ограничения в том, что в каждой ручке должно быть не менее 1 свиньи и A.pigs <= B.pigs <= C.pigs . Перечислите все возможные конфигурации пера.

РЕАЛЬНОЕ приложение может содержать от 1 до 7 ручек, а также от numPens и numPens*30 до свиней, и ни одна ручка не может содержать более 30 свиней. Таким образом, по сути, это означает, что «какие числа от 1 до 30 (допустимые повторы) составляют X, используя числа Y»

Это можно было бы решить просто с помощью вложенных циклов, но это ужасно неэффективное решение, особенно с учетом области реального применения:

 var cnt = 0
val target = 10

for (a in 1..30) {
    for (b in a..30) {
        val c = target - a - b
        cnt  
        if (a <= b amp;amp; b <= c amp;amp; a   b   c == target) {
            println("$a $b $c")
        }
    }
}

println(cnt)
 

вывод:

 1 1 8
1 2 7
1 3 6
1 4 5
2 2 6
2 3 5
2 4 4
3 3 4
465
 

Я уверен, что есть рекурсивное решение этой проблемы. Но у меня возникли проблемы даже с поиском отправной точки для этого.

Кажется, легко начать с массива [1, 1, 8] , где каждый индекс представляет перо. Просто поместите всех свиней в 1 загон и перемещайте их по 1 за раз, соблюдая ограничения.

Вычтите из C, добавьте к B столько, сколько сможете, сохраняя при этом ограничения, [1, 2, 7], [1, 3, 6], [1, 4, 5] но в этот момент я застрял в коде.

Что у меня есть в настоящее время:

 fun main(vararg args: String) {
    val list = arrayOf(1, 1, 8)
    list.forEach { print("$itt") }
    println()
    rec(list, list.lastIndex - 1)
}

fun rec(list: Array<Int>, index: Int) {
    if (index == list.lastIndex || index < 0) {
        return
    }

    while (list[index]   1 <= list[index   1] - 1) {
        list[index]  
        list[index   1]--
        list.forEach { print("$itt") }
        println()
    }
}
 

Очевидно, мне нужно вызвать rec где-то внутри себя и, вероятно, нужны некоторые условные обозначения для правильного вызова rec (возможно, добавив к нему дополнительные параметры). Вопрос в том, где и как? Обычно неплохо с рекурсией, но это ставит меня в тупик.

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

 for (a in 1..30) {
    // we know a and c must be at least b, so cap range
    var b = a
    while(b < min(target - a - b, 30)){
        val c = target - a - b
        cnt  
        if (a <= b amp;amp; b <= c amp;amp; a   b   c == target) {
            println("$a $b $c")
        }
        b  
    }
}
 

Следует отметить некоторые недостатки:

• Как только вы узнаете a и b , единственным значением для c этого может быть решение, будет 10 — a b , так что вам вообще не нужен самый внутренний цикл.
• Поскольку a <= b , второй цикл должен начинаться с a , а не с 1 .
• Вы также можете ограничить верхнюю часть диапазона второго цикла на основе значения a