Проверить, делится ли число на 3 [закрыто]

https://stackoverflow.com/questions/844867

20-08-2019
|

Вопрос

Напишите код, определяющий, делится ли число на 3.Входные данные функции представляют собой одинокий бит, 0 или 1, а выход должен быть 1, если полученное число является двоичным представлением числа, делящегося на 3, в противном случае - ноль.

Примеры:

input  "0":       (0)  output 1
inputs "1,0,0":   (4)  output 0
inputs "1,1,0,0": (6)  output 1

Это основано на вопросе собеседования.Я прошу рисунок логических элементов, но, поскольку это stackoverflow, я приму любой язык кодирования.Бонусные баллы за аппаратную реализацию (verilog и т. д.).

Часть А (простая): Первый вход — старший бит.

Часть Б (немного сложнее): Первый вход — младший бит.

Часть в (сложная): Какой из них быстрее и меньше: (а) или (б)?(Не теоретически в смысле Big-O, а практически быстрее/меньше.) Теперь возьмите более медленный/большой и сделайте его таким же быстрым/маленьким, как более быстрый/меньший.

Решение

Хех

Таблица состояний для LSB:

Объяснение:0 делится на три. 0 << 1 + 0 = 0.Повторите, используя S = (S << 1 + I) % 3 и O = 1 если S == 0.

Таблица состояний для MSB:

Объяснение:0 делится на три. 0 >> 1 + 0 = 0.Повторите, используя S = (S >> 1 + I) % 3 и O = 1 если S == 0.

S' отличается от приведенного выше, но O работает так же, поскольку S' равно 0 для тех же случаев (00 и 11).Поскольку O одинаково в обоих случаях, O_LSB = O_MSB, поэтому, чтобы сделать MSB таким же коротким, как LSB, или наоборот, просто используйте самый короткий из обоих.

Другие советы

Существует довольно известный прием, позволяющий определить, кратно ли число 11, путем поочередного сложения и вычитания его десятичных цифр.Если число, которое вы получите в конце, кратно 11, то число, с которого вы начали, также кратно 11:

47278    4 - 7 + 2 - 7 + 8 = 0, multiple of 11     (47278 = 11 * 4298)
52214    5 - 2 + 2 - 1 + 4 = 8, not multiple of 11 (52214 = 11 * 4746 + 8)

Мы можем применить тот же трюк к двоичным числам.Двоичное число кратно 3 тогда и только тогда, когда попеременная сумма его бит также кратна 3:

4   = 100       1 - 0 + 0 = 1, not multiple of 3
6   = 110       1 - 1 + 0 = 0, multiple of 3
78  = 1001110   1 - 0 + 0 - 1 + 1 - 1 + 0 = 0, multiple of 3
109 = 1101101   1 - 1 + 0 - 1 + 1 - 0 + 1 = 1, not multiple of 3

Не имеет значения, начинаете ли вы со старшего или младшего бита, поэтому следующая функция Python работает одинаково хорошо в обоих случаях.Требуется итератор, который возвращает биты по одному. multiplier чередуется между 1 и 2 вместо 1 и -1, чтобы избежать вычисления по модулю отрицательного числа.

def divisibleBy3(iterator):

    multiplier = 1
    accumulator = 0

    for bit in iterator:
        accumulator = (accumulator + bit * multiplier) % 3
        multiplier = 3 - multiplier

    return accumulator == 0

Здесь...что-то новое...как проверить, делится ли двоичное число любой длины (даже тысячи цифр) на 3.

-->((0))<---1--->()<---0--->(1)        ASCII representation of graph

С картинки.

Вы начинаете с двойного круга.
Когда вы получаете единицу или ноль, если цифра находится внутри круга, вы остаетесь в этом круге.Однако если цифра находится на линии, вы пересекаете ее.
Повторяйте второй шаг, пока не будут использованы все цифры.
Если вы в конце концов окажетесь в двойном круге, значит, двоичное число делится на 3.

Вы также можете использовать это для генерации чисел, делящихся на 3.И я бы не подумал, что будет сложно преобразовать это в схему.

1 пример с использованием графика...

11000000000001011111111111101 делится на 3 (снова оказывается в двойном круге)

Попробуйте сами.

Вы также можете проделать аналогичные трюки для выполнения MOD 10 при преобразовании двоичных чисел в числа с основанием 10.(10 кружков, каждый из которых обведен вдвое и представляет значения от 0 до 9, полученные по модулю)

РЕДАКТИРОВАТЬ: Это для цифр, идущих слева направо, однако нетрудно модифицировать конечный автомат, чтобы он принимал обратный язык.

ПРИМЕЧАНИЕ: В представлении ASCII графика () обозначает одинарный круг, а (()) обозначает двойной круг.В конечных автоматах они называются состояниями, а двойной круг — это состояние принятия (состояние, которое означает, что оно в конечном итоге делится на 3).

Вот простой способ сделать это вручную.Поскольку 1 = 2² по модулю 3, получаем 1 = 2^2н mod 3 для каждого положительного целого числа.Кроме того, 2 = 2²ⁿ⁺¹ мод 3.Следовательно, можно определить, делится ли целое число на 3, подсчитав 1 бит в нечетных битовых позициях, умножив это число на 2, добавив количество 1-битных в четных битовых позициях, добавив их к результату и проверив, делится ли результат. на 3.

