Напишите метод, находящий максимальное из двух чисел, не используя операторы if-else или любые другие операторы сравнения




Самый распространенный вариант реализации функции max — проверка знака выражения a - b. В этом случае мы не можем использовать оператор сравнения, но можем использовать умножение.

Обозначим знак выражения a - b как k. Если a - b >= 0, то k = 1, иначе k = 0. Пусть q будет инвертированным значением k.

Код будет иметь вид:

/* Отражаем 1 в 0 и 0 в 1 */

int flip(int bit) {

return 1^bit;

}

 

/* Возвращаем 1, если число положительное, и 0, если отрицательное*/

int sign(int a) {

return flip((a >> 31) & 0x1);

}

 

int getMaxNaive(int a, int b) {

int k = sign(a - b);

int q = flip(k);

return a * k + b * q;

}

Это почти работоспособный код (можете проверить). Проблемы начинаются при переполнении. Предположим, что a = INT_MAX - 2 и b = -15. В этом случае a - b перестанет помещаться в INT_MAX и вызовет переполнение (значение станет отрицательным).

Можно использовать тот же подход, но придумать другую реализацию. Нам нужно, чтобы выполнялось условие k = 1, когда a > b. Для этого придется использовать более сложную логику.

Когда возникает переполнение a - b? Только тогда, когда a положительное число, а b отрицательное (или наоборот). Трудно обнаружить факт переполнения, но мы в состоянии понять, что a и b имеют разные знаки. Если у а и b разные знаки, то пусть k = sign(a).

Логика будет следующей:

  1. если у a и b разные знаки:
  2. // если a > 0, то b < 0 и k = 1.
  3. // если a < 0, то b > 0 и k = 0.
  4. // так или иначе, k = sign(a)
  5. пусть k = sign(a)
  6. иначе
  7. пусть k = sign(a - b) // переполнение невозможно

Приведенный далее код реализует этот алгоритм, используя умножение вместо операторов сравнения (проверить):

int getMax(int a, int b) {

int c = a - b;

 

int sa = sign(a); // если a >= 0, то 1, иначе 0

int sb = sign(b); // если a >= 1, то 1, иначе 0

int sc = sign(c); // зависит от переполнения a - b

 

/* Цель: найти k, которое = 1, если а > b, и 0, если a < b.

* если a = b, k не имеет значения */

 

// Если у а и b равные знаки, то k = sign(a)

int use_sign_of_a = sa ^ sb;

 

// Если у a и b одинаковый знак, то k = sign(a - b)

int use_sign_of_c = flip(sa ^ sb);

 

int k = use_sign_of_a * sa + use_sign_of_c * sc;

int q = flip(k); // отражение к

 

return a * k + b * q;

}

Отметим, что для большей наглядности мы разделяем код на методы и вводим переменные. Это не самый компактный или эффективный способ написания кода, но так мы делаем код понятнее.

Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).

6. Вероятность встретить машину на пустынном шоссе

На пустынном шоссе вероятность появления автомобиля за 30-минутный период составляет 0.95. Какова вероятность его появления за 10 минут?

Это вопрос труден только потому, что та информация, которую вы получили, не является той, которую вы хотели бы иметь. Однако в реальной жизни такое часто встречается.

Вы хотели бы определить вероятность, относящуюся к 10 минутам, имея вероятность для 30 минут. Вы не можете поступить просто, то есть разделить 0.95 на три (хотя надо сказать, что некоторые пытаются это сделать). Не очень помогает знание вероятности того, то автомобиль проедет в течение 30 минут, поскольку это может случиться в любое время. Автомобиль может проехать в первый 10-минутный отрезок или во второй, или в третий. За каждый из этих периодов могут проехать два автомобиля или пять, или тысяча, но это все считается как проезд автомобиля.

То, что вы хотели бы на самом деле знать, — это вероятность того, что за 30-минутный период не проедет ни один автомобиль. Узнать ее довольно просто. Поскольку имеется шанс, равный 95%, что за 30 минут проедет по крайней мере один автомобиль, то вероятность того, что в течение этого временного промежутка не будет ни одной машины, должна быть равна 0.05.

Чтобы в течение 30-минутного отрезка не было ни одного автомобиля, должны случиться (или, наоборот, не случиться) три вещи. Во-первых, в течение 10 минут не должно быть ни одного автомобиля. Затем должно пройти еще 10 минут без всяких машин. И, наконец, третьи 10 минут также должны быть без автомобилей. В вопросе спрашивается вероятность появления автомобиля в течение 10-минутного периода. Назовем ее X. Вероятность отсутствия машин в эти 10 минут равна 1 - X. Умножим эту величину саму на себя три раза. Она должна быть равна 0.05, то есть

(1 - X)³ = 0.05

Извлечем кубический корень из обеих частей.

1 - X = ³Ѵ0.05

Решим это уравнение относительно X.

X = 1 - ³Ѵ0.05

