Multiplication éthiopienne

17

Cette question est inspirée de cette réponse . Par coïncidence, j'avais l'habitude d'utiliser la multiplication éthiopienne quand j'étais enfant, mais je n'avais jamais connu le nom de la méthode jusqu'à récemment.

La multiplication éthiopienne est une méthode de multiplication d'entiers utilisant uniquement l'addition, le doublement et la réduction de moitié.

Méthode:

  1. Prenez deux nombres à multiplier et notez-les en haut de deux colonnes.
  2. Dans la colonne de gauche, divisez par deux à plusieurs reprises le dernier nombre, en supprimant tout reste et écrivez le résultat sous le dernier dans la même colonne, jusqu'à ce que vous écriviez une valeur de 1.
  3. Dans la colonne de droite, doublez plusieurs fois le dernier chiffre et écrivez le résultat ci-dessous. arrêtez lorsque vous ajoutez un résultat dans la même ligne que là où la colonne de gauche indique 1.
  4. Examinez le tableau produit et supprimez toute ligne où la valeur dans la colonne de gauche est paire. Additionnez les valeurs de la colonne de droite qui restent pour produire le résultat de la multiplication des deux nombres d'origine.

Par exemple: 17 x 34

17    34

Réduire de moitié la première colonne:

17    34
 8
 4
 2
 1

Doubler la deuxième colonne:

17    34
 8    68
 4   136 
 2   272
 1   544

Barrer les lignes dont la première cellule est paire, nous le ferons en mettant ces chiffres à droite entre crochets:

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

Additionnez les nombres restants dans la colonne de droite:

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

Donc 17 multiplié par 34, par la méthode éthiopienne est 578.

La tâche:

Code de golf qui prend deux nombres entre 1 et 1000 et exécute la même disposition et le même algorithme, affichant le produit ci-dessous.

Méthode d'entrée: Cependant, vous choisissez ...

Exemple d'entrée:

19 427

Résultat résultant:

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

Veuillez noter l'alignement des chiffres. C'est le plus important dans la mise en page. Notez également que la double ligne tracée par des signes égaux doit être de deux caractères plus longue que la réponse globale et doit être justifiée au centre.

Essai

Comment allez-vous tester cela? En fournissant une exécution de votre programme en utilisant deux nombres. Ces numéros peuvent être extraits de votre numéro d'utilisateur (vous pouvez les obtenir en plaçant votre curseur sur votre avatar dans la fenêtre supérieure). Prenez votre numéro et prenez les trois derniers chiffres, ce sera le numéro B, prenez tout ce qui reste à l'avant, ce sera le numéro A. Ensuite, testez A fois B.

Exemple de test:

Mon numéro d'identification d'utilisateur est 8555, donc mes numéros sont 8 et 555. Donc, ma sortie devrait ressembler à ceci:

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

Restrictions:

Aucun opérateur de multiplication natif n'est autorisé sauf dans l'utilisation du "doublage", comme mentionné dans l'algorithme. En d'autres termes, si vous utilisez un opérateur comme *, il ne peut être utilisé que pour la multiplication par 2 uniquement.

Les inscriptions qui n'y adhèrent pas ne seront pas prises en compte et l'utilisateur sera escorté hors des lieux avec une boîte en carton pleine de ses effets personnels. Chaque entrée aura un code, plus le test basé sur votre numéro d'identification d'utilisateur.

C'est le golf de code. Le plus petit nombre d'octets recevra le prix, la gloire et l'admiration de leurs pairs ... (Et peut-être une Lamborghini ... j'ai dit "peut-être"!)

WallyWest
la source
5
"Aucune multiplication réelle ne doit avoir lieu." - C'est inobservable. Vous pouvez restreindre l'utilisation de certains caractères (comme *ou x), mais il est impossible de détecter si la multiplication est utilisée ou non. Hormis cette partie, le défi est intéressant.
Vous devriez peut-être demander une description complète du code prouvant que l'algorithme est mis en œuvre sans multiplication OU une simulation sans restriction qui fournit la sortie souhaitée. Mais cela ressemble à deux défis distincts pour moi.
Arnauld, le
1
Comme indiqué dans le bac à sable, lié, possible dupe . @FelixPalmen, oui, c'est une longue multiplication en binaire.
Peter Taylor

Réponses:

8

Fusain , 91 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication:

≔⟦⟧τ≔⁰σ

Définit tsur la liste vide et ssur 0. ( udéjà par défaut dans la liste vide.)

NθNη

Saisit les deux nombres.

Wθ«

Se répète alors qu'il qest différent de zéro.

   ⊞τ⪫  Iθ

Enveloppez le qrembourrage et ajoutez-le à la liste t.

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

Enveloppez- hle dans du rembourrage ou []selon qu'il qest impair et ajoutez-le à la liste u.

   ≔⁺σ∧﹪θ²ησ

Ajouter hà ssi qest impair.

   ≔÷θ²θ

Entier divisé qpar 2.

   ≔⁺ηηη»

Ajoutez hà lui-même.

⊞υ…=⁺²LIσ

Ajoutez une chaîne de =signes appropriée à la liste u.

⊞υ⪫  Iσ

Ajoutez la somme rembourrée sà la liste u.

←E⮌τ⮌ι

Faites pivoter la liste tde 180 ° et imprimez-la à l'envers, la justifiant ainsi à droite.

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

