LINUX.ORG.RU

[Кормен] Условие задачи


0

1

Доброго времени суток! Помогите разобраться в условии задачи 2.1-4 из книги Кормена «Introduction to Algorithms».

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 pseudo-code for adding the two integers.
Правильно ли понял, что на вход подаются два массива A и B n-размером (например, A=[1,0,1,0] и B=[0,1,1,1]). А массив C должен содержать сумму элементов этих двух массивов, также в двоичном виде. Только вот почему у C размер массива n+1? Это из-за того, что при суммировании элементов 1+1=10?

Нашел ссылку по данной задаче, но опять же не догоняю его псевдокод :(

По сути правильно всё поняли вы.

eliriand ★★
()

На сколько я понял, есть два n-битных с числа, записанных в бинарном виде. Каждый битик - это один элемент массива. Вот и получается два массива размерности n. Cумма двух n-битных чисел, очевидно, будет либо n-битное число, либо (n+1)-битное число. Если именно это неочевидно, то могу попробовать объяснить

kulti ★★
()

но опять же не догоняю его псевдокод

Обычное сложение в столбик, ничего сложного.

provaton ★★★★★
()

Замечательный код на питона по ссылке приведен, псевдокод поможет расшифровать он.

baverman ★★★
()

Йода-стиль в комментариях здешних присутствует. одобрение силы (и Forth'а) чувствую я

jtootf ★★★★★
()

при суммировании один бит может добавляться (перенос по научному).

б+б = б*2 = б<<1, если б - самое большое н-битное число, то после сдвига оно будет н+1 битное. например 11+11 = 110 или 111+111= 1110 и т.д.

mi_estas
()

[offtopic] Не проще взять русскую версию книги? (она есть, а у первого издания ее аж 2).

Deleted
()

Это из-за того, что при суммировании элементов 1+1=10

Переносом зовется сие

Sectoid ★★★★★
()
Ответ на: комментарий от baverman

> Замечательный код на питона

/0

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.