( terkait )
Sebuah Pythagoras Tiga adalah daftar (a, b, c)
yang memenuhi persamaan a 2 + b 2 = c 2 .
Sebuah primitif Pythagoras Tiga (PPT) adalah salah satu tempat a
, b
dan c
semua coprime (yaitu, pembagi hanya umum antara tiga unsur adalah 1
). Misalnya, (3, 4, 5)
segitiga kanan adalah Triple Pythagoras Primitif yang terkenal.
Tantangan
- Input yang diberikan
n
, outputn
PPT ke-4. Atau, - Input yang diberikan
n
, outputn
PPT pertama .
Ada beberapa cara untuk memesan PPT ini untuk membentuk daftar yang tertata dengan baik, untuk menentukan mana yang n
ke-5. Anda dapat memilih pemesanan yang Anda inginkan, selama Anda dapat membuktikan (secara informal tidak masalah) bahwa algoritma Anda dapat menghasilkan setiap PPT unik yang mungkin. Misalnya, kode Anda tidak boleh menampilkan keduanya (3,4,5)
dan (4,3,5)
karena itu adalah duplikat dari triple-satu yang sama, tolong.
Demikian pula, apakah kode Anda nol atau satu diindeks baik-baik saja, asalkan Anda menyatakan yang Anda gunakan.
Contohnya
Untuk contoh di bawah ini, saya menggunakan satu-pengindeksan, mengeluarkan n
PPT th, dan memesan dengan terkecil c
, lalu terkecil a
, lalu terkecil b
.
n | output
1 | (3, 4, 5)
2 | (5, 12, 13)
5 | (20, 21, 29)
12| (48, 55, 73)
Aturan
- Input dan output dapat diberikan dalam format apa pun yang nyaman .
- Dalam kiriman Anda, sebutkan bagaimana entri Anda dipesan, dan apakah entri Anda diindeks 0 atau 1 diindeks.
- Pemesanan yang Anda pilih tidak dapat membuat duplikat.
- Program lengkap atau fungsi dapat diterima. Jika suatu fungsi, Anda dapat mengembalikan output daripada mencetaknya.
- Jika memungkinkan, harap sertakan tautan ke lingkungan pengujian online agar orang lain dapat mencoba kode Anda!
- Celah standar dilarang.
- Ini adalah kode-golf sehingga semua aturan golf biasa berlaku, dan kode terpendek (dalam byte) menang.
sumber
Jawaban:
Jelly ,
2725 byte2 byte, terima kasih kepada Jonathan Allan.
Cobalah online!
Menghasilkan
n
tiga kali lipat indeks pertama[b, a, c]
, diurutkan dengan meningkatkanb
lalua
.Menggunakan algoritma dari Wikipedia :
Ini menghasilkan semua tiga kali lipat primitif untuk semua pasangan koprime unik bilangan bulat ganjil
m > n > 0
.Penjelasan
sumber
g/Ị$Ðf
->g/ÐṂ
untuk menyimpan dua byte (karena gcd minimal adalah 1 dan akan selalu ada setidaknya satu entri seperti itu).+2ḶḤ‘Œc
dengan²Rm2Œc
- memo yang tidak akan berfungsi untuk input1
:(²ḶḤ‘Œc
adalah salah satu yang pertama saya pikirkan.)MATL , 36 byte
Input berbasis 1. Urutan output menjamin bahwa setiap triple muncul tepat sekali. Urutan dijelaskan sebagai berikut. Penjelasannya membutuhkan sedikit menggali cara kerja program.
Kode terus meningkatkan penghitung
k
dalam satu lingkaran, mulai dari1
. Untuk setiapk
itu menghasilkan semua pasangan dengana = 1,...,k
,b = 1,...,k
,a < b
, dan picks mereka yang memberikan Pythagoras triple denganc <= k
. Pasangan diperoleh dalam urutan meningkatb
, lalua
.Setiap pasangan kemudian dibagi dengan gcd-nya. Pasangan yang dihasilkan (mungkin diduplikasi) disusun sebagai matriks dua kolom. Matriks ini digabungkan secara vertikal dengan matriks serupa yang berisi hasil akumulasi yang diperoleh untuk nilai yang lebih kecil dari
k
. Baris-baris matriks kemudian diduplikasi secara stabil. Ini menghapus dua jenis duplikat:Pasangan yang telah ditemukan lebih dari satu kali untuk saat ini
k
(seperti3,4
, yang juga hasil dari6,8
ketika membaginya dengan gcd);Pasangan yang sudah ditemukan dengan yang lebih kecil
k
.Bahkan, setiap iterasi
k
menemukan semua pasangan yang sudah ditemukan untuk iterasi sebelumnya. Tetapi mungkin menemukan mereka dalam urutan yang berbeda . Misalnya,k=25
akan menemukan triple7,24,25
dan bukan20,21,29
(karenac
tidak bisa melebihik
). Nantinya, iterasik=29
akan menemukan keduanya, tetapi dengan20,21,29
sebelumnya7,24,25
(pesanan meningkatb
, lalua
). Inilah sebabnya, alih-alih menjaga semua pasangan ditemukan untuk yang terbaruk
, kami menambahkannya ke yang sebelumnya dan menduplikasi secara stabil. Melakukan hal itu memastikan bahwa urutannya sama untuk setiap inputn
.Penjelasan di atas menjamin bahwa setiap triple Pythagoras primitif pada akhirnya akan muncul, dan itu hanya akan muncul sekali. Untuk input
n
, loop overk
selesai ketika setidaknyan
tiga kali lipat valid telah diperoleh; dan kemudiann
-th triple adalah ouput.Cobalah online!
Atau gunakan kode yang dimodifikasi ini untuk melihat
n
tiga kali lipat pertama :Cobalah online!
sumber
Haskell , 98 byte
Cobalah online!
Bagaimana itu bekerja
Ini menafsirkan basis-3 bijective digit n sebagai jalan ke pohon tiga kali lipat Pythagoras primitif . Ini berjalan tanpa pencarian dalam operasi O (log n ).
sumber
Jelly ,
1918 byteProgram ini mengambil indeks berbasis 1 n dan mencetak pertama n PPTs [c, b, a] agar leksikografis.
Ini adalah solusi O (64 n ) , jadi TIO akan tersedak input 4 dan lebih tinggi. Saya akan berusaha membuatnya lebih cepat.
Cobalah online!
Versi alternatif, O (n 3 ), mungkin valid
Untuk menemukan triplet ke- n - [c n , b n , a n ] - solusi di atas mengasumsikan bahwa c n ≤ 4 n , yang mudah diverifikasi. Namun, A020882 membuktikan bahwa c n ~ 2πn , jadi ada k sedemikian sehingga c n ≤ kn untuk semua n .
Jika kita dapat mengambil k = 7 , solusi di bawah ini juga valid (dan jauh lebih cepat).
Cobalah online!
Bagaimana itu bekerja
sumber
JavaScript (ES7),
106105103 byteMenghasilkan PPT ke-N. Hasil 1-diindeks dan dipesan oleh nilai b .
Demo
Tampilkan cuplikan kode
sumber
MATL , 63 byte
Cobalah online!
Pelajaran dalam bermain golf sangat salah. Saya tetap memposting karena saya ingin tahu apakah ada cara untuk bermain golf ini lebih baik.
Saya mendasarkan ini pada halaman Wikipedia ini dalam kombinasi dengan formula Euclid, untuk secara konstruktif menghasilkan semua tiga kali lipat daripada pendekatan coba-coba.
Pertama, pasangan coprime aneh dihasilkan sebagai pohon ternary. Ini dilakukan sebagai perkalian matriks besar, akuntansi untuk sebagian besar jumlah byte. Kemudian, formula Euclid diterapkan, mungkin juga dengan cara byte-wasting. Jika ada yang punya tip untuk dua bagian ini, saya ingin mendengarnya.
Perhatikan bahwa, untuk menyimpan byte, program ini menghasilkan pohon kedalaman yang sama dengan input, bukan
log3(n)
. Juga, anak-anak dihasilkan untuk setiap baris daripada hanya untuk baris terakhir dari pohon, dan kemudian disaring lagi denganXu
. Begitu banyak untuk pendekatan konstruktif yang efisien.sumber
Haskell, 65 byte
Pengindeksan berbasis 0. Untuk yang diberikan
c
,b
berjalan ke atasc
dana
ke atasb
, jadic > b > a
selalu berlaku.Cobalah online!
sumber
Python,
67504846 BytesMenggunakan rumus yang ditemukan di wikipedia,
a=m*n, b=(m^2-n^2)/2, c=(m^2+n^2)/2
di mana
m>n>0
danm
dann
adalah coprimes dan aneh. Ini kodenya-17 byte terima kasih kepada @Martin Ender
Cobalah secara Online
Bekerja dengan selalu memiliki nilai
n
variabel dalam persamaan menjadi 1, yang berarti bahwam
hanya ada nilai ganjil lainnya, dalam hal ini, di3+2*n
manan
adalah jumlah triple Pythagoras primitif. Ini memungkinkan kita untuk mengasumsikan nilai 1 untuk semuan
nilai.sumber
a
(dan jika Anda melakukannya, Anda bisa menyingkirkan dua ruang di sana). Saya juga tidak yakin mengapa Anda diprint
sana, Anda bisa mengembalikan nilai dari lambda itu sendiri.Sekam , 18 byte
Cobalah online!
-4 byte terima kasih kepada Zgarb, dengan inspirasi dari Dennis
Pendekatan brute force super-lambat, tidak akan bekerja pada TIO untuk input yang lebih besar dari 1. Anda dapat mencoba versi yang lebih mudah dikelola, terbatas pada a, b≤200 di sini
Penjelasan
sumber
c
? dalam hal ini solusi ini perlu diperbaikic
. Solusi 18-byte ini (yang menggunakan tipuan lain dari Dennis) berfungsi apa pun.Mathematica, 89 byte
menggunakan Solve yang dipesan oleh c
Mathematica, 124 byte
sumber
R (+ angka), 88 byte
Untuk menggunakan builtin untuk menghasilkan angka, dibutuhkan jumlah byte yang mengejutkan untuk mendapatkan yang kita inginkan. Builtin mengambil dua argumen
c1
danc2
, dan mengembalikan triplet yang adac >= c1 & c <= c2
. Ini membuatnya sedikit mengganggu untuk sampai ken
triplet -th. Ini hanya akan terus meningkatkanc2
1 pada satu waktu sampai output cukup baris.sumber
PHP , 273 Bytes
t($n)
mengembalikan array [a, b, c] dengan pemesanana < b < c
Cobalah online! (kode juga dapat dibaca di sana)
sumber
C, 158 byte
Saya percaya ini adalah pengiriman pertama saya di sini, jadi Anda mungkin bisa melakukan yang lebih baik.
Dan versi yang tidak dipisahkan:
Untuk a 2 + b 2 = c 2 , urutannya meningkat c kemudian meningkat a .
Tidak mungkin ada dua kali PPT yang sama dengan b pada leas a dalam algoritma ini.sumber
Jelly ,
2725 byteIni adalah implementasi dari pendekatan pohon dari jawaban Haskell @ AndersKaseorg , dengan urutan cabang yang berbeda. Program ini menggunakan pengindeksan berbasis 0 dan mengambil input dari STDIN.
Cobalah online!
Latar Belakang
Seperti disebutkan di halaman Wikipedia Tree of Pythagoras triples primitif , setiap PPT dapat diperoleh dengan berulang kali mengalikan vektor baris (3, 4, 5) dengan matriks dengan properti tertentu.
Di setiap iterasi, hasil sebelumnya dapat dikalikan dengan salah satu A , B , atau C , yang dapat dipilih sebagai berikut.
Ketika A , B , dan C diperbaiki, setiap PPT dapat diperoleh dengan cara yang unik.
Bagaimana itu bekerja
sumber
APL (NARS), 90 karakter, 180 byte
jika argumen fungsi di atas adalah ⍵, fungsi di atas akan mengembalikan elemen indeks ⍵ (1 berbasis) dari array memiliki elemen tripel Pythagoras (a, b, c) di mana a <= b <= c dan array itu adalah urutan pertama untuk a, (sisi lebih pendek), kemudian untuk b (sisi lain bukan sisi miring). Akan ada sesuatu yang salah karena tidak terlihat di mana saya memesan untuk b juga ... test:
itu terkait dengan http://oeis.org/A020884 dan http://oeis.org/A020884/b020884.txt
A020884: Memerintahkan kaki pendek segitiga Pythagoras primitif.
Saya tidak tahu apakah itu benar, sepertinya berfungsi memberikan hasil yang benar dari sisi pertama segitiga sampai 1000 tetapi saya tidak tahu untuk yang tersisa, dan mungkin bisa beberapa triple tidak benar juga <1000.
sumber
JavaScript, 101 byte
Dengan rumus Euclid, semua tiga kali lipat Pythagoras primitif dapat dihasilkan dari bilangan bulat
m
dann
denganm>n>0
,m+n
anehgcd(m,n)==1
( Wikipedia )Fungsi ini menghitung semua
m,n
pasangan bertambah m mulai darim=2
dan menurunn
dengan 2 mulai darim-1
(jadi itum+n
aneh)Kurang golf
Uji
sumber