[Débutant] Exercice sur les nombres en précision arbitraire
Bonjour,
Je ne comprend pas comment résoudre l'exercice 2.1.4 du livre introduction to algorithms de Cormen :
Citation:
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 :
Citation:
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:
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 ;)
