Отдел по внедрению

15

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

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

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

вход

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

740 
2

Выход

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

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

Томас О
источник
будет 740,2также разрешено для входа? то есть запятая?
gnibbler
«Результаты округляются для получения дробных результатов» - хорошо, так что, очевидно, входные данные могут также привести к получению нецелого числа ... Но как насчет делителя, который больше деленного (скажем, 5 и 10) - это разрешено или не?
Aurel Bílý
@gnibber Это было бы хорошо, но сделайте это ясно в описании программы.
Томас О
2
действительно ли разрешено использование экспонент и других математических функций? они используют разделение за кулисами, потому что многие решения делают ab⁻¹
Ming-Tang
2
это самое короткое время, но я никого не видел, когда код
phuclv

Ответы:

27

Python - 73 символа

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

from math import*
x,y=input()
z=int(exp(log(x)-log(y)))
print(z*y+y<=x)+z
gnibbler
источник
5
Это, мой друг, умнее
Аамир
Выход для "740,2" - 369. Это правильно?
Eelvex
@Eelvex, должен был быть <=, исправил это и сделал это короче :)
gnibbler
14

JavaScript, 61

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

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

Кейси Чу
источник
2
Моя любимая реализация здесь пока. Поздравляю за классный код!
Томас Эдинг
Я попытался сделать это немного короче. A=Array,P=prompt,P((''+A(+P())).split(','+A(+P())).length)
pimvdb
10

JavaScript - 36 символов

p=prompt;alert(p()*Math.pow(p(),-1))
PleaseStand
источник
5
Замена alertна pвас принесет вам несколько дополнительных символов. :)
Кейси Чу
9

Mathematica: 34 символа

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

Solve[x#[[1]]==#[[2]],x]&@Input[]
Доктор Велизарий
источник
2
23 Solve[x#==#2]&@@Input[]
символа
8

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

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

x,y=input();z=0
for i in range(32)[::-1]:z+=(1<<i)*(y<<i<=x-z*y)
print z
gnibbler
источник
8

Python, 37

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

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

print('1'*input()).count('1'*input())
Бутби
источник
7

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

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

x,y=input();z=x
while y*z>x:z-=1 
print z
gnibbler
источник
1
В некоторых случаях это хуже, чем непрерывное вычитание. например, ввод 5,4. В то время как цикл будет выполняться 4 раза, а в случае вычитания нам нужно будет только вычесть один раз.
Аамир
6

Python, 70

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

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

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

JBernardo
источник
4

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

input a,b:?a*b^-1
PleaseStand
источник
3

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.
Аурел Белый
источник
Вы использовали оператор деления в этом, вы можете сойтись с небольшим сдвигом, хотя. ;)
Томас О,
@ Томас О да ... Я заметил это сейчас ... Я действительно думал о небольшом сдвиге (когда я изменил его на / = 2 вместо / = 10) - но это был еще один символ ... Думаю, я ' Я все равно буду его использовать ... Кстати, это совсем не разделение: D.
Aurel Bílý
В вопросе говорится, что вам нужно использовать стандартный ввод, который PHP поддерживает.
Кевин Браун
@ Bass5098 А-а-а-а-а ... ну ладно, набрал 4 символа ... Исправлено.
Aurel Bílý
3

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
Lbg
источник
NoMethodError: закрытый метод `split ', вызванный для 69938: Fixnum
rkj
@rkj, извините, только Ruby 1.9. Для запуска на Ruby 1.8 вам нужно сделать на ('a'*a+'b').split('a'*b).size-13 символа больше.
LBg
3

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()))))
Мэринус
источник
2

PHP, 55 символов

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

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

Кевин Браун
источник
44 символа: <?$a=fgetcsv(STDIN);echo$a[0]*pow($a[1],-1);просто используйте запятую вместо пробела для разделения чисел.
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)
Пользователь неизвестен
источник
2

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, потому что я могу взять первый элемент из такого списка. В другом случае мне пришлось бы взять последнее, но тяжело достать последний элемент из бесконечного списка. Ну, можно доказать, что список конечен, но Хаскелл не знает лучше при выполнении фильтра, поэтому он продолжает фильтровать неопределенно долго.

Томас Эдинг
источник
2

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

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

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

Strigoides
источник
2

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

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

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

Hovercouch
источник
Как «Возьмите два ввода в stdin, разделенных новыми строками или пробелами (ваш выбор)», лучше выбрать более поздние значения, разделенные пробелами. В этом случае вы можете написать read x y. С удалением еще нескольких пробелов можно сократить до 64 символов: pastebin.com/Y3SfSXWk
manatwork
1

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

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

x,y=input()
print-1+len((x*'.').split('.'*y))
gnibbler
источник
1

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)
меморандум
источник
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?

Лямбда Фея
источник
0

Python, 46 байт

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

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

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]

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

aka.nice
источник
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
источник
0

DC: 26 символов

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

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

Форс
источник
0

Python 54

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

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

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

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

источник
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
источник
0

Python, 40 символов

print(float(input())*float(input())**-1)
fdvfcges
источник
0

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

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

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

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

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

mbomb007
источник
Как вы считаете это 25 байтами? Если вы ожидаете унарный ввод / вывод, вы должны сказать об этом (и я думаю, что это 24 байта). Не уверен, почему вы рассматриваете случай 0 отдельно: retina.tryitonline.net/…
Мартин Эндер
Это было неправильно скопировано
mbomb007