Эфиопское Умножение

17

Этот вопрос вдохновлен этим ответом . По совпадению я использовал Эфиопское Умножение, когда я был ребенком, но никогда не знал название метода до недавнего времени.

Эфиопское умножение - это метод умножения целых чисел с использованием только сложения, удвоения и деления пополам.

Метод:

  1. Возьмите два числа, которые нужно умножить, и запишите их в верхней части двух столбцов.
  2. В левом столбце несколько раз делите пополам последнее число, отбрасывая все остатки, и записывайте результат ниже последнего в том же столбце, пока не напишите значение 1.
  3. В правом столбце несколько раз удвойте последнее число и напишите результат ниже. остановка, когда вы добавляете результат в той же строке, где в левом столбце отображается 1.
  4. Изучите созданную таблицу и откажитесь от любой строки, в которой значение в левом столбце является четным. Суммируйте значения в правом столбце, которые остались, чтобы получить результат умножения исходных двух чисел вместе.

Например: 17 х 34

17    34

Половина первого столбца:

17    34
 8
 4
 2
 1

Удвоение второго столбца:

17    34
 8    68
 4   136 
 2   272
 1   544

В зачеркнутых строках, чья первая ячейка четная, мы сделаем это, заключив эти числа справа в квадратные скобки:

17    34
 8   [68]
 4  [136]
 2  [272]
 1   544

Суммируйте оставшиеся числа в правом столбце:

17    34
 8   [68]
 4  [136]
 2  [272]
 1   544
    =====
     578

Таким образом, 17, умноженное на 34, по эфиопскому методу равно 578.

Задание:

Гольф-код, который принимает два числа от 1 до 1000 и выполняет ту же схему и алгоритм, отображая продукт ниже.

Метод ввода: однако вы выбираете ...

Пример ввода:

19 427

Результирующий вывод:

19   427
 9   854
 4 [1708]
 2 [3416]
 1  6832
   ======
    8113

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

тестирование

Как вы будете это тестировать? Предоставляя прогон вашей программы, используя два числа. Эти числа могут быть извлечены из вашего идентификационного номера пользователя (это можно получить, наведя курсор на свой аватар в верхнем окне). Возьмите ваш номер и возьмите последние три цифры, это будет номер B, возьмите все остальное, что будет впереди, это будет номер A. Затем проверьте на A раз B.

Пример тестирования:

Мой идентификационный номер пользователя 8555, поэтому мои номера 8 и 555. Таким образом, мой вывод должен выглядеть следующим образом:

8  [555]
4 [1110]
2 [2220]
1  4440
  ======
   4440

Ограничения:

Не допускается использование собственных операторов умножения, кроме как при использовании «удвоения», как указано в алгоритме. Другими словами, если вы используете оператор типа *, он может использоваться только для умножения только на 2.

Записи, которые не придерживаются этого, не будут рассматриваться, и пользователя будут сопровождать из помещения с картонной коробкой, полной их вещей. Каждая запись будет иметь код плюс тест, основанный на вашем идентификационном номере.

Это код гольф. Наименьшее количество байтов получит приз, славу и восхищение своих пэров ... (И, может быть, Ламборджини ... Я сказал "возможно"!)

Уолли Уэст
источник
5
«Фактическое умножение не должно происходить». - Это ненаблюдаемо. Вы можете ограничить использование некоторых символов (например, *или x), но невозможно определить, используется ли умножение или нет. За исключением этой части, задача интересная.
Возможно, вам следует либо попросить полное описание кода, доказывающего, что алгоритм реализован без умножения, ИЛИ неограниченного моделирования, которое обеспечивает желаемый результат. Но это выглядит как две разные проблемы для меня.
Арно
1
Как отмечается в песочнице, связаны, возможно, дураки . @FelixPalmen, да, это длинное умножение в двоичном виде.
Питер Тейлор,

Ответы:

8

Древесный уголь , 91 байт

≔⟦⟧τ≔⁰σNθNηWθ«⊞τ⪫  Iθ⊞υ⪫⎇﹪θ²  ¦[]Iη≔⁺σ∧﹪θ²ησ≔÷θ²θ≔⁺ηηη»⊞υ…=⁺²LIσ⊞υ⪫  Iσ←E⮌τ⮌ιM⌈EυLιLυ←E⮌υ⮌ι

Попробуйте онлайн!Ссылка на подробную версию кода. Объяснение:

≔⟦⟧τ≔⁰σ

Устанавливает tв пустой список и sв 0. ( uуже по умолчанию пустой список.)

NθNη

Вводит два числа.

Wθ«

