Cycle Detection Algorithm

[•Dddarius95]

 Salut. Am incercat problema Albinuta de la ONI 2008 . Am o problema cu algoritmul Floyd de detectie a ciclurilor intr.un sir.
am facut la fel ca pe http://en.wikipedia.org/wiki/Cycle_detection . Pe albinuta iau doar 15p.
intr-adevar da incorect.pe unul din testele oficiale sirul ar fi

Cod:

1 2 4 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 1 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 2 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 3 4 1 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 1 2 4 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 2 4 5 2 4 1 3 5 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 3 4 5 2 4 1 2 4 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 1 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 1 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 1 3 5 2 4 1 3 5 2 3 5 1 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 1 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 1 2 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 1 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 1 2 4 1 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 1 3 5 2 3 4 1 2 4 5 2 4 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 2 4 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 2 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 1 2 4 1 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3 5 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 1 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 1 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 1 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 1 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 5 1 3 5 2 4 1 3 5 2 3 5 1 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 3 5 2 3 5 2 3 5 2 3 5 2 3 4 1 2 4 1 3 5 2 3

iar algoritmul meu imi returneaza miu=4 lambda=3 ceea ce este gresit...

Cod:

#define F(i) i+1

void find()
{
    tortoise = F(0);
    hare =F(F(0));
    while (x[tortoise] != x[hare])
    {
         tortoise = F(tortoise);
         hare = F(F(hare));
    }

}

void find_miu()
{
    miu=0;
    tortoise = 0;
    while (x[tortoise] != x[hare])
    {
        tortoise = F(tortoise);
        hare = F(hare);
        miu++;
    }

}

void find_lambda()
{
    lambda=1;
    hare = F(tortoise);
    while (x[tortoise] != x[hare])
    {
        hare = F(hare);
        lambda++;
    }
}

LE: ma poate ajuta cineva?

[•freak93]

Scuza ca nu te ajut in niciun fel, nu prea am timp.

Vreau doar sa te rog sa postezi pe pagina problemei de acum inainte, exista deja un topic deschis pentru problema albinuta. http://www.infoarena.ro/forum/index.php?topic=3078.0