J'obtiens ce code de leetcode.

class Solution(object):
    def myPow(self, x, n):
         if n == 0: 
             return 1
         if n == -1: 
             return 1 / x
         return self.myPow(x * x, n / 2) * ([1, x][n % 2])

Ce code est utilisé pour implémenter poe(x, n), ce qui signifie x**n en Python.

Je veux savoir pourquoi il peut implémenter pow(x, n).

Ça n'a pas de sens ...

Je comprends

if n == 0: 
and
if n == -1:

Mais le code de base:

self.myPow(x * x, n / 2) * ([1, x][n % 2])

Est vraiment difficile à comprendre.

BTW, ce code ne fonctionne que sur Python 2.7. Si vous voulez tester sur Python 3, vous devez changer

myPow(x*x, n / 2) * ([1, x][n % 2])

À

myPow(x*x, n // 2) * ([1, x][n % 2]) 
6
Mars Lee 7 mars 2016 à 09:51

3 réponses

Meilleure réponse

La fonction récursive consiste à calculer la puissance (très probablement entier , non négatif ou -1, puissance) d'un nombre, comme vous vous en doutez (quelque chose comme x = 2.2 et {{ X2}}).

(Et cela semble être écrit pour Python 2.x (car n/2 ayant un résultat attendu de integer au lieu de n//2))

Les returns initiaux sont des calculs très simples.

 if n == 0: 
     return 1
 if n == -1: 
     return 1 / x

Lorsque la puissance est 0, alors vous retournez 1 puis la puissance est -1, vous retournez 1/x.

Maintenant, la ligne suivante se compose de deux éléments:

self.myPow(x * x, n/2)
and
[1, x][n%2]

Le premier self.myPow(x * x, n/2) signifie simplement que vous voulez augmenter la puissance (pas 0 ou -1) en deux en faisant la quadrature du nombre propulsé x

(très probablement pour accélérer le calcul en réduisant le nombre de multiplications nécessaires - imaginez si vous avez des raisons de calculer 2^58. Par multiplication, vous devez multiplier le nombre 58 fois. Mais si vous le divisez en deux à chaque fois et le résolvez récursivement, vous vous retrouvez avec un plus petit nombre d'opérations).

Exemple:

x^8 = (x^2)^4 = y^4 #thus you reduce the number of operation you need to perform

Ici, vous passez x^2 comme argument suivant dans le récursif (c'est-à-dire y) et le faites récursivement jusqu'à ce que la puissance soit 0 ou -1.

Et le suivant est que vous obtenez le module de deux de la puissance divisée. Il s'agit de compenser le cas impair (c'est-à-dire lorsque la puissance n est impaire).

[1,x][n%2] #is 1 when n is even, is x when n is odd

Si n est odd, alors en faisant n/2, vous perdez un x dans le processus. Il faut donc rattraper en multipliant le self.myPow(x * x, n / 2) par ce x. Mais si votre n n'est pas impair (pair), vous n'en perdez pas un x, vous n'avez donc pas besoin de multiplier le résultat par x mais par 1.

À titre d'illustration:

x^9 = (x^2)^4 * x #take a look the x here

Mais

x^8 = (x^2)^4 * 1 #take a look the 1 here

Ainsi, ceci:

[1, x][n % 2]

Consiste à multiplier la récursivité précédente par 1 (pour le cas pair n) ou x (pour le cas impair n) et équivaut à l'expression ternaire:

1 if n % 2 == 0 else x
4
Ian 7 mars 2016 à 07:36

C'est une technique de division et de conquête. L'implémentation ci-dessus est un moyen rapide de calculer l'exponentiation. À chaque appel, la moitié des multiplications sont éliminées.

En supposant que n est pair, x ^ n peut être écrit comme ci-dessous (si n est impair, il nécessite une multiplication supplémentaire)

x^n = (x^2)^(n/2)
or
x^n = (x^n/2)^2

La fonction ci-dessus implémente la 1ère version. Il est également facile d'implémenter le 2ème (j'ai supprimé les cas de base de récursivité ci-dessous)

r = self.myPow(x,n/2)
return r * r * ([1, x][n % 2])
0
zero_to_one 8 mars 2016 à 03:21

La bonne réponse pourrait être ci-dessous

class Solution:
    def myPow(self, x: float, n: int) -> float:

        if n == 0: 
            return 1
        if n > 0:
            return self.myPow(x * x, int(n / 2)) * ([1, x][n % 2])
        else:
            return self.myPow(x * x, int(n / 2)) * ([1, 1/x][n % 2])
0
LittleWat 19 mai 2019 à 08:23