Teoría de grafos/Relaciones de recurrencia

Relaciones de Recurrencia

editar

La explicación de relaciones de recurrencia se encuentra como archivo en este enlace y puede ser descargado como archivo fuente de TeXmacs en este enlace. Si quiere ayudarnos a construir la versión Wiki del documento bienvenido.

Las relaciones de recurrencia se relacionan con problemas de algoritmos recurrentes, demostraciones por inducción y definiciones iterativas, ya que es posible transformar definiciones recursivas en definiciones iterativas, o bien expresar una relación de recurrencia como un algoritmo recursivo y en el caso de la inducción, esta también apela a un caso por defecto y se invoca a un caso previo (la hipótesis de inducción) para llegar a una demostración general.


Torres de Hanoi

editar

Las torres de Hanoi son un viejo problema para ampliar más la definición de este problema

Un ejemplo hecho en php


<?phpx
function hanoi($n, $origen, $aux, $destino){
   if($n>=1){
       hanoi($n-1, $origen, $destino, $aux);
       echo "mover de $origen a $destino\n";
       hanoi($n-1, $aux, $origen, $destino);
   }
}
echo "para 4\n";
hanoi(4, 1,2,3);
echo "para 1\n";
hanoi(1,1,2,3); 
?>