Algorytm Liczba-Inwersji (algorytm Ryttera)

Niech będzie permutacją liczbzadaną tablicą o zakresie .
Na przykład mamy inwersji w permutacji

Pomocniczą tablicą będzie , załóżmy że początkowo zawiera ona same zera.
Funkcja logiczna sprawdza czy liczba jest nieparzysta. Funkcja jest dzieleniem całkowitoliczbowym, pomijamy resztę.
Funkcja zwraca całkowitoliczbową część logarytmu przy podstawie, np..

Końcową wartością zmiennej wynik jest liczba inwersji permutacji P.

1

2 repeat times

3 for to do

4 if then

5 else

6 for to do

7

Mam ten problem że nie wiem czy algorytm jest poprawny bo dla np.3,2,1 są 3 inwersje a jak liczę tym algorytmem to mi wychodzi 1

liczę tak że dla i=0 licz[3]=1
i=1 wynik=licz[2+1]=1
i=2 licz[2]=1

czyli wynik 1 a powinno być 3...

Proszę o pomoc

Wygląda na to, że repeat działa 1 raz a powinien 2. Tak samo w przypadku podanych wyżej 7 liczb, pętla działa o 1 raz za mało. Nie doszukałem się 'oryginalnego' algorytmu w sieci, tylko na tej stronie z której Ty korzystałeś i rzeczywiście jest tam 'całkowitoliczbowa część logarytmu' a bardziej wygląda to na zaokrąglenie. Proponuję poszukać bezpośrednio u Ryttera.

(3,2,1) ** nie jest** permutacją dla algorytmu Ryttera. Sprawdź co dostaniesz dla permutacji (2,1,0).

bogdans napisał(a):

(3,2,1) ** nie jest** permutacją dla algorytmu Ryttera. Sprawdź co dostaniesz dla permutacji (2,1,0).

Dla tej permutacji dostałem 1. Poza tym, tak jak wspomniałem wyżej dla (5,4,3,6,0,1,2) też dostaję niepoprawny wynik.

tu: http://smurf.mimuw.edu.pl/node/287
jest błąd jest w opisie ile ma się razy wykonywać pętla z log n.
Zwiększ iterację o 1 i zadziała.
Chodzi o to by na końcu p ma zawierać same zera, a o tym decyduje największa liczba w ciągu równa n-1.
Czyli jeśli masz permutację o długości 4 to największa liczba w tej permutacji to 3, którą trzeba podzielić przez 2 dwa razy
dla długości 5 największa liczba to to 4, którą trzeba podzielić przez 2 trzy razy.
czyli powinno być reapeat log(n-1) +1 times

Ja na poprawne rozwiązanie wpadłem przypadkiem, nie chciało mi się liczyć na kartce, więc zaimplementowałem opisany w pierwszym poście algorytm. W implementacji zrobiłem błąd, i ta "błędna" implementacja daje poprawne wyniki. Błąd, to

for(int step=1;step<=log(n + 1);step++)

zamiast podanego w opisie

for(int step=1;step<=log(n);step++)

Przy okazji, wymaganą funkcję log można napisać bez użycia liczb zmiennoprzecinkowych.

    int log(int n)
    {
        int power = 1;
        int result = 0;
        while(power*2 <= n)
        {
            power*=2;
            result++;
        }
        return result;
    }

bogdans napisał(a):

Przy okazji, wymaganą funkcję log można napisać bez użycia liczb zmiennoprzecinkowych.

    int log(int n)
    {
        int power = 1;
        int result = 0;
        while(power*2 <= n)
        {
            power*=2;
            result++;
        }
        return result;
    }

nt RoundDownBinLog(int x)
{
	int result = 0;
	while (x>>=1)
		++result;
	return result;
}

http://ideone.com/3lmTHK