Никто не ожидает, что вы можете в уме извлекать кубические корни. Компьютер вам подскажет, что ответ равен около 0.63. Такой результат вполне обоснован. Вероятность появления автомобиля в 10-минутный период должна быть меньше, чем вероятность его появления, равная 0.95, за 30-минутный период.

Разбор взят из книжки «Are You Smart Enough to Work at Google?».

7. Напишите функцию суммирования двух целых чисел без использования «+» и других арифметических операторов

Первое, что приходит в голову, — обработка битов. Почему? У нас нет выбора — нельзя использовать оператор «+». Так что будем суммировать числа так, как это делают компьютеры!

Теперь нужно разобраться, как работает суммирование. Дополнительные задачи позволяют нам выработать новые навыки, узнать что-нибудь интересное, создать новые шаблоны.

Так что давайте рассмотрим дополнительную задачу. Мы будем использовать десятичную систему счисления.

Чтобы просуммировать 759 + 674, я обычно складываю digit[0] обоих чисел, переношу единицу, затем перехожу к digit[1], переношу и т.д. Точно так же можно работать с битами: просуммировать все разряды и при необходимости сделать переносы единиц.

Можно ли упростить алгоритм? Да! Допустим, я хочу разделить «суммирование» и «перенос». Мне придется проделать следующее:

  1. Выполнить операцию 759 + 674, забыв о переносе. В результате получится 323.
  2. Выполнить операцию 759 + 674, но сделать только переносы (без суммирования разрядов). В результате получится 1110.
  3. Теперь нужно сложить результаты первых двух операций (используя тот же механизм, описанный в шагах 1 и 2): 1110 + 323 = 1433.

Теперь вернемся к двоичной системе.

  1. Если просуммировать пару двоичных чисел, без учета переноса знака, то i-й просуммированный бит может быть нулевым, только если i-e биты чисел a и b совпадали (оба имели значение 0 или 1). Это классическая операция XOR.
  2. Если суммировать пару чисел, выполняя только перенос, то i-му биту суммы присваивается значение 1, только если i-1-е биты обоих чисел (a и b) имели значение 1. Это операция AND со смещением.
  3. Нужно повторять эти шаги до тех пор, пока не останется переносов.

Следующий код реализует данный алгоритм.

public static int add(int a, int b) {

if (b == 0) return a;

int sum = a ^ b; // добавляем без переноса

int carry = (a & b) << 1; // перенос без суммирования

return add(sum, carry); // рекурсия

}

Задачи, связанные с реализацией базовых операций (сложение, вычитание), достаточно популярны. Чтобы решить такую задачу, нужно разобраться с тем, как обычно реализуются операции, а потом найти путь, позволяющий написать код с учетом ограничений.

Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).

8. Логическая задача на взвешивание

Дано 20 баночек с таблетками. В 19 баночках лежат таблетки весом 1 г, а в одной – весом 1.1 г. Даны весы, показывающие точный вес. Как за одно взвешивание найти банку с тяжелыми таблетками?

Решение

Иногда “хитрые” ограничения могут стать подсказкой. В нашем случае подсказка спрятана в информации о том, что весы можно использовать только один раз.

У нас только одно взвешивание, а это значит, что придется одновременно взвешивать много таблеток. Фактически, мы должны одновременно взвесить 19 банок. Если мы пропустим две (или больше) банки, то не сможем их проверить. Не забывайте: только одно взвешивание!

Как же взвесить несколько банок и понять, в какой из них находятся “дефектные” таблетки? Давайте представим, что у нас есть только две банки, в одной из них лежат более тяжелые таблетки. Если взять по одной таблетке из каждой банки и взвесить их одновременно,то общий вес будет 2.1 г, но при этом мы не узнаем, какая из банок дала дополнительные 0.1 г. Значит, надо взвешивать как-то иначе.

Если мы возьмем одну таблетку из банки №1 и две таблетки из банки №2, то, что покажут весы? Результат зависит от веса таблеток. Если банка №1 содержит более тяжелые таблетки, то вес будет 3.1 г. Если с тяжелыми таблетками банка №2 – то 3.2 грамма. Подход к решению задачи найден.

Можно обобщить наш подход: возьмем одну таблетку из банки №1, две таблетки из банки №2, три таблетки из банки №3 и т.д. Взвесьте этот набор таблеток. Если все таблетки весят 1 г, то результат составит 210 г. “Излишек” внесет банка с тяжелыми таблетками.

Таким образом, номер банки можно узнать по простой формуле: (вес – 210) / 0.1. Если суммарный вес таблеток составляет 211.3 г, то тяжелые таблетки находились в банке №13.

 

9. На подготовку актеров уйдет один час. За это время первый гример сделает макияж двум актерам (30 + 30 = 60 минут), а второй гример сделает макияж третьему актеру, и причешет всех трех актеров (10 + 30 + 10 + 10 = 60 минут).

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-11-19 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: