Реализуйте алгоритм деления на вашем любимом языке, который обрабатывает целочисленное деление. Он должен обрабатывать только положительные числа - но бонусные баллы, если он обрабатывает также отрицательное и смешанное деление. Результаты округляются для получения дробных результатов.

Программа не может содержать /, \, divили аналогичные оператор. Это должна быть процедура, которая не использует родные возможности разделения языка.

Вам нужно только обрабатывать до 32-битного деления. Использование повторного вычитания не допускается.

вход

Возьмите два ввода в stdin, разделенных новыми строками или пробелами (на ваш выбор)

740 
2

Выход

В этом случае вывод будет 370.

Решение, которое является самым коротким, выигрывает.

Python - 73 символа

Принимает ввод через запятую, например 740,2

from math import*
x,y=input()
z=int(exp(log(x)-log(y)))
print(z*y+y<=x)+z

JavaScript, 61

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

Это делает строку длиной делимого ,,,,,,(6) и разделяется на делитель ,,,(3), в результате чего получается массив длиной 3:, из ['', '', '']которого я затем вычитаю единицу длины. Определенно не самый быстрый, но, тем не менее, интересный!

JavaScript - 36 символов

p=prompt;alert(p()*Math.pow(p(),-1))

Mathematica: 34 символа

Символически решает уравнение (xa == b)

Solve[x#[[1]]==#[[2]],x]&@Input[]

Питон - 72 символа

Принимает ввод через запятую, например, 740,2

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

Python, 37

Шаг 1. Конвертировать в одинарный.

Шаг 2. Унарный алгоритм деления.

print('1'*input()).count('1'*input())

Питон - 41 символ

Принимает ввод через запятую, например 740,2

x,y=input();z=x
while y*z>x:z-=1 
print z

Python, 70

Что-то сумасшедшее, что я только что подумал (используя ввод через запятую):

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

Если вы принимаете небольшие ошибки точности с плавающей точкой, roundфункция может быть отброшена.

Ябасич - 17 персонажей

input a,b:?a*b^-1

PHP - 82 символа (глючит)

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

Однако это очень простое решение - оно не обрабатывает дроби или другие знаки (может попасть в бесконечный цикл). Я не буду вдаваться в детали в этом, это довольно просто.

Ввод в стандартный ввод, разделенный новой строкой.

PHP - 141 символ (полный)

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

Вход и выход такие же, как и предыдущий.

Да, это почти в два раза больше предыдущего, но это:

• правильно обрабатывает дроби
• правильно обрабатывает знаки
• никогда не войдет в бесконечный цикл, ЕСЛИ БЕЗ второго параметра равен 0 - но это деление на ноль - неверный ввод

Переформатировать и объяснить:

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

Ruby 1.9, 28 символов

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

Остальная часть дивизии, 21 персонаж

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

Образец:

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

Для Ruby 1.8:

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

APL (6)

⌊*-/⍟⎕

/здесь не деление, но foldr. то есть, F/a b cесть a F (b F c). Если я не могу использовать, foldrпотому что это называется /, это может быть сделано в 9 символов:

⌊*(⍟⎕)-⍟⎕

Объяснение:

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

PHP, 55 символов

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

Выход (740/2): http://codepad.viper-7.com/ucTlcq

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)

Haskell, 96 знаков

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

Ввод в одной строке.

Код просто ищет ответ, беря делитель dи умножая его на все целые числа n >= 0. Позвольте mбыть дивидендом. Самый большой nтакой, который n * d <= mвыбран, чтобы быть ответом. Код на самом деле выбирает наименьшее n, что n * d > mвычитает из него 1, потому что я могу взять первый элемент из такого списка. В другом случае мне пришлось бы взять последнее, но тяжело достать последний элемент из бесконечного списка. Ну, можно доказать, что список конечен, но Хаскелл не знает лучше при выполнении фильтра, поэтому он продолжает фильтровать неопределенно долго.

Common Lisp, 42 персонажа

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

Принимает пробел или ввод через строку

Bash, 72 64 персонажа

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

Выведите бесконечное число новых строк, возьмите первые x, поместите их все в файл с именем f, затем получите размер f в блоках размером y. Принял совет Манатворка, чтобы сбрить восемь персонажей.

Питон - 45 символов

Принимает ввод через запятую, например, 740,2

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

Python, 94 символа

Рекурсивный бинарный поиск:

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)

Питон, 148

Другие решения могут быть короткими, но масштабированы ли они ?

Вот элегантное решение с постоянным временем , использующее возможности CLOUD.

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

Я упоминал, что он также использует Haskell?

Python, 46 байт

Никто не опубликовал скучное решение по вычитанию, поэтому я не удержался.

а, б = вход ()
I = 0
в то время как a> = b: a- = b; i + = 1
распечатать я

Smalltalk , Squeak 4.x вкус

определить это двоичное сообщение в 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)

После игры в гольф этот коэффициент все еще длинный (88 символов):

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

Но это достаточно быстро:

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

-> 127 мс на моем скромном Mac mini (8 моп / с)

По сравнению с обычным делением:

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

-> 31 мс, это всего в 4 раза медленнее

Я не считаю символы для чтения stdin или записи stdout, Squeak не был разработан для сценариев.

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

Конечно, глупее повторять вычитание

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

или просто тупое перечисление

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

может работать, но не очень интересно

#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);
}

DC: 26 символов

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

Я признаю, что это не самое быстрое решение.

Python 54

Принимает ввод через запятую.

1. Делает строку из точек длиной х
2. Заменяет сегменты точек длины y одной запятой
3. Считает запятые.

Слова, потому что уценка умирает со списком, за которым следует код ?:

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

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

int divide (int num, int divideBy)
{
    int sum = 0;
    int shift = divideBy -1;
    while (num > divideBy) {
        sum += num >> shift ;
        num = (num >> shift ) + (num & divideBy);
    }
    if (num == divideBy) ++sum;
    return sum; 
}

Ссылка: http://www.forums.hscripts.com/viewtopic.php?f=13&t=1358

Python, 40 символов

print(float(input())*float(input())**-1)

Python, 37

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

Создает строку length x( '0'*x) и использует расширенные срезы для выбора каждого yсимвола, начиная с индекса y-1. Печатает длину полученной строки.

Как и Gnibbler, для этого требуется ввод через запятую. Удаление это стоит 9символов:

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

Сетчатка 0.7.3, 33 байта (не конкурирует)

Язык новее, чем вызов. Сначала вводится разделенный пробелами разделитель. Деление на ноль не определено.

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

Попробуйте онлайн