No creo que ninguna fórmula será capaz de capturar esas reglas, para no trivial de los valores de N y k.
Lo que sí es factible es escribir un algoritmo para determinar ese número; o mejor aún, la secuencia infinita de formas para cada natural n, dado un k fijos.
Dicho algoritmo será, básicamente, "inductivamente" calcular cada elemento de la serie basada en el elemento anterior. Tal elemento se representan internamente en una fracción de la forma en un par de útiles particiones, una para cada uno de los estados posibles de la actual problema de resolver la situación.
Permítanme explicar más.
Máquina de estados finitos
Un ejemplo de la secuencia de N soluciones de problemas puede ser imaginado como una secuencia de N+1 estados de progreso en la resolución de problemas. Las cosas que desea recordar, durante ese proceso, son sólo
$$
un \[0..k[ = \text{cómo muchos de los problemas a resolver hasta el momento (en el modulo k)}\\
b \in [0,1] = \text{1 si el último problema fue resuelto por B, de lo contrario 0}\\
c \in [0,1] = \text{1 iff C ya resuelto ningún problema, de lo contrario 0}
$$
Por sólo conociendo estos hechos (o variables) que son capaces de determinar cuáles son todos los posibles estados, y si uno de ellos es un final estado (es decir, si la secuencia actual de los solucionadores de problemas será una de las maneras en que se cuentan en $w(N)$).
Por ejemplo, si $a=0, b=0, c=0$ sé que se puede ir, dependiendo de la próxima persona que va a resolver el problema,
- $A -> a=1, b=0, c=1$ (no un estado final)
- $B -> a=0, b=1, c=1$ (un final estado)
- $C -> a=0, b=0, c=0$ (un final estado)
Seguimiento de todos los estados
Ahora, observe que todos los estados posibles son un número finito, y en realidad relativamente pocos. La cantidad exacta es $4k$, y en el peor de los caso en que k = 10 (gracias por el enlace k), usted sólo tiene 40 estados.
Si usted sabe, para cada una de las $4k$ estados, en cómo muchas maneras que usted podría haber llegado allí en exactamente n pasos, usted puede determinar de cuántas maneras se puede llegar a cada una de las $4k$ estados unidos luego de que el paso n+1.
Si usted comienza con 0 problemas, con 1 sólo en $w_0(0,0,0)$ (sólo se puede iniciar a partir de este estado en el que Una solucionado 0, B no se resuelve en la última, y C no resolver ninguno), y calcular la cantidad de formas en la $w_i$ por cada estado, para cada i hasta n, usted simplemente tiene que sumar junto a las formas $w_n(0,0,1) + w_n(0,1,1)$ conseguir tus caminos en el que n solución de problemas y todas sus reglas, fueron honrados.
El código
Lo programé esta en la Scala, espero que no te importa el idioma elegido.
Ten en cuenta que su número crece muy rápidamente, y si su valor sobrepasa el máximo de Java mucho valor ($2^{63}-1$), usted tendrá que reemplazar la larga variables con un BigInteger o algo similar.
import collection.Map // generic Map interface
object ProblemSolverz {
def main(args: Array[String]): Unit = {
// C
println(new ProblemSolverz(3).ways(1))
// CC, BC, CB
println(new ProblemSolverz(3).ways(2))
// CCC, BCC, CBC, CCB, BCB
println(new ProblemSolverz(3).ways(3))
// CCCC
// BCCC, CBCC, CCBC, CCCB
// BCBC, BCCB, CBCB
// AAAC, AACA, ACAA, CAAA
println(new ProblemSolverz(3).ways(4))
// a LOT of ways
println(new ProblemSolverz(3).ways(20))
}
}
class ProblemSolverz(k: Int) {
def ways(N: Int) =
// number of states in which
// A solved a number of problems equal to 0 in modulo k,
// C solved at least one problem,
// B whatever
states(N - 1)((0, 0, 1)) + states(N - 1)((0, 1, 1))
val states = makeNextStates(Map((0, 0, 0) -> 1L)) // initial state
def makeNextStates(previousStates: Map[(Int, Int, Int), Long]): Stream[Map[(Int, Int, Int), Long]] = {
// initialize all states to 0 (makes for cleaner code later)
val states = scala.collection.mutable.Map((for {
a <- 0 until k
b <- 0 to 1
c <- 0 to 1
} yield ((a, b, c), 0L)): _*)
// for each previous state, compute its successors
previousStates.foreach({
case ((a, b, c), ways) => {
// A could solve this problem
states(((a + 1) % k, 0, c)) += ways
// B could solve this problem, if he is rested
if (b == 0)
states((a, 1, c)) += ways
// C could solve this problem
states((a, 0, 1)) += ways
}
})
// contribute this state to the stream
Stream.cons(states, makeNextStates(states))
}
}
