wykonanie pętli n^n razy

0

Witam,
mam problem tego typu, że chcę wykonać jakąś czynność nn razy, przy czym wynik tego potęgowania jest zbyt duży aby został przypisany do jakiejkolwiek zmiennej (i później stał się warunkiem zakończenia pętli). Chcę to zastąpić jakimś zestawem pętli, który umożliwi mi wykonanie danej sekwencji kodu nn razy, ale nie mam pomysłu jak to zrealizować. Proszę o pomoc.

0

Przecież to zajmie wieki... Co Ty chcesz zrobić?

1

EDIT: n^2 przeczytałem :D zaraz napiszę :P

0

@up - minuta pisania, co ty tam 12 minut piszesz, BigNumy implementujesz? :]

Na oko:

void foo(int n, int m)
{
    if (m <= 0) { return; }
    for(int i = 0; i < n; i++)
    {
        if (m == 1) { operation(); }
        foo(n, m - 1);
    }
}
0

@gumka zróbmy szybkie obliczenia:
maksymalna wartość którą możesz zapisać w zmiennej niech będzie to 64 bitowy unsigned long long, czyli mamy 2^64 = 18446744073709551616
Załóżmy więc że chcesz wykonać jakąś czynność dokładnie tyle razy (a ponoć chcesz więce, bo ci się nie mieści...). Załóżmy że twoja czynność zabiera 1 takt zegara (a nie zabiera, bo zabiera przynajmniej kilka) na procku który ma 5GHz (a nie ma, bo ma pewnie połowę z tego) czyli jesteś w stanie wykonać 5 miliardów operacji na sekundę. Daje nam to:
18446744073709551616 / 5 000000000 = 3689348814,7419103232 sekund = 61489146,912365172053333333333333 minut = 1024819,1152060862008888888888889 godzin = 42700,79646692025837037037037037 dni = 116,98848347101440649416539827499 lat
Przypominam że założyłem tutaj dość gruby margines i w realnej sytuacji to będzie kilka(naście) razy dluzej...

Nie róbmy sobie jaj, nie bez przyczyny potocznie mówi się że problemy O(2n) czy O(n!) są "nierozwiązywalne". O(nn) to już w ogóle jakiś chory pomysł...

0

@msm:
Usunąłem posta, bo mylnie stwierdziłem, że twoje rozwiązanie działa w miejscu. Otóż ono nie działa w miejscu, bo wykorzystuje stos o rozmiarze Theta(n * log(baza)), dokładnie tyle samo co BigNum, który by reprezentował ten sam stan co stos. Inaczej mówiąc: tworzysz BigNuma na stosie. Mam nadzieję, że teraz wybaczysz mi usunięcie posta :P

PS:
Cyfry tego BigNuma można pobrać przechodząc ramki stosu i wyciągając wartości lokalnych zmiennych 'i' z pętli. No i oczywiście twoja metoda ma narzut związany z ramkami stosu, którego normalne BigNumy nie mają.

1 użytkowników online, w tym zalogowanych: 0, gości: 1