mar 29, 2010

Enviado por en Algoritmos, Ciencia, Programacion

Solución a ¿Cuántas formas?

Primero, no importan que caracteres son, con S=ABC o S=XYZ da la misma solución para cualquier N .

Segundo, veamos que podemos hacer si representamos la idea por grafos. Usemos el ejemplo dado, con S=ABC , existen arcos desde A para A , B y C ; desde B para B y C ; y desde C hasta C solamente, tal como se muestra en la figura siguiente.

Si representamos este grafo con una matriz de adyacencia A , esto es, una matriz cuyo elemento en la fila i y columna j es 1 si existe un arco desde el nodo representado por i al nodo representado por j y 0 en el caso contrario. Con el ejemplo sería:

A=\begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix}

Adicionalmente, existe un teorema que indica que dado un grafo, la matriz M resultante de elevar la matriz de adyacencia correspondiente al grafo a la n representa en cada elemento M_{ij} la cantidad de caminos diferentes de longitud n desde el nodo i al nodo j . Ahora, para una cadena de longitud 3 tal como ACC se define un camino de longitud 2 , es decir hay dos arcos: el primero de A hasta C y el segundo de C hasta C . En general para una cadena de L caracteres, la longitud del camino correspondiente es L-1 .

Veamos que tal.

A^2=\begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1\end{bmatrix}^2=\begin{bmatrix} 1 & 2 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & 1\end{bmatrix}

Según esto, existen dos caminos que van desde A hasta B (AAB y ABB ) y tres desde A hasta C (AAC , ABC y ACC ) lo cual es cierto, e incluso se cumple para el resto de los casos. Luego solo nos queda sumar cada caso dando el resultado al problema, en este caso diez.

Otro ejemplo, S=QWERTY con L=7 entonces la solución seria sumar cada elemento de,

\begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}^6=\begin{bmatrix} 1 & 6 & 21 & 56 & 126 & 252 \\ 0 & 1 & 6 & 21 & 56 & 126 \\ 0 & 0 & 1 & 6 & 21 & 56 \\ 0 & 0 & 0 & 1 & 6 & 21 \\ 0 & 0 & 0 & 0 & 1 & 6 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}

Lo cual nos da como respuesta 918 .

    Posts Relacionados

    2 Comentarios

    1. avatar
      Kalith dice:
      marzo 30, 2010 en 3:10 am

      ya dejaste de ser un padawan ya eres un gran maestro jedi :D

      Usando Firefox 3.6.2 Firefox 3.6.2 en Windows Vista Windows Vista
      • avatar
        Llyn dice:
        marzo 30, 2010 en 10:51 am

        Je je, aún no, este tipo de problemas es de aquel tipo de que si no te lo dicen, no se te ocurre, mi caso por ejemplo. Aunque creo que hay una solución por DP pero ya sera para después.

        Usando Opera 10.51 Opera 10.51 en Windows Vista Windows Vista

    Menciones/Notificaciones

    1. house extension costs melbourne - into series like part 1, part 2... etc. you can successfully build anticipation for your audience so they can catch that ...

    Dejar una respuesta

    Debes ser Alojarse para enviar un comentario.