Пример:57₁₀=111001₂.Есть 2 бита в нечетных позициях и 2 бита в четных позициях.2*2+2=6 делится на 3.Следовательно, 57 делится на 3.

Вот еще мысль по поводу решения вопроса в).Если инвертировать порядок битов двоичного целого числа, то все биты останутся в четных/нечетных позициях или все биты изменяются.Следовательно, инвертирование порядка бит целого числа n приводит к тому, что целое число делится на 3 тогда и только тогда, когда n делится на 3.Следовательно, любое решение вопроса а) работает без изменений для вопроса б) и наоборот.Хм, возможно, это поможет выяснить, какой подход быстрее...

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

MSB:

number=0
while(!eof)
    n=input()
    number=(number *2 + n) mod 3

if(number == 0)
    print divisible

младший бит:

number = 0;
multiplier = 1;
while(!eof)
    n=input()
    number = (number + multiplier * n) mod 3
    multiplier = (multiplier * 2) mod 3

if(number == 0)
   print divisible

Это общая идея...

Теперь ваша задача — понять почему это верно.

И да, делайте домашнее задание сами ;)

Идея состоит в том, что число может расти сколь угодно долго, а это значит, что вы не можете использовать mod 3 здесь, поскольку ваше число выйдет за пределы емкости вашего целочисленного класса.

Идея состоит в том, чтобы заметить, что происходит с числом.Если вы добавляете биты вправо, на самом деле вы сдвигаете один бит влево и добавляете новый бит.

Сдвиг влево — это то же самое, что умножение на 2, а добавление нового бита — это либо 0, либо 1.Предполагая, что мы начали с 0, мы можем сделать это рекурсивно, основываясь на модуле 3 последнего числа.

last | input || next | example
------------------------------------
0    | 0     || 0    | 0 * 2 + 0 = 0
0    | 1     || 1    | 0 * 2 + 1 = 1
1    | 0     || 2    | 1 * 2 + 0 = 2
1    | 1     || 0    | 1 * 2 + 1 = 0 (= 3 mod 3)
2    | 0     || 1    | 2 * 2 + 0 = 1 (= 4 mod 3)
2    | 1     || 2    | 2 * 2 + 1 = 2 (= 5 mod 3)

Теперь давайте посмотрим, что произойдет, если вы добавите немного влево.Во-первых, обратите внимание на следующее:

2^2н мод 3 = 1

2²ⁿ⁺¹ мод 3 = 2

Итак, теперь нам нужно либо добавить 1, либо 2 к моду в зависимости от того, является ли текущая итерация нечетной или четной.

last | n is even? | input || next | example
-------------------------------------------
d/c  | don't care | 0     || last | last + 0*2^n = last
0    | yes        | 1     || 0    | 0 + 1*2^n = 1 (= 2^n mod 3)
0    | no         | 1     || 0    | 0 + 1*2^n = 2 (= 2^n mod 3)
1    | yes        | 1     || 0    | 1 + 1*2^n = 2
1    | no         | 1     || 0    | 1 + 1*2^n = 0 (= 3 mod 3)
1    | yes        | 1     || 0    | 2 + 1*2^n = 0
1    | no         | 1     || 0    | 2 + 1*2^n = 1

input  "0":       (0)  output 1
inputs "1,0,0":   (4)  output 0
inputs "1,1,0,0": (6)  output 1

не должен ли этот последний ввод быть 12, или я неправильно понял вопрос?

На самом деле метод LSB действительно облегчит эту задачу.В С:

Метод MSB:

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_msb(char *input) {
  unsigned value = 0;
  char *p = input;
  if (*p == '1') {
    value &= 1;
  }
  p++;
  while (*p) {
    if (*p != ',') {
      value <<= 1;
      if (*p == '1') {
        ret &= 1;
      }
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

Метод LSB:

/* 
Returns 1 if divisble by 3, otherwise 0
Note: It is assumed 'input' format is valid
*/
int is_divisible_by_3_lsb(char *input) {
  unsigned value = 0;
  unsigned mask = 1;
  char *p = input;
  while (*p) {
    if (*p != ',') {
      if (*p == '1') {
        value &= mask;
      }
      mask <<= 1;
    }
    p++;
  }
  return (value % 3 == 0) ? 1 : 0;
}

Лично мне трудно поверить, что один из них будет существенно отличаться от другого.

Я думаю, что Натан Феллман на правильном пути для частей a и b (за исключением того, что b требует дополнительного фрагмента состояния:вам нужно следить за тем, является ли ваша цифра нечетной или четной).

я думать трюк для части C заключается в отрицании last значение на каждом этапе.Т.е.0 переходит в 0, 1 переходит в 2 и 2 переходит в 1.

Число делится на 3, если сумма его цифр делится на 3.

Таким образом, вы можете сложить цифры и получить сумму:

если сумма больше или равна 10, используйте тот же метод
если это 3,6,9 то оно делится
если сумма отличается от 3, 6, 9, то она не делится

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow