webentwicklung-frage-antwort-db.com.de

Berechne die letzte (dezimale) Ziffer von x1 ^ (x2 ^ (x3 ^ (... ^ xn)))

Ich muss die Einheitsziffer von x1 ^ (x2 ^ (x3 ^ (... ^ xn))) aus ganzen Zahlen finden, die als Liste an die Funktion übergeben werden . Die Eingabe [3, 4, 2] würde beispielsweise 1 zurückgeben, da 3 ^ (4 ^ 2) = 3 ^ 16 = 43046721 die letzte Ziffer 1. .__ ist. Die Funktion muss effizient sein möglich, weil offensichtlich der Versuch, 767456 ^ 981242 zu berechnen, nicht sehr schnell ist. 

Ich habe einige Methoden ausprobiert, aber ich denke, der beste Weg, dies zu lösen, ist die Verwendung von Sequenzen. Zum Beispiel endet eine Zahl, die auf 1 endet, wenn sie auf eine Potenz erhöht wird, immer auf 1. Bei 2 endet die resultierende Nummer entweder 2, 4, 6 or 8. Wenn eine Zahl zu einer Potenz erhöht wird, folgt die letzte Ziffer der resultierenden Zahl einem Muster, das auf der letzten Ziffer des Exponenten basiert:

1: Sequenz ist 1

2: Sequenz ist 2, 4, 8, 6

3: Sequenz ist 3, 9, 7, 1

4: Sequenz ist 4, 6

5: Sequenz ist 5

6: Sequenz ist 6

7: Sequenz ist 7, 9, 3, 1

8: Sequenz ist 8, 4, 2, 6

9: Sequenz ist 9, 1

0: Sequenz ist 0

Ich denke, der einfachste Weg, um die Gesamtzahl der letzten Ziffer zu berechnen, besteht darin, rückwärts durch die Liste zu arbeiten und die letzte Ziffer jeder Berechnung einzeln zu berechnen, bis ich wieder an den Anfang komme, aber ich bin mir nicht sicher, wie ich das tun soll. Wenn jemand helfen könnte oder eine andere Methode vorschlagen würde, wäre dies ebenso oder effizienter. 

Ich habe diesen Code bis jetzt, aber es funktioniert nicht für sehr große Zahlen

def last_digit(lst):
    if lst == []:
        return 1

    total = lst[len(lst)-2] ** lst[len(lst)-1]
    for n in reversed(range(len(lst)-2)):
        total = pow(lst[n], total)

    return total%10

Edit: 0 ^ 0 sollte als 1 angenommen werden

6
Harry Day

x ^ n = x ^ (n% 4), da die letzte Ziffer immer eine Periode von 4 hat. 

x  ^2  ^3  ^4  ^5

1   1   1   1   1
2   4   8   6   2
3   9   7   1   3
4   6   4   6   4
5   5   5   5   5
6   6   6   6   6
7   9   3   1   7
8   4   2   6   8
9   1   9   1   9

Wie Sie sehen, haben alle 9 Ziffern eine Periode von 4, sodass wir% 4 verwenden können, um Berechnungen zu vereinfachen.

Es gibt auch ein Muster, wenn wir dies tun% 4.

x  ^0  ^1  ^2  ^3  ^4  ^5  ^6  ^7  ^8  ^9
1   1   1   1   1   1   1   1   1   1   1
2   1   2   0   0   0   0   0   0   0   0
3   1   3   1   3   1   3   1   3   1   3
4   1   0   0   0   0   0   0   0   0   0
5   1   1   1   1   1   1   1   1   1   1    (all %4)
6   1   2   0   0   0   0   0   0   0   0
7   1   3   1   3   1   3   1   3   1   3
8   1   0   0   0   0   0   0   0   0   0
9   1   1   1   1   1   1   1   1   1   1

Wie gezeigt, gibt es für jedes x ein Muster, wenn n> 1 ist. Daher kann man sehen, dass (x ^ n)% 4 = (x ^ (n + 4k))% 4 ist, wenn n> 1 ist. Wir können dann die Probleme verhindern, die sich aus n = 0 und n = 1 ergeben, indem wir 4 zu n addieren. Wenn (x ^ n)% 4 = (x ^ (n + 4k))% 4 ist, dann gilt (x ^ n)% 4 = (x ^ (n% 4 + 4))% 4.

powers = [3, 9, 7, 1]

lastDigit = 1

for i in range(len(powers) - 1, -1, -1):
    if lastDigit == 0:
        lastDigit = 1
    Elif lastDigit == 1:
        lastDigit = powers[i]
    else:
        lastDigit = powers[i]**(lastDigit%4+4)

