Relación de recurrencia en un problema de asistencia estudiantil

Question

Relación de recurrencia en un problema de asistencia estudiantil

Matemáticas
combinatoria
relaciones de recurrencia

andres cheon

Tengo problemas para entender la solución a un problema de concurso de codificación.

Problema de asistencia del estudiante

Supongamos que la asistencia de un estudiante se registra como una cadena, por ejemplo

PPAPPPPLPPPLPPLLAPPPP

donde las letras representan Presente, Tarde y Ausente. Se otorga una recompensa al estudiante que cumple con los siguientes criterios,

No más de una ausencia.
Sin tres retrasos consecutivos, por ejemplo LLL .

Dado un registro de asistencia de longitud $n$ , entonces, ¿cuántos récords premiables existen?

por ejemplo, para $n=2$ , solo AAdeja de ser recompensado, de $3^2$ posibles cadenas, por lo que la respuesta es $8$ .

Solución oficial

La solución oficial intenta construir una relación de recurrencia, comenzando con este diagrama:

Explica: Deja $f[n]$ representan el número de casos recompensables para una cadena de longitud $n$ . Vamos a dividir en dos casos,

Cadenas que terminan en L.
Cadenas que terminan en P. (No sé por qué dice Nen el diagrama; error tipográfico, creo).

Es fácil ver que el segundo caso es recompensable siempre que la pieza que precede a la P, $f[n-1]$ , es gratificante.

Sin embargo, el Lcaso se debe dividir en cuatro partes, como se muestra. Allí, el autor afirma que la única pieza problemática es la última, que termina la cadena en LLL. Sus palabras exactas son,

De las cuatro combinaciones posibles al final, la cuarta combinación, que termina con un $LL$ al final conduce a una cadena sin recompensa. Pero, dado que hemos considerado solo cadenas recompensables de longitud $n-3$ , para que la última cadena sea recompensable en longitud $n-3$ e inasignable al fin $n-1$ , debe ir precedida de $PP$ antes de $LL$ .

Por lo tanto, teniendo en cuenta la primera cadena [rama izquierda] nuevamente, todas las cadenas recompensables de longitud $n-1$ , excepto las cadenas de longitud $n−4$ seguido por $PLL$ , puede contribuir a una cadena gratificante de longitud $n$ . Por lo tanto, esta cadena representa un factor de $f[n-1] - f[n-4]$ a $f[n]$ .

Así, la relación recurrente se convierte en:

$F [norte] = 2 F [norte - 1] - F [norte - 4]$ $f[n] = 2f[n-1] - f[n-4]$

Esperaba que alguien pudiera poner esta explicación en sus propias palabras, porque no entiendo las de este autor. Y ya ha cometido varios errores tipográficos en su explicación, así que no estoy seguro de confiar en esta explicación.

Otra cosa que no entiendo es por qué el primero de los cuatro casos no es también problemático, ya que si el $n-5$ y $n-4$ los caracteres eran L, entonces también tendríamos una cadena no recompensable.

Cualquier sugerencia para desenredar la explicación del autor sería apreciada. Gracias.

PS El autor está ignorando intencionalmente Aen esta etapa, para ser considerado por separado.

Tintorero Franklin Pezzuti

Creo que podrías querer decir

8

$8$ para

n = 2

$n=2$ puesto que hay

3^{n}

$3^n$ registros posibles de

n

$n$ días, y así

9

$9$ registros para

n = 1

$n=1$ , y con

1

$1$ récord inaceptable, habría

8

$8$ aceptables.

andres cheon

Sí, eso es correcto, ¡gracias!

esquistos del norte

A la fría luz del día todavía soy incapaz de entender el método de este autor. Puede ser que tenga sentido, pero debido a la falta de claridad, parece posible que se haya empleado alguna "falsedad" para que coincida con la respuesta deseada. Sé que soy parcial, pero he hecho algunos de estos tipos de recurrencias y siento que mi método es, con mucho, el más fácil de entender, así que me quedaría con eso por ahora si fuera tú. Con algunos ejemplos más diferentes, es posible que pueda entender a nuestro autor aquí, pero me parece un poco complicado.