Déplacez le curseur de sorte que lorsque uest justifié à droite, son coin supérieur gauche soit aligné avec le coin supérieur droit que nous venons d'atteindre, et imprimez ujustifié à droite.

Neil
la source
Excellent travail. Vous avez la tête jusqu'à présent, @Neil. Où puis-je en savoir plus sur la langue, y a-t-il un lien?
WallyWest
1
@WallyWest Le titre est lié à la page GitHub et à partir de là, vous pouvez lire le wiki pour plus d'informations.
Neil
8

Python 2 , 203 202 187 133 octets

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)

Essayez-le en ligne!

Si je peux utiliser *pour la multiplication de chaînes ( '='*R) et comme 'sélecteur' ( b*(a%2)au lieu de [0,b][a%2]), j'obtiens:

118 octets

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)

Essayez-le en ligne!


Explication:

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
la source
189 octets
M. Xcoder
4

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

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

Essayez-le en ligne!

Roberto Graham
la source
1
214 octets:(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*bsympa et simple, merci
Roberto Graham
4

Mathematica, 264 octets

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


contribution

[19,427]

production

19   427  
 9   854  
 4 [1708]  
 2 [3416]  
 1  6832  
   ======  
    8113  
J42161217
la source
Vous pourriez probablement économiser une somme exorbitante d' un octet en utilisant la notation infixe sur s=Quotient[s,2]:)
numbermaniac
3

Perl 5 , 157 octets

155 octets de code + 2 drapeaux de ligne de commande ( -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

Essayez-le en ligne!

Xcali
la source
3

JavaScript 2017, 221 octets

Surtout un problème de formatage de sortie

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

Moins golfé

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

Tester

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
la source
revisitant juste cette question ... qu'est-ce que padStart fait exactement? Je ne reconnais pas cette méthode ...
WallyWest
Serait nul d'exécuter cela dans IE! ;)
WallyWest
3

C, C ++, 319 313 301 299 octets

-8 octets grâce à Zacharý

Grand merci à la printfmagie que je viens d'apprendre en 60 minutes entre les éditions

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

Optimisation C ++, remplacez l'en-tête stdio.hpar cstdioet string.hpar cstring, économise 2 octets

La compilation avec MSVC nécessite d'ajouter #pragma warning(disable:4996)afin d'utilisersprintf

Test avec mon ID PPCG:

72 x 535 =>

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

Il respecte les règles, les chiffres sont alignés et les signes égaux seront toujours supérieurs de 2 caractères au nombre final. Exemple avec 17 x 34 =>

   17         34
    8 [       68]
    4 [      136]
    2 [      272]
    1        544
            =====
             578
HatsuPointerKun
la source
Je pense que vous pouvez changer les deux dernières lignes en #define O printf("%*d %c%*d%c\n",5,a,a%2?' ':'[',9,b,a%2?' ':']');etvoid 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ý
Oui, je le sais, mais pourquoi est-ce important?. Ad aussi, la priorité de %et *sont les mêmes, r+=a%2*bdevrait donc fonctionner.
Zacharý
@ Zacharý en fait, j'avais tort, vous avez raison
HatsuPointerKun
Avez-vous même besoin d'inclure <cstdio>, ne pouvez-vous pas utiliser la même astuce que vous avez fait ici ?
Zacharý
240 octets
Plafond
3

[Bash], 144 142 140 140 131 128 octets

Meilleur respect de l'affichage, notez qu'il y a un caractère d'espace de fin

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\ 

Première réponse

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
la source
2

Haskell , 305 octets

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

Essayez-le en ligne!

L' !opérateur crée les deux listes, ?calcule le produit. %et #sont utilisés pour la disposition ascii.

jferard
la source
1

C, 205 201 190 183 156 150 143 octets

Cela se compilera avec des avertissements en tant que C89, et je ne pense pas que ce soit un C99 valide, mais il finit par être plus petit que la version de HatsuPointerKun, car il économise des octets en omettant #include, sans utiliser de longueurs dynamiques pour imprimer car elles sont inutiles, et utiliser log10()pour calculer le nombre de =nécessaires:

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

Comme mon numéro est 64586, j'ai utilisé ce programme de test pour calculer 64 * 586:

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

& il génère:

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

Éditer

enregistré 4 octets par la règle "implicit int"

modifier 2

enregistré 11 octets en passant à une do...while()boucle et en déplaçant le printf dans la boucle à partir d'une macro. Devrait également fonctionner correctement sia=1 .

modifier 3

enregistré 7 octets et fait fonctionner le code correctement.

modifier 4

Sauvegardé 26 octets avec quelques astuces printf.

modifier 5

enregistré 6 octets en réduisant le remplissage supplémentaire en 1 nombre.

modifier 6

sauvé 7 octets par la supercherie printf avec l'opérateur ternaire et ne déclarant pas une variable inutilisée

JustinCB
la source
Excellent travail, Justin! Réjouissez-vous d'en voir plus dans les semaines à venir!
WallyWest
Je vous remercie. J'espère en faire plus dans les semaines à venir aussi.
JustinCB
1

Excel VBA, 183 octets

Une fonction de fenêtre immédiate VBE anonyme qui prend les entrées de la plage [A1:B1]et les sorties vers la console.

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)

Non golfé

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

Production

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