Мне нужно определить, делится ли число на 3 без использования %, / или *. Указанный намек заключался в использовании функции atoi(). Любая идея, как это сделать?
Проверьте, является ли число делимым на 3
Ответ 1
Вычтите 3, пока не будете
a) hit 0 - число делится на 3
b) получить число меньше 0 - число не делится
- отредактированная версия для исправления отмеченных проблем
while n > 0:
n -= 3
while n < 0:
n += 3
return n == 0
Ответ 2
В текущем ответе все сосредоточены на десятичных цифрах, применяя "добавить все цифры и посмотреть, делит ли это на 3". Этот трюк действительно работает и в шестнадцатеричном виде; например 0x12 можно разделить на 3, потому что 0x1 + 0x2 = 0x3. И "преобразование" в шестнадцатеричное намного проще, чем преобразование в десятичную.
Псевдо-код:
int reduce(int i) {
if (i > 0x10)
return reduce((i >> 4) + (i & 0x0F)); // Reduces 0x102 to 0x12 to 0x3.
else
return i; // Done.
}
bool isDiv3(int i) {
i = reduce(i);
return i==0 || i==3 || i==6 || i==9 || i==0xC || i == 0xF;
}
[править] Вдохновленный R, более быстрая версия (журнал журнала событий N):
int reduce(unsigned i) {
if (i >= 6)
return reduce((i >> 2) + (i & 0x03));
else
return i; // Done.
}
bool isDiv3(unsigned i) {
// Do a few big shifts first before recursing.
i = (i >> 16) + (i & 0xFFFF);
i = (i >> 8) + (i & 0xFF);
i = (i >> 4) + (i & 0xF);
// Because of additive overflow, it possible that i > 0x10 here. No big deal.
i = reduce(i);
return i==0 || i==3;
}
Ответ 3
Разделите число на цифры. Добавьте цифры вместе. Повторяйте, пока не останется только одна цифра. Если эта цифра равна 3, 6 или 9, число делится на 3. (И не забывайте обрабатывать 0 как частный случай).
Ответ 4
Хотя технология преобразования в строку и добавление десятичных цифр вместе является элегантной, она либо требует деления, либо неэффективна на этапе преобразования в строку. Есть ли способ применить идею непосредственно к двоичному числу без предварительной конвертации в строку десятичных цифр?
Оказывается, есть:
Учитывая двоичное число, сумма его нечетных битов минус сумма его четных битов делится на 3, если исходное число делится на 3.
В качестве примера: возьмите число 3726, которое делится на 3. В двоичном формате это 111010001110. Поэтому мы берем нечетные цифры, начиная с правого и движущегося слева, которые являются [1, 1, 0, 1, 1, 1]; их сумма 5. Четные биты - [0, 1, 0, 0, 0, 1]; их сумма 2. 5 - 2 = 3, из которого можно заключить, что исходное число делится на 3.
Ответ 5
Вопрос о интервью в основном просит вас придумать (или уже известно) сокращение правила делимости с 3 в качестве делителя.
Одно из правил делимости для 3 выглядит следующим образом:
Возьмите любое число и добавьте каждую цифру в число. Затем возьмите эту сумму и определите, делится ли она на 3 (повторяя ту же процедуру, что и требуется). Если конечное число делится на 3, то исходное число делится на 3.
Пример:
16,499,205,854,376
=> 1+6+4+9+9+2+0+5+8+5+4+3+7+6 sums to 69
=> 6 + 9 = 15 => 1 + 5 = 6, which is clearly divisible by 3.
См. также
- правило Википедии/делимости - есть много правил для многих делителей
Ответ 6
Число, делящееся на 3, iirc имеет характеристику, что сумма ее разряда делится на 3. Например,
12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9
Ответ 7
Учитывая число x. Преобразуйте x в строку. Разбор символа строки по символу. Преобразуйте каждый проанализированный символ в число (используя atoi()) и добавьте все эти числа в новое число y. Повторяйте процесс до тех пор, пока ваш конечный результирующий номер не будет иметь одну цифру. Если эта цифра равна 3,6 или 9, исходное число x делится на 3.
Ответ 8
Вы не отметили этот C, но, поскольку вы упомянули atoi, я собираюсь дать решение C:
int isdiv3(int x)
{
div_t d = div(x, 3);
return !d.rem;
}
Ответ 9
Мое решение в Java работает только для 32-разрядных неподписанных int s.
static boolean isDivisibleBy3(int n) {
int x = n;
x = (x >>> 16) + (x & 0xffff); // max 0x0001fffe
x = (x >>> 8) + (x & 0x00ff); // max 0x02fd
x = (x >>> 4) + (x & 0x000f); // max 0x003d (for 0x02ef)
x = (x >>> 4) + (x & 0x000f); // max 0x0011 (for 0x002f)
return ((011111111111 >> x) & 1) != 0;
}
Сначала он уменьшает число до числа меньше 32. Последний шаг проверяет делимость, сдвигая маску на соответствующее число раз вправо.
Ответ 10
bool isDiv3(unsigned int n)
{
unsigned int n_div_3 =
n * (unsigned int) 0xaaaaaaab;
return (n_div_3 < 0x55555556);//<=>n_div_3 <= 0x55555555
/*
because 3 * 0xaaaaaaab == 0x200000001 and
(uint32_t) 0x200000001 == 1
*/
}
bool isDiv5(unsigned int n)
{
unsigned int n_div_5 =
i * (unsigned int) 0xcccccccd;
return (n_div_5 < 0x33333334);//<=>n_div_5 <= 0x33333333
/*
because 5 * 0xcccccccd == 0x4 0000 0001 and
(uint32_t) 0x400000001 == 1
*/
}
Следуя тому же правилу, чтобы получить результат теста на делимость на 'n', мы можем: умножьте число на 0x1 0000 0000 - (1/n) * 0xFFFFFFFF сравните с (1/n) * 0xFFFFFFFF
Другим является то, что для некоторых значений тест не сможет вернуть правильный результат для всех 32-битных чисел, которые вы хотите проверить, например, с делимостью на 7:
мы получили 0x100000000- (1/n) * 0xFFFFFFFF = 0xDB6DB6DC и 7 * 0xDB6DB6DC = 0x6 0000 0004, Мы проверим только одну четверть значений, но мы можем, конечно, избежать этого с помощью подстрок.
Другие примеры:
11 * 0xE8BA2E8C = A0000 0004, одна четверть значений
17 * 0xF0F0F0F1 = 10 0000 0000 1 по сравнению с 0xF0F0F0F Все значения!
Etc., мы можем даже проверять каждое число, комбинируя натуральные числа между ними.
Ответ 11
Число делится на 3, если все цифры в числе при добавлении дают результат 3, 6 или 9. Например, 3693 делится на 3 как 3 + 6 + 9 + 3 = 21 и 2 + 1 = 3 и 3 делится на 3.
Ответ 12
inline bool divisible3(uint32_t x) //inline is not a must, because latest compilers always optimize it as inline.
{
//1431655765 = (2^32 - 1) / 3
//2863311531 = (2^32) - 1431655765
return x * 2863311531u <= 1431655765u;
}
В некоторых компиляторах это происходит быстрее, чем обычный: x % 3. Подробнее здесь.
Ответ 13
и число делится на 3, если вся сумма цифр числа делится на 3. Таким образом, вы можете получить каждую цифру как подстроку входного числа, а затем добавить их. вы затем будете повторять этот процесс до тех пор, пока не получите только один результат.
если это 3, 6 или 9, число делится на 3.
Ответ 14
Вот ваше оптимизированное решение, которое каждый знает.................
Источник: http://www.geeksforgeeks.org/archives/511
Программа:
#include<stdio.h>
int isMultiple(int n)
{
int o_count = 0;
int e_count = 0;
if(n < 0)
n = -n;
if(n == 0)
return 1;
if(n == 1)
return 0;
while(n)
{
if(n & 1)
o_count++;
n = n>>1;
if(n & 1)
e_count++;
n = n>>1;
}
return isMultiple(abs(o_count - e_count));
}
int main()
{
int num = 23;
if (isMultiple(num))
printf("multiple of 3");
else
printf(" not multiple of 3");
return 0;
}
Ответ 15
С# Решение для проверки того, что число делится на 3
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int num = 33;
bool flag = false;
while (true)
{
num = num - 7;
if (num == 0)
{
flag = true;
break;
}
else if (num < 0)
{
break;
}
else
{
flag = false;
}
}
if (flag)
Console.WriteLine("Divisible by 3");
else
Console.WriteLine("Not Divisible by 3");
Console.ReadLine();
}
}
}
Ответ 16
def divisible(a,b):
d = a % b
if d > 0:
print "Not divisible"
elif d == 0:
print "Divisible"
else:
pass
делится (93,3)
Ответ 17
Число делится на 3, если сумма его цифр делится на 3. Вы можете использовать это определение рекурсивно, пока вы не останетесь с одной цифрой. Если результат равен 3, 6 или 9, исходное число делится на 3, иначе оно не будет.
Exaple: 33333 = > 15 (3 + 3 + 3 + 3 + 3) = > 6 (1 + 5), поэтому 33333 делится на 3.
Ответ 18
- Вот псевдо-алгол, который я придумал.
Давайте рассмотрим двоичный ход кратных 3
000 011
000 110
001 001
001 100
001 111
010 010
010 101
011 000
011 011
011 110
100 001
100 100
100 111
101 010
101 101
просто отметим, что для двоичного кратного 3 x = abcdef в следующих парах abc= (000,011), (001 100), (010,101) cde внести изменения, следовательно, мой предложенный алгоритм:
divisible(x):
y = x&7
z = x>>3
if number_of_bits(z)<4
if z=000 or 011 or 110 , return (y==000 or 011 or 110) end
if z=001 or 100 or 111 , return (y==001 or 100 or 111) end
if z=010 or 101 , return (y==010 or 101) end
end
if divisible(z) , return (y==000 or 011 or 110) end
if divisible(z-1) , return (y==001 or 100 or 111) end
if divisible(z-2) , return (y==010 or 101) end
end