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

Существует довольно известный прием, позволяющий определить, кратно ли число 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

Не имеет значения, начинаете ли вы с MSB или LSB, поэтому следующая функция 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

The idea is that the number can grow arbitrarily long, which means you can't use mod 3 here, since your number will grow beyond the capacity of your integer class.

The idea is to notice what happens to the number. If you're adding bits to the right, what you're actually doing is shifting left one bit and adding the new bit.

Shift-left is the same as multiplying by 2, and adding the new bit is either adding 0 or 1. Assuming we started from 0, we can do this recursively based on the modulo-3 of the last number.

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)

Now let's see what happens when you add a bit to the left. First, notice that:

2²ⁿ mod 3 = 1

and

2²ⁿ⁺¹ mod 3 = 2

So now we have to either add 1 or 2 to the mod based on if the current iteration is odd or even.

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

You need to do all calculations using arithmetic modulo 3. This is the way

MSB:

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

if(number == 0)
    print divisible

LSB:

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

if(number == 0)
   print divisible

This is general idea...

Now, your part is to understand why this is correct.

And yes, do homework yourself ;)

Here is an simple way to do it by hand. Since 1 = 2² mod 3, we get 1 = 2²ⁿ mod 3 for every positive integer. Furthermore 2 = 2²ⁿ⁺¹ mod 3. Hence one can determine if an integer is divisible by 3 by counting the 1 bits at odd bit positions, multiply this number by 2, add the number of 1-bits at even bit posistions add them to the result and check if the result is divisible by 3.

Example: 57₁₀=111001₂. There are 2 bits at odd positions, and 2 bits at even positions. 2*2 + 2 = 6 is divisible by 3. Hence 57 is divisible by 3.

Here is also a thought towards solving question c). If one inverts the bit order of a binary integer then all the bits remain at even/odd positions or all bits change. Hence inverting the order of the bits of an integer n results is an integer that is divisible by 3 if and only if n is divisible by 3. Hence any solution for question a) works without changes for question b) and vice versa. Hmm, maybe this could help to figure out which approach is faster...

Actually the LSB method would actually make this easier. In C:

MSB method:

/* 
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 method:

/* 
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;
}

Personally I have a hard time believing one of these will be significantly different to the other.

I think Nathan Fellman is on the right track for part a and b (except b needs an extra piece of state: you need to keep track of if your digit position is odd or even).

I think the trick for part C is negating the last value at each step. I.e. 0 goes to 0, 1 goes to 2 and 2 goes to 1.

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

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

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

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

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

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

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

Из рисунка.

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

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

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

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

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

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

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

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