Spróbowałem kilkoma sposobami obliczyć silnię ze 100.
W tym celu należy dobrze przygotować strukturę. Liczbę trzymam na liście dwukierunkowej o węzłach link postaci:
[int cyfra, link prev, link next, int flaga]
Okazało się, że same wskaźniki na sąsiednie cyfry prev oraz next nie wystarczą. Aby dobrze zaalokować liczbę na liście potrzebna była flaga, gdyż w przeciwnym przypadku były kłopoty z jednocyfrową liczbą 0. Nie była ona odróżniana od węzła pustego. Ponieważ węzły należały do dużego kontenera, szukanie w tym kontenerze wolnego miejsca na kolejną cyfrę wskazywało taką liczbę jako puste miejsce i nadpisywało...
Sama liczba ma dwa pola: link value oraz link baze. Składa się z cyfr dziesiętnych (docelowo), chwyconych za cyfrę najmniej znaczącą oraz podstawę systemu liczbowego.
Oprócz tego występują funkcje mnożenia przez 10 "mul0()" oraz przez małą wartość "mula( int a)". Dołączyłem także konwersje między systemami niedziesiątkowymi "convert (int new_baze)".
Wykorzystałem najpierw standardowe mnożenie dla liczenia silni z liczby n dla sprawdzenia wyników:
Liczba a;
for( i=n; 0<i; i-- )
a.mula(i);
a.show();
Następnie konwersje, by uniknąć kłopotów rozbiłem je na trzy fazy:
- liczenie 9! małymi iloczynami - by uzyskać odpowiednią wartość początkową;
- przekształcenie wartości do liczby w systemie o podstawie n;
- reszta obliczeń, by wynik wyszedł w dziesiątkowym:
Liczba a = 9!;
a.baze( n );
a.mul0();
for( i=n-1; 9<i; i-- ) {
a.convert(i);
a.mul0();
};
a.show();
Wreszcie rozklad kanoniczny czyli mieszanka konwersji oraz mul0() w odpowiednich systemach. I tu się sypało, uzyskana wartość była znacznie za mała.
W pozostałych też były kłopoty. Okazało się, że zarówno przy mnożeniu mula(int), jak i przy konwersjach nie mogę sobie pozwolić na przechowywanie reszt w dodatkowej zmiennej przechodząc między węzłami cyfr. Należy je przekazać sąsiedniej cyfrze zaraz po ich zaobserwowaniu. Inaczej czasem miewałem błędy oraz uzyskana wartość była zawyżana.
A oto szczególy funkcji:
mul0() { // mnożenie przez 10 (dokładniej: przez baze)
link cyfr = t.add(); // nowy węzeł z kontenera;
cyfr.cyfra = 0;
value->next = cyfr;
cyfr->prev = value;
value = cyfr;
};
czyli zwykłe doczepienie węzła z zerem na końcu liczby i uchwycenie go jako liczby.
mula( int a ) {}
// pierwszy przebieg: mnożenie każdej cyfry liczby przez a
link b = value;
while( b ) { b->item *= a; b=b->prev; }
// przeniesienia wartości
b = value;
int s=0;
while( 1 ) {
s = b->cyfra;
b->cyfra = s% 10; // system dziesiątkowy
s /= 10;
if( s ) {
if( b-> prev ) b->prev->cyfra += s;
else {
link c=t.add();
c->cyfra = s;
c->next = b; b->prev = c; // przypięcie węzła cyfry najbardziej znaczącej
}
};
s=0;
if( b->prev ) b = b->prev; else break;
};
Konwersja też jest podzielona na dwa moduły, w pierwszym wymagana jest liczba dwucyfrowa oraz ustawienie węzła blokującego b na cyfrę poprzedzajacą najbardziej znaczącą. Drugi węzeł link c przebiega cyfry bardziej znaczące od b ze wzorem s = cyfra*r, której część całkowita zasila bieżącą cyfrę wskazywaną przez c, zaś reszta jest odkładana do cyfry mniej znaczącej c->next->cyfra. Podstawa baze maleje, zatem wartość liczby rośnie.
int r = baze->cyfra - new-baze;
int s=0;
// modyfikacja pól baze
link b = value;
while( b->prev ) b = b->prev;
while( 1 ) {
if( b->next ) b = b->next; else break;
c = b->prev;
while( 1 ) {
s = c->cyfra * r;
c->cyfra += s/new_baze;
c->next->cyfra += s % new_baze;
if( c->prev ) c = c->prev; else break;
};
c=b; ... // druga część
};
W drugiej części zmieniamy kierunek c=b oraz przenosimy nadmiary podobnie jak przy mnozeniu mula(int).
Potem przesuwamy b = b->next; aż przekształcane będą wszystkie cyfry liczby.
Obydwoma sposobami w przeciągu sekund wypisało mi wartość wszystkich 158 cyfr dziesiętnych silni 100!
Brak komentarzy:
Prześlij komentarz