tło

W tym wyzwaniu podstawowa breprezentacja liczby całkowitej njest wyrażeniem nsumy potęg b, gdzie każdy termin występuje w większości b-1przypadków. Na przykład podstawowa 4reprezentacja 2015to

4^5 + 3*4^4 + 3*4^3 + 4^2 + 3*4 + 3

Teraz, dziedziczny Base- bprzedstawienie notrzymuje się przez przeprowadzenie ich w wykładniki Base- breprezentacje następnie przekształcenie ich wykładniki itd rekurencyjnie. Zatem dziedziczna podstawowa 4reprezentacja 2015jest

4^(4 + 1) + 3*4^4 + 3*4^3 + 4^2 + 3*4 + 3

Jako bardziej złożony przykład dziedziczna 3reprezentacja bazy

7981676788374679859068493351144698070458

jest

2*3^(3^(3 + 1) + 2) + 3 + 1

Dziedziczne zmianę zasady z nod bceluc , oznaczone H(b, c, n)jest liczbą otrzymywaną poprzez dziedziczne zasadową- breprezentację n, zastępując co bo ci oceny uzyskanej ekspresji. Na przykład wartość

H(3, 2, 7981676788374679859068493351144698070458)

jest

2*2^(2^(2 + 1) + 2) + 2 + 1 = 2051

Wyzwanie

Są podane jako wejście trzy liczby całkowite b, c, n, dla których można założyć n >= 0i b, c > 1. Twój wynik to H(b, c, n). Wygrywa najkrótsza liczba bajtów, a standardowe luki są niedozwolone. Możesz napisać funkcję lub pełny program. Musisz być w stanie poradzić sobie z dowolnie dużymi wejściami i wyjściami (bignum).

Przypadki testowe

4 2 3 -> 3
2 4 3 -> 5
2 4 10 -> 1028
4 4 40000 -> 40000
4 5 40000 -> 906375
5 4 40000 -> 3584
3 2 7981676788374679859068493351144698070458 -> 56761
2 3 2051 -> 35917545547686059365808220080151141317047

Śmieszny fakt

Dla dowolnej liczby całkowitej nsekwencja uzyskana przez

n1 = n
n2 = H(2, 3, n1) - 1
n3 = H(3, 4, n2) - 1
n4 = H(4, 5, n3) - 1
....

w końcu sięga 0. Jest to znane jako twierdzenie Goodsteina .

CJam, 60 58 45 43 41 38 36 bajtów

Dzięki Optimizer za oszczędność dwóch bajtów.

l~:C;:B;{Bb)1$,,@f{1$~=C@)F#*+}~}:F~

Sprawdź to tutaj.

Porządkuje dane wejściowe w kolejności n b c.

Możesz użyć tego do testowania uruchomienia wszystkich przypadków testowych:

"3 4 2 
3 2 4 
10 2 4 
40000 4 4 
40000 4 5 
40000 5 4 
7981676788374679859068493351144698070458 3 2 
2051 2 3 "N/
{
~:C;:B;{Bb)1$,,@f{1$~=C@)F#*+}~}:F~
p}/

Wyjaśnienie

Jest to dość bezpośrednia implementacja procesu wyjaśnionego w wyzwaniu, z tym wyjątkiem, że przeplatam rekursywną ekspansję bazy, podstawienie zasady i obliczenie końcowego wyniku:

l~:C;:B;{Bb)1$,,@f{1$~=C@)F#*+}~}:F~
l~:C;:B;                             "Read and evaluate input, store b and c in B and C.";
        {                       }:F  "Define a block F. This performs the required conversion.";
         Bb                          "Get digits of input number in base B.";
           )                         "Split off 0-power digit.";
            1$,                      "Copy remaining digits. Get their length n.";
               ,                     "Make array [0 1 ... n-1].";
                @                    "Pull up remaining digits.";
                 f{           }      "Map this block onto the range, passing in the digits
                                      as a second argument each time.";
                   1$~=              "Copy current i, bitwise complement, access digit array.
                                      This accesses the digits in reverse order.";
                       C             "Push the new base C.";
                        @)           "Pull up current i and increment to get power.";
                          F          "Apply F recursively.":
                           ~         "Raise C to the resulting power.";
                            *        "Multiply by digit.";
                             +       "Add to running total.";
                               ~     "The result will be in an array. Unwrap it.";
                                   ~ "Execute F on the input n.";

Python 2, 55

H=lambda b,c,n,s=0:n and n%b*c**H(b,c,s)+H(b,c,n/b,s+1)

Rozwiązanie rekurencyjne. Podobnie jak algorytm rekurencyjny do konwersji między bazami, z tym że powtarza się również na wykładniku.

Podzieliliśmy się nna dwie części, bieżącą cyfrę n%bi wszystkie pozostałe cyfry n/b. Bieżąca wartość miejsca jest przechowywana w parametrze opcjonalnym s. Bieżąca cyfra jest konwertowana na bazę za cpomocą, c**a wykładnik wykładniczy sjest rekurencyjnie. Reszta jest następnie konwertowana w ten sam sposób, ponieważ +H(b,c,n/b,s+1)wartość miejsca sjest o jeden wyższa.

W przeciwieństwie do konwersji podstawowej dziedziczna konwersja bazy wymagała zapamiętania bieżącej wartości miejsca w rekursji, aby mogła zostać przekonwertowana.

Dla ułatwienia lektury, oto jak to wygląda, kiedy bi crozwiązywanych stałych globalnych.

H=lambda n,s=0:n and n%b*c**H(s)+H(n/b,s+1)