Повторяется пока qненулевое.

   ⊞τ⪫  Iθ

Заверните qв отступ и добавьте его в список t.

   ⊞υ⪫⎇﹪θ²  ¦[]Iη

Оберните hв дополнение или в []зависимости от того, qявляется ли нечетным, и добавьте его в список u.

   ≔⁺σ∧﹪θ²ησ

Добавьте hк sесли qнечетно.

   ≔÷θ²θ

Целочисленное деление qна 2.

   ≔⁺ηηη»

Добавьте hк себе.

⊞υ…=⁺²LIσ

Добавьте в список подходящую строку =знаков u.

⊞υ⪫  Iσ

Добавьте дополненную сумму sв список u.

←E⮌τ⮌ι

Повернуть список t на 180 ° и распечатайте его вверх ногами, выровняв его по правому краю.

M⌈EυLιLυ←E⮌υ⮌ι

Переместите курсор так, чтобы при uвыравнивании по правому краю его верхний левый угол совпал с только что достигнутым верхним правым углом, и напечатайте выравнивание по uправому краю.

Нил
источник
Потрясающая работа. У тебя пока есть преимущество, @Neil. Где я могу узнать больше о языке, есть ли ссылка?
WallyWest
1
@WallyWest Заголовок связан со страницей GitHub, и оттуда вы можете прочитать вики для получения дополнительной информации.
Нил
8

Python 2 , 203 202 187 133 байта

a,b=input()
s=0
while a:print'%3s%9s'%(a,'[ %%dd] '[a%2::2]%b);s+=[0,b][a%2];a/=2;b*=2
print'%10s==\n%11s'%(''.rjust(len(`s`),'='),s)

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

Если я могу использовать *для умножения строк ( '='*R) и в качестве «селектора» (b*(a%2) вместо [0,b][a%2]), я получаю:

118 байт

a,b=input()
s=0
while a:print'%3s%9s'%(a,'[ %%dd] '[a%2::2]%b);s+=a%2*b;a/=2;b*=2
print'%10s==\n%11s'%('='*len(`s`),s)

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


Объяснение:

a,b=input()                   #Get input
L=len(`a`)                    #Get length of first number for adjusting text
l=[]                          #Output list
s=0                           #Sum
while a:
 B=['[%d]',' %d '][a%2]%b     #B is either '[b]' or ' b ' depending on if a is odd/even
 l+=[(`a`,B)]                 #Add a,B to output list
 s+=[0,b][a%2]                #Add b to sum if a is odd
 a/=2;                        #Halve a
 b*=2;                        #Double b
R=len(B)                      #Length of last B for adjusting output
l+=[('',''.rjust(R,'='))]     #Add double line ==== to output list
l+=[('','%d '%s)]             #Add sum to output list
for x,y in l:
 print x.rjust(L),y.rjust(R)  #Print adjusted numbers
TFeld
источник
189 байт
г-н Xcoder
4

Java (OpenJDK 8) , 353 316 267 214 210 байт

(a,b)->{int g=0;for(;a>0;g+=a%2*b,a/=2,b*=2)System.out.printf("%1$8d%2$10s\n",a,a%2<1?"["+b+"]":b+" ");System.out.printf("%1$19s%2$18s","".valueOf(new char[(int)Math.log10(g)+3]).replace("\0","=")+"\n",g+" ");}

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

Роберто Грэм
источник
1
214 байтов:(a,b)->{int g=0;for(;a>0;g+=a%2*b,a/=2,b*=2)System.out.printf("%1$8d%2$10s\n",a,a%2<1?"["+b+"]":" "+b+" ");System.out.printf("%1$19s%2$18s","".valueOf(new char[(int)Math.log10(g)+3]).replace("\0","=")+"\n",g+" ");}
Невай
@ Просто и a%2*bприятно, спасибо
Роберто Грэм,
4

Mathematica, 264 байта

(s=#;k=(i=IntegerLength)@s;t=#2;w=0;P=Print;T=Table;While[s>0,If[OddQ@s,P[""<>T[" ",k-i@s],s,"  ",""<>T[" ",i[s(t)]-i@t],t];w=w+t,P[""<>T[" ",k-i@s],s,""<>T[" ",i[s(t)]-i@t]," [",t,"]"]];s=Quotient[s,2];t=2t];P[" "<>T[" ",k],""<>T["=",i@w+2]];P["  "<>T[" ",k],w])&


вход

[19427]

выход

19   427  
 9   854  
 4 [1708]  
 2 [3416]  
 1  6832  
   ======  
    8113  
J42161217
источник
Вы могли бы, вероятно, сохранить колоссальный один байт, используя инфиксную нотацию s=Quotient[s,2]:)
numbermaniac
3

