Aller au contenu

E08 - Addition binaire⚓︎

Le problème

Addition binaire

Proposition 1⚓︎

🐍 Script Python
import doctest


def additionne(liste_bin: list) -> list:
    """
    Fonction qui réalise la somme de ces nombres et qui place le résultat dans
    une chaine de caractères également en base 2, et du même nombre de 
    chiffres (les dépassements éventuels sont ignorés).

    additionne(['0110', '1001'])
    [1, 1, 1, 1]
    """
    retenue = 0
    ans = [0 for _ in liste_bin[0]]
    for i in range(len(liste_bin[0])):
        compte = 0
        for nombre_bin in liste_bin:

            if nombre_bin[-i-1] == "1":
                compte += 1

        compte += retenue
        if compte % 2 == 0:
            ans[-i-1] = 0
            retenue = compte // 2
        else:
            ans[-i-1] = 1
            retenue = compte // 2

    return ans

import doctest
doctest.testmod()

# Entrées
nb_chiffre_valeur_additioner = int(input())
nb_valeurs = int(input())
liste_valeur = [input() for _ in range(nb_valeurs)]

# Sorti
print(*additionne(liste_valeur), sep='')
  • Revoir le doctest,

    • tu l'as importé deux fois
    • il manque les chevrons >>>
    • tu devrais aussi ajouter un doctest avec une retenue perdue.
  • Pour la sortie, danger, le unpack peut faire peur à certaines personnes, mais plaire à d'autres.

  • Il serait bon que ta sortie soit du même type que les éléments d'entrée... Ici, il vaudrait mieux renvoyer une str résultat du collage.

Corrigé du professeur⚓︎

Version itérative⚓︎

🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2004/semifinal/addition_binaire
"""

def division_par_2(n):
    """Renvoie le quotient et le reste de n divisé par deux.

    >>> division_par_2(13)
    (6, 1)

    >>> division_par_2(42)
    (21, 0)

    """
    # au choix plusieurs méthodes
    return (n//2, n%2)
    return divmod(n, 2)
    return n>>1, n&1


def somme_binaire(nb_bits: int, nombres: list) -> str:
    """Renvoie la somme des nombres donnés sur nb_bits,
    le débordement est jeté.

    >>> nombres = ["1010", "1111", "1001"]
    >>> somme_binaire(4, nombres)
    '0010'

    >>> nombres = ["001", "001", "100"]
    >>> somme_binaire(3, nombres)
    '110'

    """
    somme = ["0" for _ in range(nb_bits)]
    retenue = 0
    for i in range(nb_bits - 1, -1, -1):
        for nombre_en_binaire in nombres:
            if nombre_en_binaire[i] == "1":
                retenue += 1

        retenue, bit = division_par_2(retenue)

        if bit == 1:
            somme[i] = "1"
    # la retenue finale est jetée ici...
    return "".join(somme)

# Tests
import doctest
doctest.testmod()

# Entrée
nb_bits = int(input())
nb_nombres = int(input())
nombres = []
for i in range(nb_nombres):
    nombre_en_binaire = input()
    assert nb_bits == len(nombre_en_binaire), f"Erreur avec le {i}e nombre"
    nombres.append(nombre_en_binaire)

# Sortie
print(somme_binaire(nb_bits, nombres))

Version récursive⚓︎

L'idée sera de renvoyer zéro si la liste est vide, sinon de renvoyer la somme du premier avec la somme des autres.

🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2004/semifinal/addition_binaire
"""

def addition_binaire(nb_bits: int, nombre_1: str, nombre_2: str) -> str:
    """Ajoute deux nombres écrit en binaire sur nb_bits.
    Le débordement est jeté.

    >>> addition_binaire(3, "111", "101")
    '100'

    """
    somme = []
    retenue = 0
    for i in range(nb_bits - 1, -1, -1):
        # pré-condition : retenue est égale à 0 ou 1
        if nombre_1[i] == "1":
                retenue += 1
        if nombre_2[i] == "1":
                retenue += 1

        if retenue == 0:
            somme.append('0')
        elif retenue == 1:
            somme.append('1')
            retenue = 0
        elif retenue == 2:
            somme.append('0')
            retenue = 1
        elif retenue == 3:
            somme.append('1')
            retenue = 1
        else:
            assert False, "Cas impossible ; erreur curieuse"
        # post-condition : retenue est égale à 0 ou 1
    # la retenue finale est jetée ici...
    # on colle le résultat construit à l'envers
    return "".join(somme[::-1])

def somme_binaire(nb_bits: int, nombres: list) -> str:
    """Renvoie la somme des nombres donnés sur nb_bits,
    le débordement est jeté.

    >>> nombres = ["1010", "1111", "1001"]
    >>> somme_binaire(4, nombres)
    '0010'

    >>> nombres = ["001", "001", "100"]
    >>> somme_binaire(3, nombres)
    '110'

    """
    if nombres == []:
        return '0' * nb_bits
    else:
        premier = nombres[0]
        somme_autres = somme_binaire(nb_bits, nombres[1:])
        return addition_binaire(nb_bits, premier, somme_autres)


# Tests
import doctest
doctest.testmod()

# Entrée
nb_bits = int(input())
nb_nombres = int(input())
nombres = []
for i in range(nb_nombres):
    nombre_en_binaire = input()
    assert nb_bits == len(nombre_en_binaire), f"Erreur avec le {i}e nombre"
    nombres.append(nombre_en_binaire)

# Sortie
print(somme_binaire(nb_bits, nombres))

Cette version récursive est bien plus simple pour de nombreuses raisons, mais elle est un peu moins efficace.