Wdrożenie podziału

15

Zaimplementuj algorytm podziału w swoim ulubionym języku, który obsługuje dzielenie liczb całkowitych. Musi obsługiwać tylko liczby dodatnie - ale punkty bonusowe, jeśli obsługuje także podział ujemny i znak mieszany. Wyniki są zaokrąglane w dół dla wyników ułamkowych.

Program nie może zawierać /, \, divlub podobne podmioty. Musi to być procedura, która nie korzysta z natywnych możliwości podziału języka w tym języku.

Musisz tylko obsłużyć podział 32-bitowy. Używanie powtarzanego odejmowania nie jest dozwolone.

Wejście

Weź dwa wejścia na standardowe wejście oddzielone nowymi liniami lub spacjami (twój wybór)

740 
2

Wynik

W takim przypadku wynik byłby 370.

Rozwiązanie, które jest najkrótsze, wygrywa.

Thomas O
źródło
jest 740,2również dozwolone dla danych wejściowych? tzn. oddzielone przecinkiem?
gnibbler
„Wyniki są zaokrąglane w dół dla wyników ułamkowych” - ok, więc najwyraźniej dane wejściowe mogą również skutkować liczbą niecałkowitą ... Ale co z dzielnikiem większym niż podzielony (powiedzmy 5 i 10) - czy jest to dozwolone lub nie?
Aurel Bílý
@gnibber To by było w porządku, ale wyjaśnij to w opisie programu.
Thomas O
2
czy używanie wykładniczych i innych funkcji matematycznych jest naprawdę dozwolone? używają podziału za kulisami, ponieważ wiele rozwiązań działa w sposób ab --¹
Ming-Tang
2
jest to najkrótszy czas, ale nie widziałem, żeby ktokolwiek
kodował

Odpowiedzi:

27

Python - 73 znaki

Pobiera dane oddzielone przecinkami, np 740,2

from math import*
x,y=input()
z=int(exp(log(x)-log(y)))
print(z*y+y<=x)+z
gnibbler
źródło
5
To jest mój przyjaciel, CLEVER
Aamir
Dane wyjściowe dla „740,2” wynoszą 369. Czy to prawda?
Eelvex
@Eelvex, powinien był być <=, naprawił i
skrócił
14

JavaScript, 61

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

To sprawia, że ​​łańcuch ma długość dywidendy ,,,,,,(6) i dzieli się na dzielniku ,,,(3), w wyniku czego powstaje tablica o długości 3 ['', '', '']:, której długości następnie odejmuję. Zdecydowanie nie najszybszy, ale mam nadzieję, że mimo to interesujący!

Casey Chu
źródło
2
Jak dotąd moja ulubiona implementacja. Gratulacje za fajny kod!
Thomas Eding,
Próbowałem zrobić to trochę krócej. A=Array,P=prompt,P((''+A(+P())).split(','+A(+P())).length)
pimvdb,
10

JavaScript - 36 znaków

p=prompt;alert(p()*Math.pow(p(),-1))
Proszę wstać
źródło
5
Wymiana alertz pzłowi Ci kilka dodatkowych znaków. :)
Casey Chu,
9

Mathematica: 34 znaki

Rozwiązuje symbolicznie równanie (xa == b)

