division - numeros - Verifica si un número es divisible por 3
numeros divisibles por 3 (17)
Necesito encontrar si un número es divisible por 3 sin usar % , / o * . La sugerencia fue utilizar la función atoi() . ¿Alguna idea de cómo hacerlo?
C # Solution for Check si un número es divisible por 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();
}
}
}
Aquí está su solución optimizada que todo el mundo debería saber .................
Fuente: http://www.geeksforgeeks.org/archives/511
Programa:
#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;
}
Dado un número x. Convierta x en una cadena. Analizar la cadena carácter por carácter. Convierta cada carácter analizado a un número (usando atoi ()) y sume todos estos números en un nuevo número y. Repita el proceso hasta que su número resultante final tenga un dígito de longitud. Si ese dígito es 3,6 o 9, el número original x es divisible por 3.
Divida el número en dígitos. Agrega los dígitos juntos. Repita hasta que solo le quede un dígito. Si ese dígito es 3, 6 o 9, el número es divisible por 3. (Y no se olvide de manejar 0 como un caso especial).
La pregunta de la entrevista esencialmente te pide que hagas (o ya hayas sabido) la regla de divisibilidad taquigrafía con 3 como divisor.
Una de las reglas de divisibilidad para 3 es la siguiente:
Tome cualquier número y sume cada dígito en el número. Luego tome esa suma y determine si es divisible por 3 (repite el mismo procedimiento según sea necesario). Si el número final es divisible por 3, entonces el número original es divisible por 3.
Ejemplo:
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.
Ver también
- Regla de Wikipedia / Divisibilidad : tiene muchas reglas para muchos divisores
Las respuestas actuales se enfocan en los dígitos decimales, al aplicar "agregar todos los dígitos y ver si eso se divide por 3". Ese truco en realidad también funciona en hexadecimal; por ejemplo, 0x12 se puede dividir entre 3 porque 0x1 + 0x2 = 0x3. Y "convertir" a hexadecimal es mucho más fácil que convertir a decimal.
Pseudo-código:
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;
}
[edit] Inspirado por R, una versión más rápida (O log log 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''s possible that i > 0x10 here. No big deal.
i = reduce(i);
return i==0 || i==3;
}
Mi solución en Java solo funciona para int sin firmar de 32 bits.
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;
}
Primero reduce el número a un número inferior a 32. El último paso verifica la divisibilidad desplazando la máscara el número apropiado de veces hacia la derecha.
No atoi esta C, pero como mencionó atoi , le voy a dar una solución C:
int isdiv3(int x)
{
div_t d = div(x, 3);
return !d.rem;
}
Reste 3 hasta que usted
a) llegar a 0 - el número era divisible por 3
b) obtener un número menor que 0 - el número no era divisible
- Versión editada para corregir problemas conocidos
while n > 0:
n -= 3
while n < 0:
n += 3
return n == 0
Si bien la técnica de convertir a una cadena y luego sumar los dígitos decimales es elegante, requiere división o es ineficaz en el paso de conversión a una cadena. ¿Hay alguna forma de aplicar la idea directamente a un número binario, sin convertir primero a una cadena de dígitos decimales?
Resulta que, hay:
Dado un número binario, la suma de sus bits impares menos la suma de sus bits pares es divisible por 3 si el número original era divisible por 3.
Como ejemplo: tome el número 3726, que es divisible por 3. En binario, esto es 111010001110 . Así que tomamos los dígitos impares, empezando por la derecha y moviéndonos a la izquierda, que son [1, 1, 0, 1, 1, 1]; la suma de estos es 5 . Los bits pares son [0, 1, 0, 0, 0, 1]; la suma de estos es 2 . 5 - 2 = 3, de donde podemos concluir que el número original es divisible por 3.
Un número divisible por 3, iirc tiene una característica que la suma de su dígito es divisible por 3. Por ejemplo,
12 -> 1 + 2 = 3
144 -> 1 + 4 + 4 = 9
Un número es divisible por 3 si la suma de sus dígitos es divisible por 3. Puede usar esta definición recursivamente hasta que se quede con un solo dígito. Si el resultado es 3, 6 o 9, el número original es divisible por 3, de lo contrario no lo es.
Exaple: 33333 => 15 (3 + 3 + 3 + 3 + 3) => 6 (1 + 5) entonces 33333 es divisible por 3.
Un número es divisible por 3 si todos los dígitos del número cuando se agrega da un resultado 3, 6 o 9. Por ejemplo, 3693 es divisible por 3 como 3 + 6 + 9 + 3 = 21 y 2 + 1 = 3 y 3 es divisible por 3.
bien, un número es divisible por 3 si toda la suma de dígitos del número es divisible por 3. por lo que puede obtener cada dígito como una subcadena del número de entrada y luego sumarlos. entonces repetirías este proceso hasta que solo haya un resultado de un solo dígito.
si esto es 3, 6 o 9, el número es divisible por 3.
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
*/
}
Siguiendo la misma regla, para obtener el resultado de la prueba de divisibilidad mediante ''n'', podemos: multiplicar el número por 0x1 0000 0000 - (1 / n) * 0xFFFFFFFF comparar con (1 / n) * 0xFFFFFFFF
La contrapartida es que para algunos valores, la prueba no podrá devolver un resultado correcto para todos los números de 32 bits que desea probar, por ejemplo, con la divisibilidad por 7:
tenemos 0x100000000- (1 / n) * 0xFFFFFFFF = 0xDB6DB6DC y 7 * 0xDB6DB6DC = 0x6 0000 0004, solo probaremos una cuarta parte de los valores, pero ciertamente podemos evitar eso con sustracciones.
Otros ejemplos :
11 * 0xE8BA2E8C = A0000 0004, una cuarta parte de los valores
17 * 0xF0F0F0F1 = 10 0000 0000 1 en comparación con 0xF0F0F0F ¡Todos los valores!
Etc., incluso podemos probar cada número combinando números naturales entre ellos.
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;
}
En algunos compiladores, esto es incluso más rápido que la forma regular: x % 3 . Lea más here .
- Aquí hay un pseudo-algol que se me ocurrió.
Sigamos el progreso binario de múltiplos de 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
Simplemente tenga una observación que, para un múltiplo binario de 3 x = abcdef en las parejas siguientes abc = (000,011), (001,100), (010,101) cde doest change, por lo tanto, mi algoritmo propuesto:
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