Perl 5 , 157 байт

155 байт кода + 2 флага командной строки ( -nl)

$\=<>;$w=y///c;$y=2+length$\<<((log)/log 2);while($_){$s+=$\if$_%2;printf"%${w}s %${y}s\n",$_,$_%2?$\.$":"[$\]";$_>>=1;$\<<=1}say$"x++$w,'='x$y;say$"x++$w,$s

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

Xcali
источник
3

JavaScript 2017, 221 байт

В основном проблема форматирования вывода

(a,b)=>{for(t=b,r=0,l=[],w=`${a}`.length;a;l.push([a,t]),a>>=1,t+=t)z=`${r+=a&1&&t}`.length+2;P=(s,w)=>`${s}`.padStart(w);return[...l.map(([a,b])=>P(a,w)+P(a&1?b+' ':`[${b}]`,z+1)),P('='.repeat(z),z-~w),P(r,z+w)].join`
`}

Меньше гольфа

(a, b) => {
  var w=`${a}`.length, r=0, l=[]
  while(a) {
    r += a&1 && b
    l.push([a,b])
    a >>= 1
    b += b
  }
  // algo complete, result in r, now display it and the steps in l[]
  var z=`${r}`.length+2
  var P= (s,w) => `${s}`.padStart(w)
  return [... l.map( ([a,b]) => P(a,w) + P(a&1?b+' ' : `[${b}]`, z+1) )
    , P('='.repeat(z), z+w+1)
    , P(r, z+w)
  ].join`\n`
}

Тестовое задание

var F=
(a,b)=>{for(t=b,r=0,l=[],w=`${a}`.length;a;l.push([a,t]),a>>=1,t+=t)z=`${r+=a&1&&t}`.length+2;P=(s,w)=>`${s}`.padStart(w);return[...l.map(([a,b])=>P(a,w)+P(a&1?b+' ':`[${b}]`,z+1)),P('='.repeat(z),z-~w),P(r,z+w)].join`
`}

function update(){
  var i=I.value, [a,b]=i.match(/\d+/g)
  O.textContent=F(+a,+b)
}

update()
<input id=I value='21x348' oninput='update()'><pre id=O></pre>

edc65
источник
просто возвращаюсь к этому вопросу ... что конкретно делает padStart? Я не узнаю этот метод ...
WallyWest
Было бы отстой, чтобы запустить это в IE! ;)
WallyWest
3

C, C ++, 319 313 301 299 байт

-8 байт благодаря Захари

Большое спасибо printfмагии, которую я только что узнал за 60 минут между изменениями

#include<string.h>
#include<stdio.h>
#define O printf("%*d %c%*d%c\n",5,a,a%2?32:91,9,b,a%2?32:93);
void m(int a,int b){int r=0,i=0;O while(a>1){r+=a%2*b;a/=2;b*=2;O}r+=b;char t[20],p[20];memset(t,0,20);memset(p,0,20);sprintf(t,"%d",r);memset(p,61,strlen(t)+2);printf("%*c%*s\n%*d",5,32,12,p,16,r);}

C ++ оптимизации, заменить заголовок stdio.hна cstdioи с string.hпомощью cstring, сохраняет 2 байта

Компиляция с MSVC требует добавить #pragma warning(disable:4996)для использованияsprintf

Тестирование с моим PPCG ID:

72 х 535 =>

   72 [      535]
   36 [     1070]
   18 [     2140]
    9       4280
    4 [     8560]
    2 [    17120]
    1      34240
          =======
           38520

Он соблюдает правила, цифры выровнены, а знаки равенства всегда будут на 2 знака больше, чем окончательное число. Пример с 17 x 34 =>

   17         34
    8 [       68]
    4 [      136]
    2 [      272]
    1        544
            =====
             578
HatsuPointerKun
источник
Я думаю, что вы можете изменить последние две строки #define O printf("%*d %c%*d%c\n",5,a,a%2?' ':'[',9,b,a%2?' ':']');иvoid m(int a,int b){int r=0,i=0;O while(a>1){r+=a%2*b;a/=2;b*=2;O}r+=b;char t[20],p[20];memset(t,0,20);memset(p,0,20);sprintf(t,"%d",r);for(;i<strlen(t)+2;++i)p[i]='=';printf("%*c%*s\n%*d",5,' ',12,p,16,r);}
Zacharý
Да, я знаю это, но почему это важно? Кроме того, приоритет %и *одинаковы, поэтому r+=a%2*bдолжно работать.
Захари
@ На самом деле Захари, я был не прав, ты прав
HatsuPointerKun
Вам даже нужно включить <cstdio>, разве вы не можете использовать тот же трюк, что и здесь ?
Захари
240 байт
floorcat
3

