Etiopskie mnożenie

17

To pytanie jest inspirowane tą odpowiedzią . Przypadkowo, kiedy byłem dzieckiem, używałem mnożenia etnicznego, ale do niedawna nie znałem nazwy tej metody.

Etiopskie mnożenie to metoda mnożenia liczb całkowitych przy użyciu tylko dodawania, podwajania i zmniejszania o połowę.

Metoda:

  1. Weź dwie liczby do pomnożenia i zapisz je u góry dwóch kolumn.
  2. W lewej kolumnie kilkakrotnie zmniejsz o połowę ostatnią liczbę, odrzucając resztki i zapisz wynik poniżej ostatniej w tej samej kolumnie, aż zapiszesz wartość 1.
  3. W prawej kolumnie wielokrotnie powtarzaj ostatnią liczbę i wpisz wynik poniżej. zatrzymaj się, gdy dodasz wynik w tym samym wierszu, w którym w lewej kolumnie pokazuje 1.
  4. Sprawdź wyprodukowaną tabelę i odrzuć każdy wiersz, w którym wartość w lewej kolumnie jest parzysta. Zsumuj wartości w prawej kolumnie, które pozostały, aby uzyskać wynik pomnożenia dwóch oryginalnych liczb.

Na przykład: 17 x 34

17    34

Zmniejszenie o połowę pierwszej kolumny:

17    34
 8
 4
 2
 1

Podwojenie drugiej kolumny:

17    34
 8    68
 4   136 
 2   272
 1   544

Przekreśl wiersze, których pierwsza komórka jest parzysta, zrobimy to, umieszczając liczby po prawej stronie w nawiasach kwadratowych:

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

Zsumuj pozostałe liczby w prawej kolumnie:

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

Zatem 17 pomnożone przez 34, metodą etiopską jest 578.

Zadanie:

Kod golfowy, który przyjmuje dwie liczby od 1 do 1000 i wykonuje ten sam układ i algorytm, wyświetlając produkt poniżej.

Metoda wprowadzania: jednak wybierasz ...

Przykładowe dane wejściowe:

19 427

Wynikowy wynik:

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

Zwróć uwagę na wyrównanie cyfr. Jest to najważniejsze w układzie. Zauważ również, że podwójna linia ułożona znakami równości musi być o dwa znaki dłuższa niż ogólna odpowiedź i musi być wyśrodkowana.

Testowanie

Jak będziesz to testować? Udostępniając przebieg programu za pomocą dwóch liczb. Liczby te można wyodrębnić z numeru identyfikacyjnego użytkownika (można to uzyskać, najeżdżając kursorem na awatar w górnym oknie). Weź swój numer i weź trzy ostatnie cyfry, będzie to liczba B, weź wszystko, co pozostanie z przodu, to będzie liczba A. Następnie sprawdź A razy B.

Przykład testowy:

Mój numer identyfikacyjny użytkownika to 8555, więc moje numery to 8 i 555. Więc moje dane wyjściowe powinny wyglądać następująco:

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

Ograniczenia:

Żadne natywne operatory mnożenia nie są dozwolone, z wyjątkiem „podwajania”, jak wspomniano w algorytmie. Innymi słowy, jeśli używasz operatora takiego jak *, można go użyć tylko do pomnożenia przez 2.

Zgłoszenia niezgodne z powyższym nie będą brane pod uwagę, a użytkownik zostanie wyprowadzony z lokalu z tekturowym pudełkiem pełnym swoich rzeczy. Każdy wpis będzie miał kod plus test oparty na numerze identyfikacyjnym użytkownika.

To jest kod golfowy. Najmniejsza liczba bajtów otrzyma nagrodę, chwałę i podziw swoich rówieśników ... (A może Lamborghini ... Powiedziałem „może”!)

