Discussion :

[LeFredd]

Bonjour,

Je ne comprend pas comment résoudre l'exercice 2.1.4 du livre introduction to algorithms de Cormen :

2.1-4
Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an (n+1) element array C . State the problem formally and write pseudocode for adding the two integers.

Déjà je ne comprend pas pourquoi le tableau C doit faire n + 1 element.

Ensuite j'ai trouvé cette solution mais qui ne m'éclaire pas du tout :

Input: An array of booleans A=⟨a1,a2,…,an⟩, an array of booleans B=⟨b1,b2,…,bn⟩, each representing an integer stored in binary format (each digit is a number, either 0 or 1, least-significant digit first) and each of length n.

Output: An array C=⟨c1,c2,…,cn+1⟩ that such that C′=A′+B′, where A′, B′ and C′ are the integers, represented by A, B and C

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
ADD-BINARY(A, B):
C = new integer[A.length + 1]
 
carry = 0
  for i = 1 to A.length
      C[i] = (A[i] + B[i] + carry) % 2  // remainder
      carry = (A[i] + B[i] + carry) / 2 // quotient
  C[i] = carry
 
return C

Je ne comprend pas pourquoi il se base sur la longueur du tableau A, car si A = 101 et B = 1001101 son code n'est pas bon. Dans l'énoncé il est juste spécifié que chacun de ces tableaux comporte n éléments et pas les 2 tableaux doivent comporter le même nombre d'éléments.

Si quelqu'un aurai la gentillesse de m'expliquer

[yahiko]

Exercice utile pour comprendre la représentation des nombres dans un ordinateur et pour implémenter les calculs en précision arbitraire.

[dourouc05]

Déjà je ne comprend pas pourquoi le tableau C doit faire n + 1 element.

Réfléchis déjà en base 10 : la somme de deux nombres à un chiffre donne un nombre au plus à deux chiffres. Le pire cas : 9 + 9 = 18. Même chose en binaire : 1 + 1 = 10. Conclusion : la déclaration du tableau de bits de la solution que tu as trouvée est fausse, à moins d'ajouter l'hypothèse que A est le plus grand des deux nombres en entrée.

[Flodelarab]

Bonjour,

car si A = 101

A ne sera pas égal à cela car A est un tableau de taille n. Il représente le nombre A'. Si tu tiens absolument à utiliser A plutôt que A' alors A=0000101 et B=1001101 et du coup, plus de problème de taille de tableau.

[LeFredd]

Merci pour votre aide mais C a n + 1 élément ne me parle qu'à moitié.

Flodelarab

A ne sera pas égal à cela car A est un tableau de taille n. Il représente le nombre A'

oui je voulais dire A = [1, 0, 1]

Maintenant je ne fais que suivre l'exercice et il faut que j'additionne ces 2 tableaux A et B. Je suis tout a fais d'accord pour avoir un tableau A qui soit A = [0, 0, 0, 1, 0, 1] pour avoir la même longueur que B

Voici ma compréhension du problème :

-Il faut additionner deux entiers en représentation binaire qui sont stockés sur n bits.

un entier A' stocké sur n bits = 110
un entier B' stocké sur n bits = 101100

-Ils sont rangés dans deux tableaux A et B à n éléments.

A = [1, 1, 0]
B = [1, 0, 1, 1, 0, 0]

-La somme des deux entiers doit être stockée sous forme binaire dans un tableau C à n + 1 éléments.

A' + B' = C'

110 + 101100 = 110010

C' = 110010

C = [n, n, … n+1 ]

donc :

C = [1, 1, 0, 0, 1, 0, ?] // ? = n+1

Par contre je ne vois pas du tout comment faire pour l'algorithme
Déjà comment faire pour stocker mes 2 entiers dans des tableaux tout en n'oubliant pas de mettre des 0 dans les premières cases de A pour rattraper la longueur de B ?

Des pistes ? Merci

[Flodelarab]

Tu as l'air fâché avec lez zéros inutiles. Quand, à gauche de l'écriture de ton nombre, tu ne sais pas quoi mettre, tu peux toujours mettre un zéro. Que ce soit dans A ou C.

Après, la réponse de dourouc05 est excellente. Tu sembles oublier la retenue. 9+9=18. 1111₂ + 1111₂ = 11110₂. Il y a plus de chiffres dans les sommes que dans les termes.

[LeFredd]

Non je ne suis pas faché avec les 0 en plus

C'est juste que si on imagine une fonction qui prendrait en argument 2 tableaux A et B de longueur n, on peut imaginer qu'on récupère ces 2 tableau d'un système tiers, et que ces 2 tableaux à la base n'aient pas la même longueur n. Donc comme dans mon exemple :

A = [1, 1, 0]
B = [1, 0, 1, 1, 0, 0]

Maintenant moi en tant que programmeur, pour les additionner et mettre le résultat dans un tableau C sous la même forme (un bit par case), il faudrait que mes 2 tableaux est la même longueur donc effectivement en rajoutant des 0 (ici au tableau A: A = [0, 0, 0, 1, 1, 0])

Mais déjà comment faire ça en algo ?

Et pour ce fameux tableau C pourquoi avoir besoin de préciser n + 1 ? On s'en fiche, les additions des cases des 2 tableaux viendront nourrir le tableau C donc sa taille c'est pas grave de ne pas la connaitre au départ, et pour les retenues : une variable qui les retienne et qu'on ajoute à la prochaine addition.

Maintenant c'est pour mettre tous ça en algo, je ne vois pas trop par ou commencer ni comment m'y prendre, je suis débutant.