Но даже гуголплекс – это маленькое число, если сравнить его с числом X из головоломки Microsoft. Корпорация Intel еще не изготовила достаточно микропроцессоров, чтобы рассчитать значение X. Даже если закон Мура будет выполняться до конца времен и каждые пять лет будут появляться новые суперпентиумы и вы заполните всю вселенную этими процессорами, вы все равно не сможете рассчитать невообразимо огромное значение X.
Тот факт, что интервьюер просит вас рассчитать точное количественное значение выражения, в котором таких X множество, должно подсказать вам, что здесь есть какой-то трюк.
Правильный ответ – ноль. Среди 26 сомножителей должен быть один со значением (X–X) – а это, конечно, ноль. Неважно, чему равны все остальные сомножители – что бы вы ни умножили на ноль, результатом все равно будет ноль.
У таких вопросов с подвохом может быть разная форма. Этот похож на детские картинки-загадки, на которых нужно отыскать спрятавшихся мальчиков или кошку. Нет общего правила поиска трюка – подобно кошке на загадочной картинке, трюк может быть спрятан где угодно. То, насколько быстро вы обнаружите трюк, зависит от того, на что вы обратите внимание в первую очередь, во вторую и третью. Ключевой множитель (X–X), естественно, «спрятан» там, где интервьюеры Microsoft ставят многоточие в выражении, которое нужно вычислить по условиям задачи.
Резонно проверить, умеет ли кандидат на работу сначала оценить всю ситуацию в целом, прежде чем тратить время и энергию на какое-то занятие, которое может оказаться бессмысленным. Но для многих людей «ситуация в целом» в первую очередь характеризуется тем, что им нужно пройти трудное интервью, во время которого любые сомнения и колебания могут снизить их шансы на успех. Даже если в нормальной ситуации эти люди склонны сначала проанализировать проблему, а уже потом заниматься вычислениями, и даже если они подозревают, что задача может быть с подвохом, в стрессовой ситуации они начинают заниматься алгебраическими вычислениями, то есть привычно двигаются «слева направо». Они могут идти по этому неверному пути некоторое время и только потом найти простое решение.
? Разработайте систему счисления с основанием минус 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)0).
С двойкой сложнее. Вторая позиция, считая справа налево, – это –2. Это значит, что 10 (в минус двоичной системе) будет 1 × (–2)1 + 0 × (–2)0 = –2 + 0, или –2.
Попробуйте 111. Это 1 × (–2)2 + 1 × (–2)1 + 1 × (–2)0 = 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), и вы запишете шестерку в минус двоичной системе.
