Multiplikasi Ethiopia

17

Pertanyaan ini terinspirasi oleh jawaban ini . Secara kebetulan, saya biasa menggunakan Penggandaan Ethiopia ketika saya masih kecil, tetapi belum pernah tahu nama metode ini sampai saat ini.

Perkalian Ethiopia adalah metode mengalikan bilangan bulat dengan hanya menggunakan penjumlahan, penggandaan, dan separuh.

Metode:

  1. Ambil dua angka untuk dikalikan dan tuliskan di atas dua kolom.
  2. Di kolom sebelah kiri berulang kali membagi dua angka terakhir, membuang sisa, dan menulis hasilnya di bawah yang terakhir di kolom yang sama, sampai Anda menulis nilai 1.
  3. Di kolom kanan berulang kali gandakan angka terakhir dan tulis hasilnya di bawah ini. berhenti ketika Anda menambahkan hasil di baris yang sama dengan tempat kolom sebelah kiri menunjukkan 1.
  4. Periksa tabel yang dihasilkan dan buang baris mana pun yang nilainya berada di kolom kiri. Jumlahkan nilai di kolom kanan yang tetap menghasilkan hasil dari mengalikan dua angka asli bersama-sama.

Misalnya: 17 x 34

17    34

Membagi dua kolom pertama:

17    34
 8
 4
 2
 1

Menggandakan kolom kedua:

17    34
 8    68
 4   136 
 2   272
 1   544

Baris pemogokan yang sel pertamanya genap, kita akan melakukan ini dengan membungkus angka-angka di sebelah kanan dalam tanda kurung siku:

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

Jumlahkan angka yang tersisa di kolom kanan:

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

Jadi 17 dikalikan 34, dengan metode Ethiopia adalah 578.

Tugas:

Kode golf yang mengambil dua angka antara 1 dan 1000 dan melakukan tata letak dan algoritma yang sama, menampilkan produk di bawah ini.

Metode Input: Namun Anda memilih ...

Input Contoh:

19 427

Output yang dihasilkan:

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

Harap perhatikan penyelarasan digit. Ini paling penting dalam tata letak. Perhatikan juga bahwa garis ganda yang disusun oleh tanda sama harus dua karakter lebih panjang dari jawaban keseluruhan dan harus dibenarkan tengah.

Pengujian

Bagaimana Anda akan menguji ini? Dengan menjalankan program Anda menggunakan dua angka. Angka-angka ini dapat diekstraksi dari nomor ID pengguna Anda (ini dapat diperoleh dengan mengarahkan kursor Anda di atas avatar Anda di jendela atas). Ambil nomor Anda dan ambil tiga digit terakhir, ini akan menjadi nomor B, ambil apa pun yang tersisa di depan, yang akan menjadi nomor A. Kemudian uji A kali B.

Contoh pengujian:

Nomor ID pengguna saya adalah 8555, jadi angka saya adalah 8 dan 555. Jadi output saya akan terlihat seperti ini:

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

Pembatasan:

Tidak ada operator perkalian asli yang diizinkan untuk disimpan dalam penggunaan "penggandaan", sebagaimana disebutkan dalam algoritma. Dengan kata lain, jika Anda menggunakan operator seperti *, itu hanya dapat digunakan untuk mengalikan dengan 2 saja.

Entri yang tidak mematuhi ini tidak akan dipertimbangkan dan pengguna akan diantar keluar dari tempat itu dengan kotak kardus yang penuh dengan barang-barang mereka. Setiap entri akan memiliki kode, ditambah tes berdasarkan pada nomor ID pengguna Anda.

Ini kode golf. Jumlah byte terpendek akan menerima hadiah, kemuliaan, dan kekaguman dari rekan-rekan mereka ... (Dan mungkin sebuah Lamborghini ... Aku berkata "mungkin"!)

WallyWest
sumber
5
"Tidak ada penggandaan yang sebenarnya harus terjadi." - Ini tidak bisa diobservasi. Anda dapat membatasi penggunaan beberapa karakter (suka *atau x), tetapi tidak mungkin untuk mendeteksi apakah perkalian digunakan atau tidak. Kecuali bagian itu, tantangannya menarik.
Mungkin Anda harus meminta deskripsi lengkap dari kode yang membuktikan bahwa algoritme diimplementasikan tanpa perkalian ATAU simulasi tak terbatas yang memberikan hasil yang diinginkan. Tapi itu tampak seperti dua tantangan berbeda bagi saya.
Arnauld
1
Sebagaimana dicatat dalam kotak pasir, terkait, kemungkinan dupe . @ Feliksman, ya, ini adalah perkalian panjang dalam biner.
Peter Taylor

Jawaban:

8

Arang , 91 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Penjelasan:

≔⟦⟧τ≔⁰σ

Atur tke daftar kosong dan ske 0. ( usudah default ke daftar kosong.)

NθNη

Masukkan dua angka.

Wθ«

Mengulang sementara qbukan nol.

   ⊞τ⪫  Iθ

Bungkus qpadding dan tambahkan ke daftar t.

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

Bungkus hdengan bantalan atau []tergantung pada apakah qitu aneh, dan tambahkan ke daftar u.

   ≔⁺σ∧﹪θ²ησ

Tambahkan hke sjika qaneh.

   ≔÷θ²θ

Membagi integer qdengan 2.

   ≔⁺ηηη»

Tambahkan hke dirinya sendiri.

⊞υ…=⁺²LIσ

Tambahkan serangkaian =tanda yang sesuai ke daftar u.

⊞υ⪫  Iσ

Tambahkan jumlah padded ske daftar u.

←E⮌τ⮌ι