Solve[x#[[1]]==#[[2]],x]&@Input[]
Dr Belizariusz
źródło
2
23 znaki,Solve[x#==#2]&@@Input[]
chyanog
8

Python - 72 znaki

Pobiera dane oddzielone przecinkami, np. 740,2

x,y=input();z=0
for i in range(32)[::-1]:z+=(1<<i)*(y<<i<=x-z*y)
print z
gnibbler
źródło
8

Python, 37

Krok 1. Konwertuj na unary.

Krok 2. Algorytm podziału jednostkowego.

print('1'*input()).count('1'*input())
boothby
źródło
7

Python - 41 znaków

Pobiera dane oddzielone przecinkami, np 740,2

x,y=input();z=x
while y*z>x:z-=1 
print z
gnibbler
źródło
1
W niektórych przypadkach jest to gorsze niż ciągłe odejmowanie. np. wkład wynosi 5,4. podczas gdy pętla będzie działać 4 razy, podczas gdy w przypadku odejmowania, będziemy musieli odjąć tylko raz.
Aamir
6

Python, 70

Coś szalonego, co właśnie pomyślałem (używając danych oddzielonych przecinkami):

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

Jeśli zaakceptujesz małe błędy precyzji float, roundfunkcję można usunąć.

JBernardo
źródło
4

Yabasic - 17 znaków

input a,b:?a*b^-1
Proszę wstać
źródło
3

PHP - 82 znaki (buggy)

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

Jest to jednak bardzo proste rozwiązanie - nie obsługuje ułamków ani różnych znaków (skoczyłby w nieskończoną pętlę). Nie będę wchodził w szczegóły w tym, jest to dość proste.

Dane wejściowe są w standardowym, oddzielonym nowym wierszu.

PHP - 141 znaków (pełny)

$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;

Wejście i wyjście takie same jak poprzednie.

Tak, jest prawie dwa razy większy niż poprzedni, ale:

  • poprawnie obsługuje ułamki
  • poprawnie obsługuje znaki
  • nigdy nie wejdzie w nieskończoną pętlę, chyba że drugi parametr to 0 - ale to jest dzielenie przez zero - nieprawidłowe dane wejściowe

Ponowne formatowanie i objaśnienie:

$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ý
źródło
W tym przypadku użyłeś operatora podziału, możesz jednak uciec z odrobiną zmiany. ;)
Thomas O
@Thomas O tak ... Zauważyłem to teraz ... Właściwie myślałem o odrobinie zmiany (kiedy zmieniłem na / = 2 zamiast / = 10) - ale to był jeszcze jeden znak ... I tak będę musiał go użyć ... Btw to wcale nie podział: D.
Aurel Bílý
Pytanie mówi, że musisz użyć stdin, które PHP obsługuje.
Kevin Brown
@ Bass5098 Aaahhh ... No cóż, zyskałem 4 znaki ... Naprawiono.
Aurel Bílý
3

Ruby 1.9, 28 znaków

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

Reszta podziału, 21 znaków

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

Próba:

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

Dla 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
źródło
NoMethodError: prywatna metoda `split 'wywołała 69938: Fixnum
rkj
@rkj, Przepraszamy, tylko Ruby 1.9. Aby uruchomić Ruby 1.8, musisz zrobić ('a'*a+'b').split('a'*b).size-13 postacie większe.
LBg
3

APL (6)

⌊*-/⍟⎕

/nie jest tutaj podział, ale foldr. tj . F/a b cjest a F (b F c). Jeśli nie mogę użyć, foldrponieważ się nazywa /, można to zrobić za pomocą 9 znaków:

⌊*(⍟⎕)-⍟⎕

Wyjaśnienie:

  • : input()
  • ⍟⎕: map(log, input())
  • -/⍟⎕: foldr1(sub, map(log, input()))
  • *-/⍟⎕: exp(foldr1(sub, map(log, input())))
  • ⌊*-/⍟⎕: floor(exp(foldr1(sub, map(log, input()))))
marinus
źródło
2

PHP, 55 znaków

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

Dane wyjściowe (740/2): http://codepad.viper-7.com/ucTlcq

Kevin Brown
źródło
44 znaki: po <?$a=fgetcsv(STDIN);echo$a[0]*pow($a[1],-1);prostu użyj przecinka zamiast spacji, aby oddzielić liczby.
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)
nieznany użytkownik
źródło
2

Haskell, 96 znaków

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

Wejście jest w jednym wierszu.

Kod po prostu szuka odpowiedzi, biorąc dzielnik di mnożąc go przez wszystkie liczby całkowite n >= 0. Niech mbędzie dywidenda. Największy ntaki, żen * d <= m zostanie wybrany jako odpowiedź. Kod faktycznie wybiera najmniejszą z nnich n * d > mi odejmuje 1 od niego, ponieważ mogę wziąć pierwszy element z takiej listy. W innym przypadku musiałbym wziąć ostatni, ale ciężko jest zabrać ostatni element z nieskończonej listy. Cóż, wykaz może być skończony, ale Haskell nie wie lepiej podczas wykonywania filtru, więc kontynuuje filtrowanie w nieskończoność.

Thomas Eding
źródło
2

Common Lisp, 42 znaki

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

Akceptuje wejście oddzielone spacją lub wierszem

Strigoides
źródło
2

Grzmotnąć, 72 64 znaków

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

Wyjmij nieskończoną liczbę nowych linii, weź pierwsze x, umieść je wszystkie w pliku o nazwie f, a następnie uzyskaj wielkość f w blokach wielkości y. Skorzystał z rady manatworku, aby zgolić osiem postaci.

Hovercouch
źródło
Ponieważ „Weź dwa wejścia na standardowe wejście oddzielone nowymi liniami lub spacjami (twój wybór)”, lepiej wybierz później wartości rozdzielone spacją. W takim przypadku możesz pisać read x y. Po usunięciu kilku dodatkowych spacji można zmniejszyć do 64 znaków: pastebin.com/Y3SfSXWk
manatwork
1

Python - 45 znaków

Pobiera dane oddzielone przecinkami, np. 740,2

x,y=input()
print-1+len((x*'.').split('.'*y))
gnibbler
źródło
1

Python, 94 znaki

Rekurencyjne wyszukiwanie binarne:

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)
notatka
źródło
1

Python, 148

Inne rozwiązania mogą być krótkie, ale czy mają skalę internetową ?

Oto eleganckie, stałe rozwiązanie, które wykorzystuje moc CHMURY.

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

Czy wspominałem, że używa również Haskell?

Lambda Fairy
źródło
0

Python, 46 bajtów

Nikt nie opublikował nudnego rozwiązania odejmowania, więc nie mogłem się powstrzymać.

a, b = input ()
i = 0
podczas gdy a> = b: a- = b; i + = 1
wydrukuj i
cemper93
źródło
0

Smalltalk , pisk 4. smak

zdefiniuj ten komunikat binarny w liczbie całkowitej:

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

Po zagraniu w golfa ten iloraz jest nadal długi (88 znaków):

%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)

Ale jest dość szybki:

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

-> 127 ms na moim skromnym komputerze Mac mini (8 MOp / s)

W porównaniu do zwykłego podziału:

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

-> 31 ms, jest tylko 4 razy wolniejszy

Nie liczę znaków, aby czytać standardowe lub pisać standardowe, Squeak nie został zaprojektowany do pisania skryptów.

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

Oczywiście bardziej głupie powtarzające się odejmowanie

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

lub zwykłe głupie wyliczenie

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

może również działać, ale nie są naprawdę interesujące

aka.nice
źródło
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
źródło
0

DC: 26 znaków

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

Przyznaję, że nie jest to najszybsze rozwiązanie na rynku.

Fors
źródło
0

Python 54

Pobiera dane rozdzielane przecinkami.

  1. Tworzy ciąg kropek o długości x
  2. Zastępuje segmenty kropek o długości y pojedynczym przecinkiem
  3. Liczy przecinki.

Słowa, ponieważ markdown umiera wraz z listą, po której następuje kod ?:

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

źródło
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
tartin
źródło
0

Python, 40 znaków

print(float(input())*float(input())**-1)
fdvfcges
źródło
0

Python, 37

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

Konstruuje ciąg length x( '0'*x) i korzysta z rozszerzonego krojenia, aby wybrać co ydziesiąty znak, zaczynając od indeksu y-1. Wyświetla długość wynikowego ciągu.

Podobnie jak Gnibbler, wymaga to danych oddzielonych przecinkami. Usunięcie go kosztuje 9znaki:

i=input
x,y=i(),i()
print len(('0'*x)[y-1::y])
Justin
źródło
0

Retina 0.7.3, 33 bajty (nie konkuruje)

Język jest nowszy niż wyzwanie. Najpierw pobiera separator spacji z dzielnikiem. Dzielenie przez zero jest niezdefiniowane.

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

Wypróbuj online

mbomb007
źródło
Jak liczyć to jako 25 bajtów? Jeśli oczekujesz jednoargumentowego We / Wy, powinieneś to powiedzieć (i myślę, że to 24 bajty). Nie jestem pewien, dlaczego traktujesz przypadek 0 osobno: retina.tryitonline.net/...
Martin Ender,
Został źle skopiowany
mbomb007,