Äthiopische Multiplikation

17

Diese Frage ist von dieser Antwort inspiriert . Zufälligerweise verwendete ich als Kind die äthiopische Multiplikation, kannte aber den Namen der Methode bis vor kurzem nicht.

Die äthiopische Multiplikation ist eine Methode zur Multiplikation ganzer Zahlen, bei der nur Addition, Verdopplung und Halbierung verwendet werden.

Methode:

  1. Nimm zwei zu multiplizierende Zahlen und schreibe sie oben in zwei Spalten auf.
  2. In der linken Spalte halbieren Sie wiederholt die letzte Zahl, wobei Sie alle Reste verwerfen, und schreiben Sie das Ergebnis unter die letzte in derselben Spalte, bis Sie den Wert 1 schreiben.
  3. In der rechten Spalte immer wieder die letzte Zahl verdoppeln und das Ergebnis unten eintragen. stoppen Sie, wenn Sie ein Ergebnis in derselben Zeile hinzufügen, in der die linke Spalte 1 anzeigt.
  4. Untersuchen Sie die erzeugte Tabelle und verwerfen Sie alle Zeilen, in denen der Wert in der linken Spalte gerade ist. Addieren Sie die verbleibenden Werte in der rechten Spalte, um das Ergebnis der Multiplikation der beiden ursprünglichen Zahlen zu erhalten.

Zum Beispiel: 17 x 34

17    34

Die erste Spalte halbieren:

17    34
 8
 4
 2
 1

Verdoppelung der zweiten Spalte:

17    34
 8    68
 4   136 
 2   272
 1   544

Durchgestrichene Zeilen, deren erste Zelle gerade ist, tun dies, indem Sie diese Zahlen rechts in eckige Klammern setzen:

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

Summiere die verbleibenden Zahlen in der rechten Spalte:

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

Also ist 17 multipliziert mit 34 nach der äthiopischen Methode 578.

Die Aufgabe:

Golfcode, der zwei Zahlen zwischen 1 und 1000 annimmt und dasselbe Layout und denselben Algorithmus ausführt, wobei das folgende Produkt angezeigt wird.

Eingabemethode: Wie auch immer Sie wählen ...

Beispiel Eingabe:

19 427

Resultierende Ausgabe:

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

Bitte beachten Sie die Ausrichtung der Ziffern. Dies ist im Layout am wichtigsten. Beachten Sie auch, dass die durch Gleichheitszeichen dargestellte doppelte Linie zwei Zeichen länger sein muss als die Gesamtantwort und mittig ausgerichtet sein muss.

Testen

Wie werden Sie das testen? Indem Sie ein Programm ausführen, das zwei Zahlen verwendet. Diese Nummern können aus Ihrer Benutzer-ID-Nummer extrahiert werden (dies erhalten Sie, indem Sie den Mauszeiger über Ihren Avatar im oberen Fenster bewegen). Nehmen Sie Ihre Nummer und nehmen Sie die letzten drei Ziffern, dies ist die Nummer B, nehmen Sie alles, was vorne noch übrig ist, das ist die Nummer A. Dann testen Sie A mal B.

Testbeispiel:

Meine Benutzer-ID-Nummer ist 8555, meine Nummern sind also 8 und 555. Meine Ausgabe sollte also so aussehen:

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

Beschränkungen:

Es sind keine nativen Multiplikationsoperatoren zulässig, außer bei der Verwendung von "Verdopplung", wie im Algorithmus erwähnt. Mit anderen Worten, wenn Sie einen Operator wie * verwenden, kann dieser nur zum Multiplizieren mit 2 verwendet werden.

Beiträge, die sich nicht daran halten, werden nicht berücksichtigt und der Benutzer wird mit einem Pappkarton voller Habseligkeiten von den Räumlichkeiten begleitet. Jeder Eintrag enthält einen Code sowie den Test basierend auf Ihrer Benutzer-ID-Nummer.

Das ist Code Golf. Die kürzeste Anzahl von Bytes erhält den Preis, den Ruhm und die Bewunderung ihrer Kollegen ... (Und vielleicht ein Lamborghini ... Ich sagte "vielleicht"!)