Putar daftar tdengan 180 ° dan cetak terbalik, sehingga membenarkannya.

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

Pindahkan kursor sehingga ketika udibenarkan kanan sudut kiri atas ke atas dengan sudut kanan atas yang baru saja kita capai, dan cetak udibenarkan kanan.

Neil
sumber
Pekerjaan yang luar biasa. Anda memiliki petunjuk sejauh ini, @Neil. Di mana saya bisa mengetahui lebih banyak tentang bahasa, apakah ada tautan?
WallyWest
1
@WallyWest Judulnya terhubung ke halaman GitHub dan dari sana Anda dapat membaca wiki untuk informasi lebih lanjut.
Neil
8

Python 2 , 203 202 187 133 byte

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)

Cobalah online!

Jika saya bisa menggunakannya * untuk perkalian string ( '='*R) dan sebagai 'pemilih' ( b*(a%2)bukan [0,b][a%2]), saya mendapatkan:

118 byte

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)

Cobalah online!


Penjelasan:

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
sumber
189 byte
Mr. Xcoder
4

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

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

Cobalah online!

Roberto Graham
sumber
1
214 byte:(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
@ Tidak pernah a%2*bmenyenangkan dan sederhana, terima kasih
Roberto Graham
4

Mathematica, 264 byte

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


memasukkan

[19.427]

keluaran

19   427  
 9   854  
 4 [1708]  
 2 [3416]  
 1  6832  
   ======  
    8113  
J42161217
sumber
Anda mungkin dapat menyimpan satu byte kekalahan dengan menggunakan notasi infix pada s=Quotient[s,2]:)
numbermaniac
3

Perl 5 , 157 byte

155 byte kode + 2 bendera baris perintah (-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

Cobalah online!

Xcali
sumber
3

JavaScript 2017, 221 byte

Sebagian besar masalah pemformatan output

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

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

Uji

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
sumber
hanya meninjau kembali pertanyaan ini ... apa tepatnya yang dilakukan padStart? Saya tidak mengenali metode ini ...
WallyWest
Akan payah menjalankan ini di IE! ;)
WallyWest
3

C, C ++, 319 313 301 299 byte

-8 Bytes berkat Zacharý

Terima kasih banyak untuk printfsulap yang baru saya pelajari dalam 60 menit di antara suntingan

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

Optimasi C ++, ganti header stdio.hdengan cstdiodan string.holehcstring , menghemat 2 byte

Kompilasi dengan MSVC perlu ditambahkan #pragma warning(disable:4996)untuk digunakansprintf

Menguji dengan ID PPCG saya:

72 x 535 =>

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

Itu menghormati aturan, angka disejajarkan, dan tanda-tanda yang sama akan selalu 2 char lebih besar dari angka terakhir. Contoh dengan 17 x 34 =>

   17         34
    8 [       68]
    4 [      136]
    2 [      272]
    1        544
            =====
             578
HatsuPointerKun
sumber
Saya pikir Anda dapat mengubah dua baris terakhir ke #define O printf("%*d %c%*d%c\n",5,a,a%2?' ':'[',9,b,a%2?' ':']');danvoid 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ý
Ya, saya tahu itu, tetapi mengapa itu penting? Ad juga, diutamakan %dan *sama, jadi r+=a%2*bharus bekerja.
Zacharý
@ Zacharý sebenarnya, saya salah, Anda benar
HatsuPointerKun
Apakah Anda bahkan perlu memasukkan <cstdio>, tidak bisakah Anda menggunakan trik yang sama dengan yang Anda lakukan di sini ?
Zacharý
240 bytes
ceilingcat
3

[Bash], 144 142 140 131 128 byte

Lebih baik menghormati tampilan, perhatikan ada karakter spasi tambahan

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\ 

Jawaban pertama

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

Haskell , 305 byte

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

Cobalah online!

The !Operator menciptakan dua daftar, ?menghitung produk. %dan #digunakan untuk tata letak ascii.

jferard
sumber
1

C, 205 201 190 183 156 150 143 byte

Ini akan dikompilasi dengan peringatan sebagai C89, & Saya tidak percaya itu C99 yang valid, tetapi akhirnya lebih kecil dari versi HatsuPointerKun, karena menghemat byte dengan mengomit #include, tidak menggunakan panjang dinamis untuk mencetak karena mereka tidak dibutuhkan, & menggunakanlog10() untuk menghitung jumlah yang =dibutuhkan:

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

Karena nomor saya 64586, saya menggunakan program tes ini untuk menghitung64 * 586 :

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

& itu keluaran:

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

sunting

disimpan 4 byte oleh aturan "int implisit"

edit 2

menyimpan 11 byte dengan mengubah ke do...while()loop & memindahkan printf ke loop dari makro. Juga harus bekerja dengan benar jika a=1.

edit 3

menyimpan 7 byte & membuat kode berfungsi dengan benar.

edit 4

Menyimpan 26 byte dengan tipu daya printf.

sunting 5

disimpan 6 byte dengan mengecilkan padding tambahan menjadi 1 nomor.

sunting 6

disimpan 7 byte oleh tipuan printf dengan operator ternary & tidak mendeklarasikan variabel yang tidak digunakan

JustinCB
sumber
Kerja bagus, Justin! Nantikan melihat lebih banyak dari Anda di minggu-minggu mendatang!
WallyWest
Terima kasih. Saya berharap dapat melakukan lebih banyak lagi di minggu-minggu mendatang.
JustinCB
1

Excel VBA, 183 byte

Fungsi jendela langsung VBE anonim yang mengambil input dari jangkauan [A1:B1]dan keluaran ke konsol.

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)

Tidak disatukan

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

Keluaran

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