Penentu 2 2 matriks
a b
c d
diberikan oleh ad - bc
.
Diberikan matriks digit dengan dimensi 2 n oleh 2 n , n ≥ 1, output hasil yang diperoleh dengan menghitung secara rekursif penentu masing-masing 2 oleh 2 sub-blok sampai kita mencapai angka tunggal.
Misalnya diberi input
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
Setelah satu langkah, kami memperoleh:
(3*9 - 1*5) (4*6 - 1*2) = 22 22
(5*7 - 3*9) (5*3 - 8*9) 8 -57
Dan iterasi sekali lagi, kita dapatkan:
(22*-57 - 22*8) = -1430
Oleh karena itu, hasilnya harus -1430
.
Aturan
- Elemen-elemen dari matriks akan selalu berupa bilangan bulat satu digit, yaitu 0 hingga 9.
- Anda dapat mengambil input dalam format string atau daftar yang mudah, selama tidak ada pemrosesan data yang dilakukan. Karena matriks selalu persegi, Anda dapat mengambil input sebagai daftar 1D tunggal, bukan daftar 2D jika Anda mau.
- Input dapat melalui input fungsi, STDIN, argumen baris perintah atau alternatif terdekat.
- Output harus berupa bilangan bulat tunggal untuk berfungsi output, STDOUT atau alternatif terdekat. Anda tidak dapat mengeluarkan bilangan bulat tunggal dalam daftar atau matriks.
- Anda dapat menggunakan metode determinan dan manipulasi matriks bawaan jika bahasa Anda mendukungnya.
- Algoritme Anda harus bekerja secara teori untuk input yang valid.
- Aturan standar kode-golf berlaku.
Uji kasus
Kasing uji berikut diberikan sebagai daftar gaya-Python:
[[1,0],[0,1]] -> 1
[[1,9],[8,4]] -> -68
[[0,1,2,3],[4,5,6,7],[8,9,0,1],[2,3,4,5]] -> 40
[[3,1,4,1],[5,9,2,6],[5,3,5,8],[9,7,9,3]] -> -1430
[[9,0,0,9],[0,9,9,0],[9,0,9,0],[0,9,0,9]] -> 13122
[[1,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0],[3,2,1,0,0,0,0,0],[4,3,2,1,0,0,0,0],[5,4,3,2,1,0,0,0],[6,5,4,3,2,1,0,0],[7,6,5,4,3,2,1,0],[8,7,6,5,4,3,2,1]] -> 1
[[7,1,0,5,8,0,1,5],[9,9,6,6,1,2,4,8],[4,8,7,3,8,7,4,7],[4,6,1,9,7,0,1,7],[7,6,7,1,9,4,1,6],[8,0,0,8,5,5,9,9],[4,6,4,8,9,4,8,6],[9,0,8,7,6,2,1,5]] -> 2937504
[[1,2,3,4,5,6,7,8],[2,3,4,5,6,7,8,1],[3,4,5,6,7,8,1,2],[4,5,6,7,8,1,2,3],[5,6,7,8,1,2,3,4],[6,7,8,1,2,3,4,5],[7,8,1,2,3,4,5,6],[8,1,2,3,4,5,6,7]] -> -10549504
[[1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,1,0,1,1,1,1,1,1,0],[1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0],[0,1,1,1,1,0,0,0,0,1,1,1,1,1,0,1],[1,0,1,0,1,1,1,0,0,1,1,1,1,0,1,0],[0,0,1,1,1,0,1,1,1,1,1,1,1,0,0,0],[1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1],[1,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1],[1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1],[0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1],[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,0],[1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0],[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,0,1,0,0,1,0,1,0,1,1,1,1,1,0,1],[1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1]] -> -8
(Terima kasih kepada @ MartinBüttner untuk bantuan dengan tantangan ini)
[1,0,1,0;1,1,1,1;1,1,1,1;0,0,0,1]
. Penentu penuhnya adalah nol karena memiliki dua baris yang identik. Oleh karena itu, ini adalah matriks 4 × 4 singular (artinya tidak dapat dibalik), sehingga tidak dihitung oleh A055165. Namun, penentu "rekursif" yang dibahas di sini adalah1*1-1*0==1
. Dalam arah yang berlawanan, matriks[0,0,0,1;1,0,0,0;0,1,0,0;0,0,1,0]
memiliki penentu "rekursif"0*0-0*0==0
. Namun, penentu penuhnya harus non-nol karena barisnya hanya baris dari matriks identitas dalam urutan lain; dan itu dihitung oleh A055165.Jawaban:
J,
2125 bytePemakaian:
Pada setiap langkah kami memotong matriks menjadi 2-oleh-2 dan menghitung setiap penentu yang menghasilkan matriks input langkah selanjutnya. Kami ulangi proses ini sampai hasilnya tidak berubah (elemen terakhir adalah penentu itu sendiri). Kami mengonversi hasil akhir menjadi skalar dengan
0{0{
.Cobalah online di sini.
sumber
(2 2$2)&(-/ .*;._3^:(2^.#@]))
Cobalah online!Mathematica,
5240 byteTerima kasih kepada Martin Büttner karena telah menghemat 12 byte.
Penjelasan
BlockMap[f,expr,n]
dibagiexpr
menjadi sublists ukurann
dan petaf
di setiap sublists.BlockMap[Det,#,{2,2}]&
pisahkan array input menjadi 2 * 2 blok dan hitung determinannya.Kasus cobaan
sumber
[[1,1]]
denganTr
danNest
dengan//.
:Tr[#//.l:{_,__}:>BlockMap[Det,l,{2,2}]]&
Jelly,
2017 byteCobalah online! atau verifikasi semua kasus uji sekaligus .
Bagaimana itu bekerja
sumber
Haskell ,
9386 byteSUNTING: Terima kasih kepada @Laikoni untuk mempersingkat keseluruhan 7 byte ini!
Saya tidak tahu Anda bisa memberikan pernyataan let sebelum = dan saya tidak pernah terbiasa dengan operator monad itu. Terima kasih lagi @Laikoni
Versi lama:
Cobalah online!
Ini adalah fungsi yang berulang pada dirinya sendiri dalam dua cara berbeda. Pertama pencocokan pola menangkap kasus dasar: matriks 2x2 dan melakukan perhitungan. Saya menggunakan ini untuk melakukan perhitungan dalam kasus rekursif dengan memanggil fungsi dengan matriks 2x2 yang saya hasilkan yang memiliki solusi rekursif di dalamnya. Matriks itu dihasilkan dengan mengulangi dua kali lebih dari satu array fungsi yang masing-masing memotong daftar menjadi dua. Saya menerapkannya pada baris dengan panggilan sederhana dan menerapkannya ke kolom menggunakan
map
.sumber
where h=length m`div`2;l=[take h,drop h]
, Anda bisa menggunakanf m|let l=[take,drop]<*>[length m`div`2]=
.map b m
dapatb<$>m
, dan[f$a$b<$>m|a<-l]
dapat disingkat menjadif.($b<$>m)<$>l
. Secara keseluruhan 86 byte: [ tio.run/... Cobalah online!]Python, 166 byte
Ini melewati semua kasus uji yang disediakan. m harus berupa array 2D (seperti dalam kasus uji), g memilih sub matriks.
sumber
Pyth, 26
Test Suite
Ini memiliki dua bagian:
M-F*VG_H
mendefinisikan kembali fungsig
untuk menghitung determinan matriks dua demi dua. Ini menghemat byte meskipun kami hanya menggunakannya sekali karena membongkar dua baris.Bagian lainnya adalah pernyataan pengurangan besar yang kita sebut
log_2( len( input() ) )
waktu. Sayangnya, melakukan langkah dalam pengurangan pada matriks 1 oleh 1 menyebabkan hasilnya dibungkus dalam daftar, jadi kami tidak mendapatkan titik tetap. Pengurangan sebagian besar hanya membagi matriks untuk mendapatkan 2 oleh 2 matriks dan kemudian menerapkang
.sumber
MATL , 26
30byteInput adalah array 2D dengan baris yang dipisahkan oleh
;
, yaitu,Cobalah online!
sumber
Perl 5 , 120 + 1 (
-a
) = 121 byteCobalah online!
Mengambil input sebagai daftar angka yang dipisahkan spasi.
sumber
ES6, 91 byte
Solusi rekursif langsung.
sumber
R , 111 byte
Cobalah online!
Mengambil input sebagai matriks R (yang dikonversi oleh fungsi di header).
sumber
Groovy,
221189 bytes (Pada titik ini, bisa menggunakan Java)Versi jelek lama, yang mungkin juga Java (221 byte):
Kode tidak dikunci:
sumber