2
votes

Fonction récursive pour calculer si 11 divise un nombre

J'essaie de coder une fonction récursive (utilisée Python) pour calculer si 11 divise un nombre sans utiliser le repos, la soustraction par 11. Je dois juste utiliser cette règle https://en.wikipedia.org/wiki/11_ (numéro)

Le code fonctionne, mais .. je voudrais savoir s'il existe un moyen de le réduire, peut-être sans avoir besoin de la variable "k"?

def f(n, k=0):
    if n=="" : return 0
    t = ((-1)**(len(n)-1))*int(n[0]) + f(n[1:],k+1)
    if k == 0:
        if t <= -11 or t >= 11:
            return f(str(abs(t)))
        elif t == 0:
            return True
        else:
            return False
    return t

python algorithm recursion

4 commentaires

Je suppose que c'est juste pour le plaisir ou un exercice? Étant donné qu'en réalité, vous utiliseriez simplement tester la valeur de int (n)% 11

bien sûr .. juste un exercice

@MarzioPinto quel type de données utilisez-vous comme entrée n ? n est-il une chaîne? sinon len (n) renvoie TypeError: l'objet de type 'int' n'a pas de len ()

Oui, une chaîne. Je viens de l'écrire dans quelques minutes. La principale préoccupation concerne la variable k .. J'ai utilisé une chaîne juste pour plus de facilité

4 Réponses :

0
votes

Est-il censé être strictement récursif? Aucune itération n'est autorisée? Pour éviter d'utiliser k comme profondeur de récursivité, vous pouvez opter pour une méthode semi-récursive et calculer t avec une itération et utiliser la récursivité pour la réduction de t.

def f(n):
    t = 0
    for i in range(len(n)):
        t += (-1)**(i)*int(n[i])

    if t == 0 :
        return True
    if t < 11 and t > -11:
        return False

    return f(str(abs(t)))

0 commentaires

0
votes

Ce n'est pas exactement ce que vous recherchez, mais vous pouvez modifier votre fonction pour calculer le résultat de n mod m , puis vérifier si c'est zéro. Quelque chose comme ça pourrait être simplifié en:

>>> mod11("242311") == 0
False
>>> not mod11("242311")
False
>>> not mod11("242308")
True

Utilisation:

def mod11(n):
    if not n: return 0
    diff = int(n[-1]) - mod11(n[:-1])
    if diff < 0: diff = diff and 11 - mod11(str(-diff))
    return diff

6 commentaires

Pour de nombreuses valeurs de n , ce code lève une exception: "NameError: le nom 't' n'est pas défini" - la variable t est utilisée mais jamais définie.

@cdlane oups, j'ai travaillé sur le code et le schéma de dénomination d'OP, mais quand j'ai posté ici, j'ai remplacé les noms de variables pour être plus descriptifs. Je suppose que j'ai raté un t .

Vous avez toujours une variable t non définie dans la dernière ligne return mod11 (str (t)) mais je ne peux pas me convaincre que cette ligne est jamais exécutée ...

@cdlane ouais, tu as encore raison. Je n'ai pas repéré celui-là, et mes tests après avoir corrigé cet autre t n'ont soulevé aucune exception. Je l'ai brutalement forcé à 10000000 sans exception, mais plus convaincant, je pense qu'il peut être prouvé qu'il ne s'exécutera pas.

Pour que ce retour s'exécute, diff doit être > = 11 , ce qui signifie que si diff <0 a échoué car cela renvoie des valeurs inférieures à 11, donc int (n [ -1]) - mod11 (n [: - 1]) doit être > = 11 . Cela signifierait que mod11 (n [: - 1]) doit être <= - 2 , ce qui n'est pas possible.

Correction du code pour supprimer cette instruction et le conditionnel inutile. Merci encore cdlane

1
votes

Retournons la conception en une récursion de queue (n non optimisée), donc plutôt que d'utiliser k pour détecter le retour au niveau supérieur, nous transmettons la valeur croissante de t vers le bas et faire le calcul final lorsque nous atteignons le cas de base:

def f(n, t=0):
    if not n:
        if -11 < t < 11:
            return t == 0

        return f(str(abs(t)))

    return f(n[1:], int(n[0]) - t)

Maintenant, nous retournons toujours un booléen au lieu du précédent résultat mixte booléen et entier!

0 commentaires

0
votes

C'est le mieux que je puisse faire jusqu'à présent pour une récursion pure (c'est-à-dire juste une variable). Il renverra le booléen, True, si la chaîne évalue à zéro mod 11 ou un nombre autrement.

def f(s):
  if not s:
    return True

  r = f(s[1:])

  # If the rest of the string evaluates to
  # to zero mod 11, there's no need to
  # subtract it from the prefix.
  if isinstance(r, bool):
    return s[0]

  n = int(s[0]) - int(r)

  return True if n in [-11, 11, 0] else n

for x in ['11', '121', '54734', '1099989', '12', '65637', '1565432', '2345651']:
  print (x, f(x))

0 commentaires