WallyWest
źródło
5
„Nie może mieć miejsca faktyczne pomnożenie”. - To nie można zaobserwować. Możesz ograniczyć użycie niektórych znaków (takich jak *lub x), ale nie można wykryć, czy używane jest mnożenie. Oprócz tej części wyzwanie jest interesujące.
Być może powinieneś albo poprosić o pełny opis kodu dowodzący, że algorytm jest implementowany bez mnożenia LUB nieograniczoną symulację, która zapewnia pożądany wynik. Ale to wygląda dla mnie na dwa różne wyzwania.
Arnauld
1
Jak zauważono w piaskownicy, powiązany, możliwy duplikat . @ FelixPalmen, tak, to długie mnożenie w formacie binarnym.
Peter Taylor,

Odpowiedzi:

8

Węgiel drzewny , 91 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

≔⟦⟧τ≔⁰σ

Ustawia tna pustą listę i sna 0. ( udomyślnie jest to pusta lista).

NθNη

Wprowadza dwie liczby.

Wθ«

Powtarza się, gdy qjest niezerowy.

   ⊞τ⪫  Iθ

Zawiń qpadding i dodaj go do listy t.

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

Zawiń hw wypełnienie lub w []zależności od tego, czy qjest nieparzysty, i dołącz go do listy u.

   ≔⁺σ∧﹪θ²ησ

Dodaj hdo sjeśli qjest nieparzyste.

   ≔÷θ²θ

Liczba całkowita podziel qprzez 2.

   ≔⁺ηηη»

Dodaj hdo siebie.

⊞υ…=⁺²LIσ

Dodaj odpowiedni ciąg =znaków do listy u.

⊞υ⪫  Iσ

Dołącz wyściełaną sumę sdo listy u.

←E⮌τ⮌ι

Obróć listę to 180 ° i wydrukuj ją do góry nogami, w ten sposób uzasadniając ją.

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

Przesuń kursor, aby w przypadku uwyrównania do prawej jego lewy górny róg wyrównał się z prawym górnym narożnikiem, do którego właśnie dotarliśmy, i wydrukuj wyrównanie do uprawej.

Neil
źródło
Wspaniała robota. Jak dotąd masz przewagę, @Neil. Gdzie mogę dowiedzieć się więcej o języku, czy istnieje link?
WallyWest,
1
@WallyWest Tytuł jest powiązany ze stroną GitHub, a stamtąd możesz przeczytać wiki, aby uzyskać więcej informacji.
Neil
8

Python 2 , 203 202 187 133 bajtów

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)

Wypróbuj online!

Jeśli mogę użyć *do mnożenia ciągów ( '='*R) i jako „selektora” ( b*(a%2)zamiast [0,b][a%2]), otrzymuję:

118 bajtów

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)

Wypróbuj online!


Wyjaśnienie:

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
źródło
189 bajtów
Mr. Xcoder,
4

Java (OpenJDK 8) , 353 316 267 214 210 bajtów

(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+" ");}

Wypróbuj online!

Roberto Graham
źródło
1
214 bajtów:(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+" ");}
Nevay
@Nigdy nie a%2*bmiłe i proste, dziękuję
Roberto Graham
4

Mathematica, 264 bajty

(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])&


Wejście

[19,427]

wynik

19   427  
 9   854  
 4 [1708]  
 2 [3416]  
 1  6832  
   ======  
    8113  
J42161217
źródło
Prawdopodobnie można by zaoszczędzić jeden bajt, używając notacji s=Quotient[s,2]
infix
3

Perl 5 , 157 bajtów