andres cheon

Muchas gracias, me pondré en contacto con el autor desde aquí para intentar averiguar qué pretendía transmitir.

Antkam

FYI esto es equivalente al problema 191 en el proyecto Euler. (Allí se intercambian los roles de L y A) . projecteuler.net/problem=191 Si se molesta en escribir el código para resolver ese problema numéricamente, entonces puede acceder a su foro para ver muchas más recurrencias DIFERENTES que la gente usó para resolver esto. sin embargo, en mi humilde opinión, la respuesta aceptada tiene una de las explicaciones más limpias.

Respuestas (1)

Relación de recurrencia en un problema de asistencia estudiantil

Creo que podrías querer decir $8$ para $n=2$ puesto que hay $3^n$ registros posibles de $n$ días, y así $9$ registros para $n=1$ , y con $1$ récord inaceptable, habría $8$ aceptables.
A la fría luz del día todavía soy incapaz de entender el método de este autor. Puede ser que tenga sentido, pero debido a la falta de claridad, parece posible que se haya empleado alguna "falsedad" para que coincida con la respuesta deseada. Sé que soy parcial, pero he hecho algunos de estos tipos de recurrencias y siento que mi método es, con mucho, el más fácil de entender, así que me quedaría con eso por ahora si fuera tú. Con algunos ejemplos más diferentes, es posible que pueda entender a nuestro autor aquí, pero me parece un poco complicado.
Muchas gracias, me pondré en contacto con el autor desde aquí para intentar averiguar qué pretendía transmitir.
FYI esto es equivalente al problema 191 en el proyecto Euler. (Allí se intercambian los roles de L y A) . projecteuler.net/problem=191 Si se molesta en escribir el código para resolver ese problema numéricamente, entonces puede acceder a su foro para ver muchas más recurrencias DIFERENTES que la gente usó para resolver esto. sin embargo, en mi humilde opinión, la respuesta aceptada tiene una de las explicaciones más limpias.

esquistos del norte · Answer 1

Realmente es mucho más fácil de lo que el autor hace.

Tienes $3$ posibles terminaciones mutuamente excluyentes y exhaustivas para secuencias válidas de longitud $n$

(longitud de secuencia válida norte - 1) PAG

$(\text{valid sequence length $n-1$})\, \text{P}$

(longitud de secuencia válida norte - 2) ES

$(\text{valid sequence length $n-2$})\, \text{PL}$

(longitud de secuencia válida norte - 3) PLL

$(\text{valid sequence length $n-3$})\, \text{PLL}$

o, en otras palabras

\begin{matrix} (Respuesta 1) & F [norte] = F [norte - 1] + F [norte - 2] + F [norte - 3] \end{matrix}

$f[n]=f[n-1]+f[n-2]+f[n-3]\tag{Answer 1}$

con $f[0]=1,\, f[1]=2,\, f[2]=2^2=4$ .

Pero desde

F [norte - 1] = F [norte - 2] + F [norte - 3] + F [norte - 4]

$f[n-1]=f[n-2]+f[n-3]+f[n-4]$

tenemos

\begin{matrix} (Respuesta 2) & F [norte] = 2 F [norte - 1] - F [norte - 4] \end{matrix}

$f[n]=2f[n-1]-f[n-4]\tag{Answer 2}$

con el valor inicial adicional $f[3]=2^2+2+1=7$ .

La respuesta general (incluyendo la posibilidad de una ausencia) será

F [norte] + \sum_{k = 1}^{norte} F [k - 1] F [norte - k]

$f[n]+\sum_{k=1}^{n}f[k-1]f[n-k]$