print(lastDigit%10)
2
Dan

Das ist mehr Mathematik als Programmieren. Beachten Sie, dass alle von Ihnen aufgelisteten Sequenzen eine Länge von entweder 1, 2 oder 4 haben. Genauer gesagt endet x^4 immer mit 0, 1, 5, 6 wie auch x^(4k). Wenn Sie also x^(m mod 4) mod 10 kennen, wissen Sie x^m mod 10.

Nun, um x2^(x3^(...^xn)) mod 4 zu berechnen. Die Geschichte ist sehr ähnlich, x^2 mod 4 ist Äther 0, wenn x=2k oder 1 wenn x=2k+1 (warum?). So

  1. ist 0, wenn x2 == 0 ist
  2. ist 1, wenn x2> 0 und x3 == 0 ist
  3. wenn x2 gerade ist, dann ist es entweder 2 oder 0 mit 2 nur bei x2 mod 4 == 2 and (x3==1 or (any x4,...xn == 0) ).

  4. wenn x2 ungerade ist, dann x2^2 mod 4 == 1, so erhalten wir 1, wenn x3 gerade x2 mod 4 ist.

Genug Mathematik, lass uns das Codieren sprechen. Es mag Eckfälle geben, die ich nicht behandelt habe, aber es sollte in den meisten Fällen funktionieren.

def last_digit(lst):
    if len(lst) == 0:
        return 1

    x = lst[0] % 10
    if len(lst) == 1:
        return x

    # these number never change
    if x in [0,1,5,6]:
        return x

    # now we care for x[1] ^ 4:
    x1 = x[1] % 4

    # only x[0] and x[1]
    if len(lst) == 2 or x1==0:
        return x[0] ** x1 % 10

    # now that x[2] comes to the picture
    if x1 % 2: # == 1
        x1_pow_x2 = x1 if (x[2]%2) else 1
    else: 
        x1_pow_x2 = 2 if (x1==2 and x[2]%2 == 1) else 0

    # we almost done:
    ret = x ** x1_pow_x2 % 10

    # now, there's a catch here, if x[1]^(x[2]^...^x[n-1]) >= 4, 
    # we need to multiply ret with the last digit of x ** 4
    if x[1] >=4 or (x[1] > 1 and x[2] > 1):
        ret = (ret * x**4) % 10

    return ret
2
Quang Hoang

Wenn Sie die Idee Ihrer Sequenzen ausarbeiten und sie ausarbeiten, möchten Sie ein Wörterbuch erstellen, das alle relevanten Sequenzen abbilden kann.

mapping = {}
for i in range(1, 10):
    mapping[i] = [i]
    last_digit = i
    while True:
        last_digit *= i
        last_digit = last_digit%10
        if last_digit in mapping[i]:
            break
        else:
            mapping[i].append(last_digit)

print(mapping)

Dies erzeugt Ausgabe: Zuordnung 

{1: [1],
 2: [2, 4, 8, 6],
 3: [3, 9, 7, 1],
 4: [4, 6],
 5: [5],
 6: [6],
 7: [7, 9, 3, 1],
 8: [8, 4, 2, 6],
 9: [9, 1]}

Jetzt kann die eigentliche Logik beginnen. Der Schlüssel zum Mitnehmen besteht darin, dass sich das Muster nach Abschluss der Sequenz wiederholt. Es ist also egal, wie groß die Leistung ist, wenn Sie nur einen Modulo verwenden und herausfinden, welche Position der Sequenz sie einnehmen soll. 

def last_digit_func(lst, mapping):
    if lst == []: #taken from OP
        return 1
    last_digit = lst[0] % 10
    if 0 in lst[1:]: #Edge case 0 as a power
        return 1
    if last_digit == 0: #Edge case 0 at start
        return last_digit

    for current_power in lst[1:]:
        if len(mapping[last_digit]) == 1:
            return last_digit
        ind = current_power % len(mapping[last_digit])
        ind -= 1 #zero indexing, but powers start from 1. 
        last_digit = mapping[last_digit][ind]
    return last_digit

test1 = [3, 4, 2]
print(last_digit_func(test1, mapping)) #prints 1 

Ich habe das durch die Berechnung der Potenzen in Python bestätigt.

test2 = [767456 , 981242]
print(last_digit_func(test2, mapping)) #prints 6

Und ich habe versucht, dies zu überprüfen, indem ich es in Python laufen lasse. Ich bereue es sofort und mein Programm versucht immer noch, es zu lösen. Naja :)

0
Paritosh Singh