Волшебное использование двоичного кода в обучении алгоритмам

алгоритм

Есть шутка, что в мире есть 10 типов людей, один может понять бинарность, а другой нет. Если вы поняли шутку, эта статья для вас

Single Number

Есть такой вопрос по литкоду,Single Number, проблема в том, что вы хотите найти единственное число в массиве, где есть только одно число, а все остальные числа встречаются дважды. Эта задача очень проста, мы можем использовать хеш-таблицу, чтобы записать количество раз всех чисел, а затем найти число с количеством раз 1. Если вы используете двоичный код для решения этой проблемы, эффективность будет намного быстрее.

Бинарное решение

В двоичном коде есть оператор, называемый битовым XOR, его функция заключается в том, что если две цифры одинаковы, это будет 0, а если они разные, это будет 1, то есть 1 ^ 1 = 0, 0 ^ 0 =0, 1^0=1, 0^1=1;

Благодаря характеристикам этого оператора мы можем знать, что если любое число подвергнуто XOR самому себе, полученный результат будет 00000000, а XOR 00000000 с любым числом будет тем же самым числом. И A ^ B ^ C = C ^ B ^ A этот оператор коммутативен. Давайте рассмотрим простое решение на js:


/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    return nums.reduce((res, cur) => res ^ cur);
};

проблема с ядом

Есть 8 одинаковых бутылок, из них 7 с обычной водой и одна с ядом. Любое существо, которое выпьет яд, умрет через неделю. Итак, у вас есть только 3 мыши и неделя, как узнать, в какой бутылке яд?

Решения

Мы используем двоичный код для нумерации каждой бутылки с водой, числа 000, 001, 010, 011, 100, 101, 110, 111, которые соответствуют бутылкам 1-8 соответственно, а затем пусть первая мышь выпьет первую бутылку 1 , а вторая мышь пьет вторую 1, Третья мышь пьет третью 1, предполагая, что четвертая бутылка воды ядовита, то есть 011 ядовита

  • Первые мыши выпили 100 101 110 111 результат: живы, обозначены 0
  • Вторая мышь выпила 010, 011, 110, 111, и результат: мертв, записан как 1.
  • Третья крыса выпила 001, 011, 101, 111, и результат: мертв, записан как 1.

Судя по результату смерти, это четвертая бутылка воды 011. Это просто совпадение? Боюсь, что нет. Мы можем использовать математическое мышление, чтобы доказать эту проблему.

Доказывать

У каждой крысы будет только два случая смерти или бессмертия после употребления яда.Одна крыса может проверить, являются ли два флакона с лекарством ядовитыми, то есть 2^1, две крысы могут проверить 2^2 флаконов с лекарством, а три крысы могут проверить 2 ^ 3 флакона с лекарством, так как мне проверить лекарство?

  • Мы даем каждой крысе выпить все лекарства, первая цифра которых равна 1. Если крыса умирает, это означает, что определенная цифра яда равна 1. Например, первая крыса выпила все яды, первая цифра которых была 1, и умерла. это значит, что первая цифра яда 1. Если он не умер, значит, цифра яда 0.
  • Здесь, если ни одна из трех мышей не умерла, это означает, что все три числа яда равны 0, что является первой бутылкой, которую три мыши не выпили.

Расширьте проблему

Есть 1000 точных той же бутылок, в том числе 999 бутылок обычной воды, бутылка яда. Любое существо, которое выпьет яд, умрет через неделю. Теперь есть всего 10 маленьких мышей и неделя, как вы проверяете, какая бутылка токсична?

Согласно приведенному выше вопросу, мы можем узнать, что 2 ^ 10 = 1024 > 1000, и мы также можем проверить, какая бутылка ядовита, путем двоичной нумерации каждой бутылки.

эскалация проблемы

Теперь приходят интересные вопросы: если у вас есть две недели, чтобы найти яд от 1000 бутылок, вам нужны несколько мышей по крайней мере? Обратите внимание, что мыши, которые умирают в первом раунде экспериментов, не могут продолжать участвовать во втором эксперименте.

Расширение идей проблем

27 мячей. Один из шаров немного тяжелее остальных. Вам даются весы, взвешивайте до 3 раз и находите этот особенный шарик.

идеи

Эта проблема также должна быть решена с использованием тернарной идеи.Каждый раз, когда мы говорим, что могут быть три состояния, тяжелые слева, тяжелые справа и одинаковые веса, 3 ^ 3 равно ровно 27, поэтому мы можем найдите этот маленький в 3 раза шарик.

как взвесить

Сначала дайте каждому шару номер 000 001 002 010, ..., 222.

  • В первый раз назвать все шары у которых первая позиция 2 и чья первая позиция 1, их тоже 9, какая сторона тяжелее, какое первое число у более тяжелого шара, и если это одинаковый вес, то сказать сначала имя 0
  • Во второй раз назовите все шары у которых вторая позиция 2 и чья вторая позиция 1. Их тоже 9. Какая сторона тяжелее укажет вторую позицию более тяжелого шара.Если они одного веса То вторая цифра имени 0
  • В третьем говорится, что третий равен 2 и третий бит всех маленьких шариков, их тоже 9, с какой стороны описание веса, более тяжелые шарики несколько, если такие же тяжелые, то третий равен 0

Суммировать

Категории