porque hay $f[n]$ secuencias válidas sin ausencia y $\sum_{k=1}^{n}f[k-1]f[n-k]$ secuencias con $1$ ausencia (la ausencia A puede estar en posiciones $k=1\ldots n$ con una secuencia válida de Ps y Ls a ambos lados de la A).

Genial, gracias Esta explicación fue perfectamente clara y la respuesta final coincide con la solución de trabajo. Aún así, ¿pudiste ver si la explicación del autor también era correcta? Pregunto porque comencé a sospechar que estaba mal, y el autor simplemente estaba tratando de encajar su propia explicación para la fórmula de la Respuesta 2 que en realidad copió de otro lugar. No veo cómo su enfoque es correcto.
@AndrewCheong, debo admitir que solo escaneé el método del autor, pero me pareció un poco complicado. Aún así, la respuesta dada está de acuerdo con la mía, por lo que debe ser correcta;) En una inspección más cercana, aunque todavía no estoy seguro, parece que me hizo algo similar, pero ... hmmm ... no, no puedo verlo. Quizá le eche otro vistazo mañana...
Gracias de nuevo por echar un vistazo extra. ¿Dónde puedo encontrar más información sobre por qué es adecuado establecer f[0] = 1? ¿Es esto típico (o una regla) en las relaciones de recurrencia? ¿Quizás relacionado con exponentes que nunca dan como resultado 0?
@AndrewCheong. Es una convención tener una secuencia vacía (a menos que sus condiciones indiquen explícitamente que, por ejemplo, las secuencias deben tener una cierta longitud $\gt 0$ ). Configurando $f[0]=1$ podemos calcular $f[3]$ de la recurrencia $f[3]=f[2]+f[1]+f[0]$ . El $f[0]$ cuentas a plazo para la sucesión $(\text{valid sequence of length $0$}) \text{PLL}$ o solo $\text{PLL}$ . si empezamos con $f[1]$ entonces tenemos que declarar $f[1]$ , $f[2]$ y $f[3]$ como condiciones iniciales. pero calculando $f[3]$ requiere que usemos la recurrencia de todos modos agregando el caso único de $\text{PLL}$ a $f[1]+f[2]$ .
respuesta muy clara +1 mucho mejor que la respuesta oficial :) o la mayoría de las alternativas en projecteuler.net/problem=191 (un problema equivalente)
@antkam. ¡Muchas gracias por esas amables palabras! Aunque esto tiene más de un año, es gratificante saber que mi respuesta todavía se usa y se aprecia.

Relación de recurrencia en un problema de asistencia estudiantil

andres cheon

Problema de asistencia del estudiante

Solución oficial

Tintorero Franklin Pezzuti

andres cheon

esquistos del norte

andres cheon

Antkam

Respuestas (1)

esquistos del norte

andres cheon

esquistos del norte

andres cheon

esquistos del norte

Antkam

esquistos del norte

¿Por qué surge esta relación de recurrencia en la que nnn elige kkk? [duplicar]

Números de Fibonacci solución a esta relación de recurrencia

¿Número de rutas entre puntos en una cuadrícula con nodos bloqueados?

Encontrar la fórmula cerrada para An+BnAn+BnA_n + B_n para las recursiones AnAnA_n y BnBnB_n

Contando las formas en la cuadrícula si uno puede moverse de (x,y)(x,y)(x,y) a (x+a,x+b)(x+a,x+b)(x+a, x +b) para x,y,a,b≥0x,y,a,b≥0x,y,a,b\geq 0 arbitrario.

¿Recurrencia de qqq-análogo para los números de Stirling?

Encontrar una relación de recurrencia sobre un diccionario dado

q-Análogo de la fórmula xn=∑k{nk}(x)kxn=∑k{nk}(x)kx^n=\sum_k\left\{n\atop k\right\}(x)_k.

Probabilidad de que la caminata aleatoria alcance el estado kkk por primera vez en el paso nnn

Una suma de números de Stirling del segundo tipo