Problema relacionado con el triángulo de Pascal: Secuencia de Fibonacci en los lados

Question

Tengo este triángulo:

$$\begin{array}{} &&&&&&&1\\ &&&&&&1&&1\\ &&&&&2&&2&&2\\ &&&&3&&4&&4&&3\\ &&&5&&7&&8&&7&&5\\ &&8&&12&&15&&15&&12&&8\\ &13&&20&&27&&30&&27&&20&&13\\ 21&&33&&47&&57&&57&&47&&33&&21 \end{array}$$

(Original imagen .)

Como puedes ver este triángulo se construye como el Triángulo de Pascal excepto que en los lados tenemos la Secuencia de Fibonacci.

Mi objetivo es encontrar el $m$ número de $n$ fila (la primera fila se cuenta con $1$ El primer número de una fila se cuenta con $1$ ).

Ejemplo: $n=7, m=5$ La respuesta es $27$ .

¿Cómo puedo hacer esto sin calcular todo el triángulo? Tal vez es la fórmula, si es quiero saber lo que aprender con el fin de encontrar esa fórmula. Si encontrar una fórmula es demasiado difícil, tal vez hay un algoritmo más rápido que el cálculo de todo el triángulo.

La verdad es que tengo que escribir un programa para este problema, valor máximo para $n$ es $20000$ ( $m\le n$ ) y mi programa debería ejecutarse bajo $1$ segundo. En un momento los números se hacen demasiado grandes para mi pc así que tengo que calcular todo el triángulo en módulo $666013$ (No he elegido este número, son mis restricciones). Calculo sólo la mitad del triángulo, pero todavía demasiado lento, así que pensé que tal vez las matemáticas deben ayudar, así que lo que aprender?

Espero que pueda ayudarme. :)

Answer 1

Básicamente, para que el programa sea sencillo y fácil de entender, podemos utilizar dos FUNCIONES, una para calcular la Secuencia de Fibonacci y otra para calcular el mº número de la nª fila.

int Fibonacci(int n){

if(n==1 || n==2) devuelve 1;

si no, devuelve (Fibonacci(n-1) + Fibonacci(n-2));

}

int Pascal_Fibonacci(int n, int m){

if(m==1 || n==m) return Fibonacci(n);

si no, devuelve (Pascal_Fibonacci(n-1,m-1) + Pascal_Fibonacci(n-1,m));

}

Esta es la forma básica de calcular el número. Ahora, usted puede modificar de acuerdo a sus necesidades :)