155 bajtów kodu + 2 flagi wiersza poleceń ( -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

Wypróbuj online!

Xcali
źródło
3

JavaScript 2017, 221 bajtów

Głównie problem z formatowaniem wyjściowym

(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`
`}

Mniej golfa

(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`
}

Test

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
źródło
powracając do tego pytania ... co dokładnie robi padStart? Nie znam tej metody ...
WallyWest
Chciałbym uruchomić to w IE! ;)
WallyWest
3

C, C ++, 319 313 301 299 bajtów

-8 bajtów dzięki Zacharýowi

Wielkie dzięki printfmagii właśnie nauczyłem się w 60 minut między edycjami

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

Optymalizacja C ++ zastąpić nagłówek stdio.hprzez cstdioi string.hprzez cstring, oszczędza 2 bajt

Kompilacja z MSVC wymaga dodania #pragma warning(disable:4996)w celu użyciasprintf

Testowanie przy użyciu mojego identyfikatora PPCG:

72 x 535 =>

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

Przestrzega zasad, cyfry są wyrównane, a znaki równości zawsze będą o 2 znaki większe niż końcowa liczba. Przykład z 17 x 34 =>

   17         34
    8 [       68]
    4 [      136]
    2 [      272]
    1        544
            =====
             578
HatsuPointerKun
źródło
Myślę, że możesz zmienić dwie ostatnie linie na #define O printf("%*d %c%*d%c\n",5,a,a%2?' ':'[',9,b,a%2?' ':']');ivoid 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ý
Tak, wiem o tym, ale dlaczego to ma znaczenie ?. Poza tym pierwszeństwo %i *są takie same, więc r+=a%2*bpowinno działać.
Zacharý
@ Zacharý w rzeczywistości, myliłem się, masz rację
HatsuPointerKun
Czy w ogóle potrzebujesz dołączyć <cstdio>, czy nie możesz użyć tej samej sztuczki, którą tutaj zrobiłeś ?
Zacharý
240 bajtów
ceilingcat
3

[Bash], 144 142 140 131 128 bajtów

Lepszy szacunek wyświetlania, zauważ, że jest spacja

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\ 

Pierwsza odpowiedź

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
Nahuel Fouilleul
źródło
2

Haskell , 305 bajtów

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

Wypróbuj online!

!Operator tworzy dwie listy, ?oblicza produkt. %i #są używane do układu ascii.

Jferard
źródło
1

C, 205 201 190 183 156 150 143 bajtów

Spowoduje to kompilację z ostrzeżeniami jako C89 i nie sądzę, że jest to poprawny C99, ale ostatecznie jest mniejszy niż wersja HatsuPointerKun, ponieważ oszczędza bajty przez ominięcie #include , nie używając dynamicznych długości do printf, ponieważ są niepotrzebne, i za pomocą log10()do obliczenia liczby =potrzebnych:

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

Jak mój numer to 64586 , użyłem tego programu testowego do obliczenia 64 * 586:

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

i wyprowadza:

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

edytować

zapisane 4 bajty według reguły „domyślnej int”

edycja 2

zapisano 11 bajtów, przechodząc do do...while()pętli i przenosząc printf do pętli z makra. Powinien również działać poprawnie, jeślia=1 .

edycja 3

zapisałem 7 bajtów i poprawiłem działanie kodu.

edycja 4

Zaoszczędzono 26 bajtów dzięki pewnym sztuczkom związanym z printf.

edycja 5

zaoszczędzono 6 bajtów, składając dodatkowe wypełnienie w 1 cyfrę.

edycja 6

zapisano 7 bajtów przez trickf printf z operatorem trójskładnikowym i nie deklarując nieużywanej zmiennej

JustinCB
źródło
Świetna robota, Justin! Czekamy na więcej od Ciebie w nadchodzących tygodniach!
WallyWest
Dziękuję Ci. Mam nadzieję, że w nadchodzących tygodniach zrobię więcej.
JustinCB
1

Excel VBA, 183 bajty

Anonimowa funkcja bezpośredniego okna VBE, która pobiera dane wejściowe z zakresu [A1:B1]i dane wyjściowe do konsoli.

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)

Bez golfa

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

Wynik

61   486 
30  [972]
15  1944 
 7  3888 
 3  7776 
 1 15552 
  =======
   29646
Taylor Scott
źródło