[Bash], 144 142 140 131 128 байт

Лучшее уважение к отображению, обратите внимание, что в конце есть пробел

read a b;for((;a;));{ ((a%2))&&((r+=b))&&x=$b\ ||x=[$b];printf %3s%9s\\n $a "$x"
((a/=2,b+=b));};printf %12s\\n =${r//?/=}= $r\ 

Первый ответ

read a b;while((a));do ((a%2))&&((r+=b))&&printf "%6s  %6s
" $a $b||printf "%6s [%6s]
" $a $b;((a/=2,b+=b));done;printf "%6s %7s
" \  ==== \  $r
Науэль Фуйе
источник
2

Haskell , 305 байт

i=iterate
s=show
l=length.s
a!b=zip((takeWhile(>0).i(`div`2))a)(i(*2)b)
a?b=sum[y|(x,y)<-a!b,rem x 2>0]
a%b=l(snd.last$a!b)
a#b=unlines$[(' '<$[1..l a-l x])++s x++(' '<$[-1..a%b-l y])++if mod x 2<1then show[y]else(' ':s y)|(x,y)<-a!b]++map((++)(' '<$[-1..l a+a%b-l(a?b)]))['='<$[1..l a+1+a%b],' ':(s$a?b)]

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

!Оператор создает два списка, ?вычисляет произведение. %и #используются для макета ASCII.

jferard
источник
1

C 205 201 190 183 156 150 143 байта

Это скомпилирует с предупреждениями как C89, и я не верю, что это действительный C99, но в итоге он оказывается меньше, чем версия HatsuPointerKun, так как он сохраняет байты, пропуская #include, не используя динамические длины для printf, поскольку они не нужны, & с помощьюlog10() для вычисления количества =необходимых:

r;m(a,b){r=0;while(a){printf(a%2?"%4d%10d\n":"%4d [%8d]\n",a,b);r+=a%2?b:0;a/=2;b<<=1;}printf("%15.*s\n%14d",(int)log10(r)+3,"==========",r);}

Как мой номер 64586 , я использовал эту тестовую программу для расчета 64 * 586:

#include <stdio.h>
int m(int a, int b);
int main(void)
{
    m(64, 586);
    putchar('\n');
}

И это выводит:

  64 [     586]
  32 [    1172]
  16 [    2344]
   8 [    4688]
   4 [    9376]
   2 [   18752]
   1     37504
        =======
         37504

редактировать

сохранено 4 байта по правилу "implicit int"

редактировать 2

сохранил 11 байтов, изменив do...while()цикл и переместив printf в цикл из макроса. Также должен работать правильно, еслиa=1 .

редактировать 3

сохранил 7 байтов и сделал код работать правильно.

редактировать 4

Сохранено 26 байт с некоторыми хитростями при печати.

редактировать 5

сэкономил 6 байтов, свернув дополнительные отступы в 1 число.

редактировать 6

сохранено 7 байт с помощью трюка printf с тернарным оператором и без объявления неиспользуемой переменной

JustinCB
источник
Отличная работа, Джастин! Надеемся увидеть больше от вас в ближайшие недели!
WallyWest
Спасибо. Я надеюсь сделать больше и в ближайшие недели.
JustinCB
1

Excel VBA, 183 байта

Функция анонимного непосредственного окна VBE, которая принимает данные из диапазона [A1:B1]и выводит их на консоль.

a=[A1]:b=[B1]:While a:c=a Mod 2=0:?Right(" "& a,2);Right("   "&IIf(c,"["&b &"]",b &" "),7):s=s+IIf(c,0,b):a=Int(a/2):b=b*2:Wend:?Right("     "&String(Len(s)+2,61),9):?Right("    "&s,8)

Ungolfed

Sub EthiopianMultiply(ByVal a As Integer, b As Integer)
    While a
        Let c = a Mod 2 = 0
        Debug.Print Right(" " & a, 2);
        Debug.Print Right("    " & IIf(c, "[" & b & "]", b & " "), 7)
        Let s = s + IIf(c, 0, b)
        Let a = Int(a / 2)
        Let b = Int(b * 2)
    Wend
    Debug.Print Right("     " & String(Len(s) + 2, 61), 9)
    Debug.Print Right("     " & s, 8)
End Sub

Выход

61   486 
30  [972]
15  1944 
 7  3888 
 3  7776 
 1 15552 
  =======
   29646
Тейлор Скотт
источник