Numeros de Markov

Hola amig@s,
Si os gustan los números de Fibonacci esto lo tenéis que ver.

Los números de Markov son más complicados y la verdad, no he encontrado más que una referencia en inglés en la red (sin el algoritmo además), así que esta entrada puede ser útil para alguien.

Los números se obtienen a partir de la ecuación de Markov:

x^2 + y^2 + z^2 = 3 x y z

Queremos hacer un programa que muestre los trios de números naturales que cumplen la ecuación.

La forma de obtenerlos que he leído en el libro dónde he sabido de los números de Markov está mal enunciada, y ha sido en la wikipedia inglesa dónde he encontrado estas pistas:

1.-Empezamos por el trío (1, 1, 1) que son números de Markov.
2.-Si (x, y, z) es un trío que satisface la ecuación, entonces (x, y, 3xy-z) también lo cumple.

Hay complicaciones adicionales cuando queremos trasladar esto a un lenguaje de programación:

1.-Cuando aplicas dos veces a un trío la equivalencia (x, y, 3xy-z), vuelves atrás ya que en el tercer elemento ocurre que... 3xy-(3xy-z)=z,... o sea que la cosa vuelve a (x, y, z).

2.-En principio en el trío no hay un orden establecido. (x, y, z) = (y, x, z) = (z, x, y)...
Pero si queremos visualizar cómo evolucionan los números, conviene ordenar de alguna forma el trío en el algoritmo.

3.-El árbol binario (no es exactamente un árbol binario, pero casi) que encontramos en wikipedia nos ayuda a comprobar si los resultados están bien:


El programa que utiliza una función recursiva sería este:

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int cambiar(int *a, int *b)
{
    int comodin=*b;
    *b=*a;
    *a=comodin;
}

int recursiva(int num, int x, int y, int z)
{
int a;
num--;
if (num!=0){
    if(x>y) cambiar(&x,&y);
    if(y>z) cambiar(&y,&z);
    if(x>y) cambiar(&x,&y);
    cout<<x<<" "<<y<<" "<<z<<"\n";
    recursiva(num,x,z,(3*x*z)-y);
    recursiva(num,y,z,(3*y*z)-x);
}
}

int main()
{
    int x=1,y=1,z=1;
    int x1=1,y1=1,z1=1;
    int numeros;
    string entrada="";
    cout<<"\n\nNumeros de Markov:\n";
    cout<<"------------------\n";
    cout<<"Cuantas niveles quieres? ";
    getline(cin,entrada);
    stringstream myStream(entrada);
       if (myStream >> numeros)
        recursiva(numeros,x,y,z);
}

Y el resultado: