Implementar división

15

Implemente un algoritmo de división en su idioma favorito que maneje la división de enteros. Solo necesita manejar números positivos, pero puntos de bonificación si también maneja la división de signos negativos y mixtos. Los resultados se redondean hacia abajo para obtener resultados fraccionarios.

El programa no puede contener las /, \, divo similares operadores. Debe ser una rutina que no utilice las capacidades de división nativas del lenguaje.

Solo necesita manejar una división de hasta 32 bits. No se permite la resta repetida.

Entrada

Tome dos entradas en stdin separadas por nuevas líneas o espacios (su elección)

740 
2

Salida

En este caso, la salida sería 370.

La solución que es la más corta gana.

Thomas O
fuente
740,2también está permitido para la entrada? es decir, separados por comas?
gnibbler
"Los resultados se redondean hacia abajo para obtener resultados fraccionarios", está bien, por lo que aparentemente la entrada también puede dar como resultado un número no entero ... ¿no?
Aurel Bílý
@gnibber Eso estaría bien, pero que quede claro en la descripción del programa.
Thomas O
2
¿Está realmente permitido usar exponenciales y otras funciones matemáticas? usan la división detrás de escena, porque muchas soluciones están funcionando ab⁻¹
Ming-Tang
2
esto es más corto de tiempo, pero no he visto a nadie el código de tiempo
phuclv

Respuestas:

27

Python - 73 caracteres

Toma entradas separadas por comas, p. Ej. 740,2

from math import*
x,y=input()
z=int(exp(log(x)-log(y)))
print(z*y+y<=x)+z
gnibbler
fuente
55
Esto, mi amigo, es INTELIGENTE
Aamir
La salida para "740,2" es 369. ¿Es esto correcto?
Eelvex
@Eelvex, debería haber sido <=, lo arregló y lo hizo más corto :)
gnibbler
14

JavaScript, 61

A=Array,P=prompt,P((','+A(+P())).split(','+A(+P())).length-1)

Esto hace que una cadena tenga la longitud del dividendo ,,,,,,(6) y se divide en el divisor ,,,(3), lo que da como resultado una matriz de longitud 3: de ['', '', '']cuya longitud restaré una. Definitivamente no es el más rápido, pero espero que sea interesante.

Casey Chu
fuente
2
Mi implementación favorita aquí hasta ahora. ¡Felicidades por el código genial!
Thomas Eding
Traté de hacerlo un poco más corto. A=Array,P=prompt,P((''+A(+P())).split(','+A(+P())).length)
pimvdb
10

JavaScript: 36 caracteres

p=prompt;alert(p()*Math.pow(p(),-1))
Por favor levantese
fuente
55
Reemplazar alertcon le pdará algunos caracteres adicionales. :)
Casey Chu
9

Mathematica: 34 caracteres

Resuelve simbólicamente la ecuación (xa == b)

Solve[x#[[1]]==#[[2]],x]&@Input[]
Dr. belisario
fuente
2
23 caracteres,Solve[x#==#2]&@@Input[]
chyanog
8

Python - 72 caracteres

Toma entradas separadas por comas, p. Ej. 740,2

x,y=input();z=0
for i in range(32)[::-1]:z+=(1<<i)*(y<<i<=x-z*y)
print z
gnibbler
fuente
8

Python, 37

Paso 1. Convertir a unario.

Paso 2. Algoritmo de división unaria.

print('1'*input()).count('1'*input())
boothby
fuente
7

Python - 41 caracteres

Toma entradas separadas por comas, p. Ej. 740,2

x,y=input();z=x
while y*z>x:z-=1 
print z
gnibbler
fuente
1
Esto, en algunos casos, es peor que restar continuamente. por ejemplo, la entrada es 5,4. while loop se ejecutará 4 veces mientras que en caso de resta, solo tendremos que restar una vez.
Aamir
6

Python, 70

Algo loco que acabo de pensar (usando una entrada separada por comas):

from cmath import*
x,y=input()
print round(tan(polar(y+x*1j)[1]).real)

Si acepta pequeños errores de precisión de flotación, la roundfunción se puede descartar.

JBernardo
fuente
4

Yabasic - 17 caracteres

input a,b:?a*b^-1
Por favor levantese
fuente
3

PHP - 82 caracteres (buggy)

$i=fgets(STDIN);$j=fgets(STDIN);$k=1;while(($a=$j*$k)<$i)$k++;echo($a>$i?--$k:$k);

Sin embargo, esta es una solución muy simple: no maneja fracciones o signos diferentes (saltaría a un bucle infinito). No voy a entrar en detalles en este caso, es bastante simple.

La entrada está en stdin, separada por una nueva línea.

PHP - 141 caracteres (completo)

$i*=$r=($i=fgets(STDIN))<0?-1:1;$j*=$s=($j=fgets(STDIN))<0?-1:1;$k=0;$l=1;while(($a=$j*$k)!=$i){if($a>$i)$k-=($l>>=2)*2;$k+=$l;}echo$k*$r*$s;

Entrada y salida igual que la anterior.

Sí, esto es casi el doble del tamaño del anterior, pero:

  • maneja fracciones correctamente
  • maneja los letreros correctamente
  • nunca entrará en un bucle infinito, A MENOS que el segundo parámetro sea 0 - pero eso es división por cero - entrada inválida

Reformatear y explicar:

$i *= $r = ($i = fgets(STDIN)) < 0 ? -1 : 1;
$j *= $s = ($j = fgets(STDIN)) < 0 ? -1 : 1;
                                    // First, in the parentheses, $i is set to
                                    // GET variable i, then $r is set to -1 or
                                    // 1, depending whether $i is negative or
                                    // not - finally, $i multiplied by $r ef-
                                    // fectively resulting in $i being the ab-
                                    // solute value of itself, but keeping the
                                    // sign in $r.
                                    // The same is then done to $j, the sign
                                    // is kept in $s.

$k = 0;                             // $k will be the result in the end.

$l = 1;                             // $l is used in the loop - it is added to
                                    // $k as long as $j*$k (the divisor times
                                    // the result so far) is less than $i (the
                                    // divided number).

while(($a = $j * $k) != $i){        // Main loop - it is executed until $j*$k
                                    // equals $i - that is, until a result is
                                    // found. Because a/b=c, c*b=a.
                                    // At the same time, $a is set to $j*$k,
                                    // to conserve space and time.

    if($a > $i)                     // If $a is greater than $i, last step
        $k -= ($l >>= 2) * 2;       // (add $l) is undone by subtracting $l
                                    // from $k, and then dividing $l by two
                                    // (by a bitwise right shift by 1) for
                                    // handling fractional results.
                                    // It might seem that using ($l>>=2)*2 here
                                    // is unnecessary - but by compressing the
                                    // two commands ($k-=$l and $l>>=2) into 1
                                    // means that curly braces are not needed:
                                    //
                                    // if($a>$i)$k-=($l>>=2)*2;
                                    //
                                    // vs.
                                    //
                                    // if($a>$i){$k-=$l;$l>>=2;}

    $k += $l;                       // Finally, $k is incremented by $l and
                                    // the while loop loops again.
}

echo $k * $r * $s;                  // To get the correct result, $k has to be
                                    // multiplied by $r and $s, keeping signs
                                    // that were removed in the beginning.
Aurel Bílý
fuente
Usaste un operador de división en este caso, aunque podrías salirte con un poco de cambio. ;)
Thomas O
@Thomas O sí ... Lo noté ahora ... En realidad estaba pensando en un pequeño cambio (cuando lo cambié a / = 2 en lugar de / = 10), pero fue un personaje más ... Supongo que ' tendré que usarlo de todos modos ... Por cierto, eso no es división en absoluto: D.
Aurel Bílý
La pregunta dice que necesita usar stdin, que PHP tiene soporte para.
Kevin Brown
@ Bass5098 Aaahhh ... Oh, bueno, gané 4 caracteres ... Solucionado.
Aurel Bílý
3

Ruby 1.9, 28 caracteres

(?a*a+?b).split(?a*b).size-1

Resto de división, 21 caracteres.

?a*a=~/(#{?a*b})\1*$/  

Muestra:

a = 756
b = 20
print (?a*a+?b).split(?a*b).size-1  # => 37
print ?a*a=~/(#{?a*b})\1*$/         # => 16

Para Ruby 1.8:

a = 756
b = 20
print ('a'*a+'b').split('a'*b).size-1  # => 37
print 'a'*a=~/(#{'a'*b})\1*$/          # => 16
LBg
fuente
NoMethodError: el método privado 'split' solicitó 69938: Fixnum
rkj
@rkj, lo siento, solo Ruby 1.9. Para correr en Ruby 1.8 debes hacerlo ('a'*a+'b').split('a'*b).size-1, 3 caracteres más grandes.
LBg
3

APL (6)

⌊*-/⍟⎕

/ no es división aquí, pero foldr . es decir, F/a b ces a F (b F c). Si no puedo usar foldrporque se llama /, se puede hacer en 9 caracteres:

⌊*(⍟⎕)-⍟⎕

Explicación:

  • : input()
  • ⍟⎕: map(log, input())
  • -/⍟⎕: foldr1(sub, map(log, input()))
  • *-/⍟⎕: exp(foldr1(sub, map(log, input())))
  • ⌊*-/⍟⎕: floor(exp(foldr1(sub, map(log, input()))))
marinus
fuente
2

PHP, 55 caracteres

<?$a=explode(" ",fgets(STDIN));echo$a[0]*pow($a[1],-1);

Salida (740/2): http://codepad.viper-7.com/ucTlcq

Kevin Brown
fuente
44 caracteres: <?$a=fgetcsv(STDIN);echo$a[0]*pow($a[1],-1);solo use una coma en lugar de un espacio para separar los números.
jdstankosky
2

Scala 77

def d(a:Int,b:Int,c:Int=0):Int=if(b<=a)d(a-b,b,c+1)else c
d(readInt,readInt)
usuario desconocido
fuente
2

Haskell, 96 caracteres

main=getLine>>=print.d.map read.words
d[x,y]=pred.snd.head.filter((>x).fst)$map(\n->(n*y,n))[0..]

La entrada está en una sola línea.

El código solo busca la respuesta tomando el divisor dy multiplicándolo contra todos los enteros n >= 0. Deja que msea ​​el dividendo. El más grande ntal que n * d <= mse elige para ser la respuesta. El código recoge en realidad los menos ntales que n * d > my resta 1 porque puedo dar el primer elemento de una lista de este tipo. En el otro caso, tendría que tomar el último, pero es difícil tomar el último elemento de una lista infinita. Bueno, se puede demostrar que la lista es finita, pero Haskell no sabe mejor cuando realiza el filtro, por lo que continúa filtrándose indefinidamente.

Thomas Eding
fuente
2

Lisp común, 42 caracteres

(1-(loop as x to(read)by(read)counting t))

Acepta espacios o entradas separadas por líneas

Strigoides
fuente
2

Golpetazo, 72 64 caracteres

read x y;yes ''|head -n$x>f;ls -l --block-size=$y f|cut -d\  -f5

Genere un número infinito de líneas nuevas, tome la primera x, colóquelas en un archivo llamado f, luego obtenga el tamaño de f en bloques del tamaño de y. Tomó el consejo de manatwork para afeitar a ocho personajes.

Hovercouch
fuente
Como “Tome dos entradas en stdin separadas por nuevas líneas o espacios (su elección)”, elija mejor los valores separados por espacios. En cuyo caso puedes escribir read x y. Con unos pocos espacios más eliminados se puede reducir a 64 caracteres: pastebin.com/Y3SfSXWk
manatwork
1

Python - 45 caracteres

Toma entradas separadas por comas, p. Ej. 740,2

x,y=input()
print-1+len((x*'.').split('.'*y))
gnibbler
fuente
1

Python, 94 caracteres

Una búsqueda binaria recursiva:

a,b=input()
def r(m,n):return r(m,m+n>>1)if n*b>a else n if n*b+b>a else r(n,2*n)
print r(0,1)
memorándum
fuente
1

Pitón, 148

Otras soluciones pueden ser cortas, pero ¿son escala web ?

Aquí hay una solución elegante y de tiempo constante que aprovecha el poder de la NUBE.

from urllib import*
print eval(urlopen('http://tryhaskell.org/haskell.json?method=eval&expr=div%20'+raw_input()+'%20'+raw_input()).read())['result']

¿Mencioné que también usa Haskell?

Hada lambda
fuente
0

Python, 46 bytes

Nadie había publicado la solución de resta aburrida, por lo que no pude resistirme a hacerlo.

a, b = input ()
i = 0
mientras a> = b: a- = b; i + = 1
imprimir i
cemper93
fuente
0

Smalltalk , Squeak 4.x sabor

defina este mensaje binario en Integer:

% d 
    | i |
    d <= self or: [^0].
    i := self highBit - d highBit.
    d << i <= self or: [i := i - 1].
    ^1 << i + (self - (d << i) % d)

Una vez golfizado, este cociente aún es largo (88 caracteres):

%d|i n|d<=(n:=self)or:[^0].i:=n highBit-d highBit.d<<i<=n or:[i:=i-1].^1<<i+(n-(d<<i)%d)

Pero es razonablemente rápido:

[0 to: 1000 do: [:n |
    1 to: 1000 do: [:d |
        self assert: (n//d) = (n%d)]].
] timeToRun.

-> 127 ms en mi modest mac mini (8 MOp / s)

En comparación con la división regular:

[0 to: 1000 do: [:n |
    1 to: 1000 do: [:d |
        self assert: (n//d) = (n//d)]].
] timeToRun.

-> 31 ms, es solo 4 veces más lento

No cuento los caracteres para leer stdin o escribir stdout, Squeak no fue diseñado para scripting.

FileStream stdout nextPutAll:
    FileStream stdin nextLine asNumber%FileStream stdin nextLine asNumber;
    cr

Por supuesto, una sustracción repetida más estúpida

%d self>d and:[^0].^self-d%d+1

o simple enumeración estúpida

%d^(0to:self)findLast:[:q|q*d<=self]

podría funcionar también, pero no son realmente interesantes

aka.nice
fuente
0
#include <stdio.h>
#include <string.h>
#include <math.h>


main()
{
   int i,j,ans;
   i=740;
   j=2;

   ans = pow(10,log10(i) - log10(j));
   printf("\nThe answer is %d",ans);
}
jithin
fuente
0

DC: 26 caracteres

?so?se0[1+dle*lo>i]dsix1-p

Admito que no es la solución más rápida.

Fors
fuente
0

Python 54

Toma entrada delimitada por comas.

  1. Hace una cadena de puntos de longitud x
  2. Reemplaza segmentos de puntos de longitud y con una coma simple
  3. Cuenta comas.

¿Palabras porque Markdown muere con una lista seguida de código ?:

x,y=input()
print("."*x).replace("."*y,',').count(',')

fuente
0

Q, 46

{-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}

.

q){-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}[740;2]
370
q){-1+(#){x-y}[;y]\[{s[x-y]<>(s:signum)x}[y];x]}[740;3]
246
tmartin
fuente
0

Python, 40 caracteres

print(float(input())*float(input())**-1)
fdvfcges
fuente
0

Python, 37

x,y=input()
print len(('0'*x)[y-1::y])

Construye una cadena de longitud x( '0'*x) y utiliza un corte extendido para seleccionar cada ycarácter, comenzando desde el índice y-1. Imprime la longitud de la cadena resultante.

Al igual que Gnibbler, esto toma entradas separadas por comas. Eliminarlo cuesta 9caracteres:

i=input
x,y=i(),i()
print len(('0'*x)[y-1::y])
Justin
fuente
0

Retina 0.7.3, 33 bytes (no compite)

El lenguaje es más nuevo que el desafío. Toma entrada separada por espacios con el divisor primero. La división por cero no está definida.

\d+
$*
^(.+) (\1)+.*$
$#+
.+ .*
0

Pruébalo en línea

mbomb007
fuente
¿Cómo cuenta esto como 25 bytes? Si espera E / S unarias, debería decirlo (y creo que son 24 bytes). Sin embargo, no estoy seguro de por qué trata el caso 0 por separado: retina.tryitonline.net/…
Martin Ender
Fue mal copiado
mbomb007