Логика для проверки числа делится на 3 или нет?

Question

без использования%, / или *, я должен найти нет. делится на 3 или нет?

это может быть вопрос на собеседовании.

Спасибо.

Answer 1

Есть разные способы.Самое простое довольно очевидно:

int isdivby3(int n) {
    if (n < 0) n = -n;

    while (n > 0) n -= 3;

    return n == 0;
}

Но мы можем это улучшить.Любое число может быть представлено следующим образом: ("," означает диапазон включительно):

Base2 (AKA binary)
(0,1) + 2*(0,1) + 4*(0,1)

Base4
(0,3) + 4*(0,3) + 16*(0,3)

BaseN
(0,N-1) + N*(0,N-1) + N*N*(0,N-1)

Теперь дело в том, что число x делится на n-1 тогда и только тогда, когда цифра x в базе n делится на n-1.Этот трюк хорошо известен для 9:

1926 = 6 + 2*10 + 9*100 + 1*1000
6+2+9+1 = 8 + 1*10
8+1 = 9 thus 1926 is divisible by 9

Теперь мы можем применить это к 3 тоже в base4.И нам повезло, поскольку 4 - это степень 2, мы можем выполнять двоичные побитовые операции.Я использую обозначение number(base).

27(10) = 123(4)
Digitsum
12(4)
Digitsum again
3(4) = Divisible!

Теперь давайте переведем это на C:

int div3(int n) {
    if (n < 0) n = -n;
    else if (n == 0) return 1;

    while (n > 3) {
        int d = 0;

        while (n > 0) {
            d += n & 3;
            n >>= 2;
        }

        n = d;
    }

    return n == 3;
}

Сверкающий быстро.

Answer 2

Вычитайте 3, пока вы либо

не нажмете 0 - число делится на 3 (или)

получите число меньше 0 - число не делится

Answer 3

Вот довольно эффективный алгоритм для больших чисел.(Ну, не очень эффективно, но разумно, учитывая ограничения.)

Используйте sprintf, чтобы преобразовать его в строку, преобразуйте каждую цифру обратно в число.Сложите цифры.Если вы придумали 3, 6 или 9, это делится на 3. Все, что меньше 10, это не так.Все, что больше 9, recurse.

Например, чтобы проверить число 813478902, которое вы хотите записать, затем добавьте цифры, чтобы получить 42, добавьте эти цифры, чтобы получить 6, чтобы оно делилось на 3.

Answer 4

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

Обратите внимание на последовательность подсчета:

00: 00(00)
01: 0001
02: 0010
03: 00(11)
04: 0100
05: 0101
06: 01(10)
07: 0111
08: 1000
09: 10(01)
10: 1010
11: 1011
12: 11(00)
13: 1101
14: 1110
15: 11(11)
16: 10000
17: 10001
18: 100(10)
19: 10011
20: 10100
21: 101(01)

Обратите внимание, что последние два бита тех чисел, которые делятся на три (показанные в скобках), циклически пересекают {00, 11, 10, 01}. Нам нужно проверить, есть ли последние два бита в последовательности счетчиков в последовательности.

Сначала мы начинаем сопоставление с mask = 00 и выполняем цикл, пока первое число не встречается с младшими двумя битами 00. Когда совпадение найдено, мы делаем (mask + 03) & 0x03, что дает нам следующую маску в наборе. И мы продолжаем сопоставлять последние два бита следующего счета с 11. Что можно сделать с помощью ((count & 3) == mask)

Код

#include <stdio.h>

int main (void)
{
  int i=0;
  unsigned int mask = 0x00;

  for (i=0; i<100;i++)
  {
    if ((i&0x03) == mask)
    {
      printf ("\n%d", i);
      mask = (mask + 3) & 0x03;
    }
  }
  printf ("\n");
  return 0;
}

Это не общее. Лучше всего использовать решение, которое @nightcracker предложил

Также, если вы действительно хотите реализовать операцию деления i без использования операций деления. Я бы посоветовал вам взглянуть на Невосстанавливающий алгоритм деления, это можно сделать в программе с большим количеством битовых манипуляций с побитовыми операторами. Вот несколько ссылок и ссылок на него.

Ссылка на Википедию

Вот демоверсия от UMass

Также взгляните на Компьютерная организация Карла Хамахера, Звонко Вранесича, Сафвата Заки

Answer 5

просто используйте цикл for, вычитая 3 снова и снова, и посмотрите, дойдете ли вы до 0. Если вы доберетесь до отрицательного значения, не достигнув 0, то вы знаете, что оно не делится на 3

Answer 6

Вы можете использовать обратную связь с пользователем:

int isDivisibleBy3(int n)
{
   int areDivisibleBy3[] = {};
   for(int i = 0; i < 0; i++)
   {
       if(n == areDivisibleBy3[i])
       {
           return 1;
       }
   }

   return 0;
}

Когда пользователь сообщает об ошибке, утверждающей, что число, делимое на 3, не дает правильного результата, вы просто добавляете это число в массив и увеличиваетечисло i сравнивается с условием цикла for.

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

Не забудьте добавитьмодульный тест для каждого, когда пользователь сообщает об ошибке!

Answer 7

Число делится на три, если сумма двоичных переменных цифр равна нулю:

bool by3(int n) {
  int s=0;
  for (int q=1; n; s+=q*(n&1), n>>=1, q*=-1);
  return !s;
}

Answer 8

Самый простой способ узнать, делится ли число на 3, состоит в суммировании всех его цифр и делении результата на 3. Если сумма цифр делится на 3, значит, само число делится на 3. Например, , 54467565687 делится на 3, потому что 5 + 4 + 4 + 6 + 7 + 5 + 6 + 5 + 6 + 8 + 7 = 63, а 63 делится на 3. Итак, независимо от того, насколько велико число, вы можно определить, делится ли она на 3, просто сложив все свои цифры и вычтя 3 из значения этой суммы, пока результат не станет меньше 3. Если этот результат равен 0, значение суммы делится на 3 (и т. д. исходное число), в противном случае сумма не делится на 3 (и исходное число тоже не делится). Это делается гораздо быстрее, чем последовательно вычитать 3 из исходного числа (конечно, особенно если оно большое) и без делений. Um abraço a todos.

Artur

Answer 9

Предположим, что n - это число, о котором идет речь, и оно неотрицательно.

Если n равно 0, оно делится на 3; в противном случае n = (2 ^ p) * (2 * n1 + 1) и n делится на 3, если 2 * n1 + 1 есть, если есть ak> = 0 с 2 * n1 + 1 = 3 * (2 * k +1) если n1 = 3 * k + 1, если n1 = 1 или n1> 1 и n1-1 делится на 3. Итак:

int ism3( int n)
{   for(;n;)
    {    while( !(n & 1)) n >>= 1;
         n >>= 1;
         if ( n == 0) return 0;
         n-= 1;
    }
    return 1;
 }

Answer 10

number = abs(number)

while (number > 0)
{
   number -= 3;
}

return number == 0