WallyWest
quelle
5
Msgstr "Es darf keine tatsächliche Multiplikation stattfinden." - Das ist nicht zu beobachten. Sie können die Verwendung einiger Zeichen (wie *oder x) einschränken , aber es ist unmöglich zu erkennen, ob Multiplikation verwendet wird oder nicht. Abgesehen von diesem Teil ist die Herausforderung interessant.
Vielleicht sollten Sie entweder eine vollständige Beschreibung des Codes anfordern, um zu beweisen, dass der Algorithmus ohne Multiplikation implementiert ist, ODER eine uneingeschränkte Simulation, die die gewünschte Ausgabe liefert. Aber das sieht für mich nach zwei unterschiedlichen Herausforderungen aus.
Arnauld
1
Wie im Sandkasten vermerkt, damit verbunden, möglicher Betrug . @FelixPalmen, ja, das ist lange Multiplikation in Binär.
Peter Taylor

Antworten:

8

Kohle , 91 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

≔⟦⟧τ≔⁰σ

Setzt tauf die leere Liste und sauf 0. ( uStandardmäßig ist die Liste bereits leer.)

NθNη

Gibt die beiden Zahlen ein.

Wθ«

Wiederholt, solange qungleich Null ist.

   ⊞τ⪫  Iθ

Wickeln Sie die qFüllung ein und hängen Sie sie an die Liste an t.

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

Wickeln Sie sie hentweder in Auffüllung oder, []je nachdem, ob sie qungerade ist, in die Liste ein und hängen Sie sie an u.

   ≔⁺σ∧﹪θ²ησ

Add hto sif qist ungerade.

   ≔÷θ²θ

Ganze Zahl qdurch 2 teilen .

   ≔⁺ηηη»

hZu sich selbst hinzufügen .

⊞υ…=⁺²LIσ

Fügen Sie =der Liste eine geeignete Zeichenfolge hinzu u.

⊞υ⪫  Iσ

Hängen Sie die aufgefüllte Summe san die Liste an u.

←E⮌τ⮌ι

Drehen Sie die Liste tum 180 ° und drucken Sie sie kopfüber aus.

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

Bewegen Sie den Cursor so, dass useine linke obere Ecke mit der rechten oberen Ecke übereinstimmt, die wir gerade erreicht haben, und drucken Sie sie urechtsbündig aus.

Neil
quelle
Erstaunliche Arbeit. Sie haben bisher die Führung, @Neil. Wo kann ich mehr über die Sprache erfahren? Gibt es einen Link?
WallyWest
1
@WallyWest Der Titel ist mit der GitHub-Seite verknüpft und von dort aus können Sie das Wiki lesen, um weitere Informationen zu erhalten.
Neil
8

Python 2 , 203 202 187 133 Bytes

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)

Probieren Sie es online!

Wenn ich *zur Zeichenkettenmultiplikation ( '='*R) und als 'Selektor' ( b*(a%2)anstelle von[0,b][a%2] ) verwenden kann, erhalte ich:

118 Bytes

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)

Probieren Sie es online!


Erläuterung:

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
quelle
189 Bytes
Mr. Xcoder
4

Java (OpenJDK 8) , 353 316 267 214 210 Bytes

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

Probieren Sie es online!

Roberto Graham
quelle
1
214 Bytes:(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
@Nevay a%2*bschön und einfach, danke
Roberto Graham
4

Mathematica, 264 Bytes

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


Eingang

[19,427]

Ausgabe

19   427  
 9   854  
 4 [1708]  
 2 [3416]  
 1  6832  
   ======  
    8113  
J42161217
quelle
Sie könnten wahrscheinlich sparen satte ein Byte für Infix - Notation auf s=Quotient[s,2]:)
numbermaniac
3

Perl 5 , 157 Bytes

155 Byte Code + 2 Befehlszeilenflags ( -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

Probieren Sie es online!

Xcali
quelle
3

JavaScript 2017, 221 Byte

Meistens ein Problem der Ausgabeformatierung

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

Weniger golfen

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

Prüfung

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
quelle
Ich überlege nur, was PadStart genau macht. Ich erkenne diese Methode nicht ...
WallyWest
Wäre zum Kotzen das im IE laufen zu lassen! ;)
WallyWest
3

