Pour un problème de devoirs, on nous demande de définir une fonction qui comptera le nombre de chiffres consécutifs dans une chaîne binaire, et retournera le nombre.

Par exemple, la fonction doit retourner n = [4,8,4,3,15] pour l'entrée binaire S = ‘1111000000001111000111111111111111’.

Je l'ai jusqu'à présent, mais je sais que ce n'est pas correct, et je ne sais pas où aller à partir d'ici. Toute aide serait appréciée!

def consecutive_length(s):
    if s == '':
        return 0
    if s[0] == 0:
        return 0
    return 1 + consecutive_length(s[1:])

Remarque : nous ne pouvons utiliser aucune boucle. Il est nécessaire que nous le fassions avec récursivité.

Je vous remercie!

0
jape 7 mars 2016 à 21:32

3 réponses

Meilleure réponse

Voici, espérons-le, une méthode pythonique (en ignorant le fait que ce n'est pas pythonique pour résoudre ce type de problème de manière récursive):

def consecutive_length(s):
    def sub(idx, lst, last_char, count):
        try:
            c = s[idx]     # c will be the 'next' char
        except IndexError: # no more chars left to process
            if count:
                lst.append(count)
            return lst
        if c != last_char:
            lst.append(count)
            count = 0
        return sub(idx+1, lst, c, count+1)                            
    return sub(0, [], s[0] if s else None, 0)

  • la fonction externe prend simplement la chaîne comme argument et masque les paramètres supplémentaires des fonctions internes
  • idx est l'index de la chaîne, nous n'allouons pas de nouvelle chaîne à chaque appel récursif (et s [idx] est O (1) iirc)
  • au lieu de calculer la longueur de la chaîne, nous attendons qu'une exception se produise (EAFP - Plus facile de demander pardon que permission)

Essai:

>>> print consecutive_length('1111000000001111000111111111111111')
[4, 8, 4, 3, 15]    
>>> print consecutive_length('1111000000001111000111111111111110')
[4, 8, 4, 3, 14, 1]
>>> print consecutive_length('1')
[1]
>>> print consecutive_length('0')
[1]
>>> print consecutive_length('')
[]
2
uselpa 7 mars 2016 à 20:54

Je suppose ici que le «11» est une séquence consécutive de 1, donc «111» en a 2 consécutifs. Cette solution est, si les boucles ne sont pas un problème. Utilisez l'index pour trouver «11» et continuez jusqu'à ce que vous n'en trouviez plus. Le programme ci-dessous montre le nombre de 1 consécutifs.

cnt = 0
pos = -1
while True:
    try:
        pos = '111001100101111'.index('11', pos+1)
        cnt += 1
    except ValueError:
        print cnt
        break

Résultat:

6
0
Arindam Roychowdhury 6 févr. 2017 à 06:23

EDIT: uselpa a une bien meilleure façon de le faire.

Puisque les boucles ne sont pas autorisées:

def consecutive_length(s, output, prev_char, count):
    # if end of string, append last count and return output
    if s == '':
        output.append(count)
        return output
    # if curr_char is same as prev_char, add 1 to count and parse next char
    if s[0] == prev_char:
        return consecutive_length(s[1:], output, s[0], count + 1)
    # if curr_char is diff from prev_char, append count and reset count to 1
    else:
        prev_char = s[0]
        output.append(count)
        return consecutive_length(s[1:], output, s[0], 1)

Appelez-le avec consecutive_length(s, [], s[0], 0).

0
Chuck Logan Lim 8 mars 2016 à 05:34