Найти умного. Как проверить логическое мышление и творческие способности кандидата - Уильям Паундстоун

? Разработайте систему счисления с основанием минус 2.

Эта глупая просьба долго использовалась в интервью, проводившихся в компании Microsoft. На самом деле нет никакого «минус двоичного» счисления. Это все равно, что попросить кого-нибудь написать несколько предложений на языке Клингонов – фантастической инопланетной расы из сериала Star Track.

Тем не менее можно изобрести логичную и последовательную систему счисления с основанием минус 2. Это как раз то, что от вас ожидается.

Мы пользуемся системой счисления с основанием 10. Это значит, что, когда мы записываем числа, мы представляем их как степени числа 10. Например, 176 – это 1 × 102 + 7 × 101 + 6 × 100. (Существует договоренность, что любое число в степени 0 равно 1.) Еще одна важная особенность десятичной системы счисления – это то, что в ней используется десять цифр (0, 1, 2, 3, 4, 5, 6, 7, 8 и 9).

Компьютеры используют систему счисления с основанием 2, или двоичную. В ней используются только две цифры (0 и 1). В многозначном числе (таком, как 10 010) каждый знак или позиция обозначает последовательные степени числа два – 1, 2, 4, 8, 16, 32… Двоичное число, например 10 010, означает 1 × 24 + 0 × 23 + 0 × 22 + 1 × 21 + 0 × 20. В обычной, десятичной системе счисления оно равно 18.

В общем, система счисления с любым основанием похожа на систему строительных блоков разных размеров. В десятичной системе размеры этих блоков 1, 10, 100, 1000 и т. д. В двоичной системе размеры блоков – 1, 2, 4, 8, 16 и т. д. Используя комбинации этих «блоков», можно получить любое нужное число.

Итак, какими будут обозначения в системе счисления с основанием минус 2?

Очевидно, что в этой системе счисления числа должны выражаться как суммы степеней числа –2. Последовательность степеней числа –2: –2, 4, –8, 16, –32…

Она отличается тем, что нечетные степени оказываются отрицательными (–2 × –2 = +4, но –2 × –2 × –2 = –8). Таким образом, вам нужно выразить числа как сумму этих положительных и отрицательных степеней.

Вы можете усомниться, можно ли этого добиться для любого числа? Да, можно. Вы можете таким способом записать любые положительные и отрицательные числа (при этом вам не понадобятся знаки плюс и минус, которыми вы обозначаете, положительное это число или отрицательное в десятичной системе). В целом для того, чтобы отобразить число в системе счисления с основанием минус 2, нужно больше разрядов, чем в обычной двоичной системе.

Перед тем как мы начнем считать, нужно решить еще одну проблему. Какие цифры мы станем использовать в минус двоичной системе? 2? 0 и 1? 0 и –1? Или нечто совершенно другое?

В системах с нормальным основанием количество цифр равно основанию. В десятичной системе десять цифр, в двоичной – только две цифры.

Если бы вы стали буквально следовать этому правилу, то пришли бы к заключению, что в минус-двоичной системе должно быть минус две цифры – это даже меньше, чем вообще ни одной цифры.

Правила создаются для того, чтобы их нарушать, и все же есть изящные нарушения правил и неряшливые нарушения. Вам нужно сохранить «дух» позиционной системы счисления и перенести его на «инопланетную» почву отрицательных чисел. Правило, что количество цифр равно основанию, неприменимо для систем счисления с негативным основанием.

Наиболее очевидное решение использовать цифры 0 и 1. Это те же цифры, которые используются в обычной двоичной системе счисления. Альтернативное решение, возможно, более соответствующее духу минус двоичной системы счисления, – использовать цифры 0 и –1, причем последняя цифра должна восприниматься как единый символ. Хотя это несколько трудно и тяжеловесно. Остановимся на более простом варианте с цифрами 0 и 1.

Единицу можно просто записать как 1 (это значит 1 × (–2)⁰).

С двойкой сложнее. Вторая позиция, считая справа налево, – это –2. Это значит, что 10 (в минус двоичной системе) будет 1 × (–2)¹ + 0 × (–2)⁰ = –2 + 0, или –2.

Попробуйте 111. Это 1 × (–2)² + 1 × (–2)¹ + 1 × (–2)⁰ = 4 + (–2) + 1 = 3. Теперь замените единицу на ноль в первой справа позиции: 110 = 4 + (–2) + 0 = 2. Итак, вот что мы должны написать в минус двоичной системе для того, чтобы получилась двойка, – 110.

И мы только что выяснили, что тройка в минус двоичной системе – 111.

С четверкой все просто. Третья позиция – это 4, как и в обычной двоичной системе. Четыре записывается как 100.

Если вы поставите единицу в крайней справа позиции, то получится пятерка в минус двоичной системе, или 101.

Для того чтобы получилось шесть, не стоит ставить 1 во второй или четвертой позициях справа, так это дает негативные числа (соответственно –2 и –8). Вам нужно перепрыгнуть на пятую позицию, единица в которой обозначает +16. Таким образом, 10 000 – это 16. Это слишком много, но 11 000 – это 16 + (–8) = 8. Отнимите от этого числа двойку – для этого нужно поставить 1 во второй справа позиции (11 010), и вы запишете шестерку в минус двоичной системе.

Семерка получается, если добавить 1 в крайней правой позиции (11 011).

Мы уже раньше узнали, что 11 000 – это восемь.

Добавьте единицу в первой справа позиции – получите девять (11 001).

С десяткой придется повозиться. Начните с восьмерки (11 000). Добавьте к этому числу четыре, поставив 1 в третьей позиции (11 100). Теперь вычтите два, поставив 1 во второй позиции (11 110). Это и есть десять.

Итак, первые десять чисел в позиционной системе счисления с основанием минус 2 – это: 1, 110, 111, 100, 101, 11 010, 11 011, 11 000, 11 001 и 11 110.