C, C ++, 319 313 301 299 Bytes

-8 Bytes dank Zacharý

Dank der printfMagie habe ich es in 60 Minuten zwischen den Bearbeitungen gelernt

#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 ++ - Optimierung, Header stdio.hnach cstdiound string.hnach ersetzen cstring, spart 2 Byte

Das Kompilieren mit MSVC erfordert das Hinzufügen, #pragma warning(disable:4996)um es verwenden zu könnensprintf

Testen mit meiner PPCG ID:

72 x 535 =>

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

Die Regeln werden eingehalten, die Ziffern werden ausgerichtet und die Gleichheitszeichen sind immer 2 Zeichen größer als die endgültige Zahl. Beispiel mit 17 x 34 =>

   17         34
    8 [       68]
    4 [      136]
    2 [      272]
    1        544
            =====
             578
HatsuPointerKun
quelle
Ich denke, Sie können die letzten beiden Zeilen auf #define O printf("%*d %c%*d%c\n",5,a,a%2?' ':'[',9,b,a%2?' ':']');undvoid 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ý
Ja, das weiß ich, aber warum ist das wichtig? Ad auch, der Vorrang von %und *sind die gleichen, r+=a%2*bsollte also funktionieren.
Zacharý
@ Zacharý in der Tat war ich falsch, du hast Recht
HatsuPointerKun
Müssen Sie überhaupt <cstdio> einschließen, können Sie nicht denselben Trick verwenden, den Sie hier gemacht haben ?
Zacharý
240 Bytes
Ceilingcat
3

[Bash], 144 142 140 131 128 Bytes

Beachten Sie bei der Anzeige, dass ein Leerzeichen nachgestellt ist

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\ 

Erste Antwort

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
quelle
2

Haskell , 305 Bytes

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

Probieren Sie es online!

Der !Bediener erstellt die beiden Listen und ?berechnet das Produkt. %und #werden für das ASCII-Layout verwendet.

jferard
quelle
1

C 205 201 190 183 156 150 143 Bytes

Dies wird mit Warnungen wie C89 kompiliert, und ich glaube nicht, dass es C99 ist, aber es wird kleiner als die Version von HatsuPointerKun, da es Bytes spart, indem es #includekeine dynamischen Längen verwendet, um zu drucken , wenn sie nicht benötigt werden. Verwenden Sie log10(), um die Anzahl der =benötigten zu berechnen :

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

Wie meine Nummer ist 64586, habe ich dieses Testprogramm verwendet, um Folgendes zu berechnen 64 * 586:

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

& es gibt aus:

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

bearbeiten

4 Bytes durch die "implicit int" -Regel gespart

bearbeiten 2

11 Bytes gespart, indem in eine do...while()Schleife gewechselt und das printf aus einem Makro in die Schleife verschoben wurde. Sollte auch richtig funktionieren wenna=1 .

bearbeiten 3

7 Bytes gespart und der Code funktioniert.

bearbeiten 4

Sparte 26 Bytes mit einigem printf-Trick.

bearbeiten 5

6 Bytes gespart, indem zusätzliches Auffüllen in 1 Zahl reduziert wurde.

bearbeiten 6

7 Bytes durch printf-Trick mit dem ternären Operator gespart und keine unbenutzte Variable deklariert

JustinCB
quelle
Großartige Arbeit, Justin! Freuen Sie sich darauf, in den kommenden Wochen mehr von Ihnen zu sehen!
WallyWest
Vielen Dank. Ich hoffe, dass ich in den kommenden Wochen auch mehr tun kann.
JustinCB
1

Excel VBA, 183 Bytes

Eine anonyme VBE-Direktfensterfunktion, die Eingaben aus dem Bereich [A1:B1]und Ausgaben an die Konsole weiterleitet.

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

Ausgabe

61   486 
30  [972]
15  1944 
 7  3888 
 3  7776 
 1 15552 
  =======
   29646
Taylor Scott
quelle