Anda semua tahu metode Newton untuk memperkirakan akar suatu fungsi, bukan? Tujuan saya dalam tugas ini adalah untuk memperkenalkan Anda ke dalam aspek yang menarik dari algoritma ini.
Algoritma Newton hanya konvergen untuk kepastian, tetapi sebagian besar dari semua nilai input kompleks. Jika Anda menggambarkan konvergensi metode untuk semua nilai input di atas bidang kompleks, Anda biasanya mendapatkan fraktal yang indah seperti ini:
Spesifikasi
Tujuan dari tugas ini adalah, untuk menghasilkan fraktal tersebut. Ini berarti, bahwa Anda mendapatkan polinomial sebagai input dan harus mencetak fraktal yang sesuai sebagai gambar dalam format pilihan Anda sebagai output.
Memasukkan
Input adalah daftar bilangan kompleks yang dipisahkan spasi-putih. Mereka ditulis dengan gaya <Real part><iImaginary part>
, seperti nomor ini:5.32i3.05
. Anda dapat berasumsi, bahwa jumlah input tidak lebih dari 4 tempat desimal dan lebih kecil dari 1000. Yang pertama harus tidak nol. Misalnya, ini bisa menjadi masukan untuk program Anda:
1 -2i7.5 23.0004i-3.8 i12 0 5.1233i0.1
Angka-angka ditafsirkan sebagai koefisien polinomial, dimulai dengan kekuatan tertinggi. Sepanjang spesifikasi ini, input polinomial disebut P . Input di atas sama dengan polinomial ini:
f (x) = x 5 + (-2 + 7,5 i ) x 4 + (23.0004 - 3,8 i ) x 3 + 12 i x 2 + 5,1233 + 0,1 i
Masukan mungkin datang kepada Anda baik dari stdin, dari argumen yang diteruskan ke program atau dari prompt yang ditampilkan ke program Anda. Anda dapat berasumsi, bahwa input tidak mengandung karakter spasi putih terkemuka atau tambahan.
Rendering
Anda harus membuat fraktal dengan cara berikut:
- Pilih warna sebanyak akar P ditambah warna ekstra untuk divergensi
- Untuk setiap angka dalam bidang yang terlihat, tentukan apakah metode tersebut konvergen dan jika ya ke root mana. Warnai titik sesuai dengan hasilnya.
- Jangan cetak penggaris atau barang mewah lainnya
- Cetak titik hitam pada titik-titik tersebut, yang merupakan akar polinomial untuk orientasi. Anda dapat mencetak hingga empat piksel di sekitar setiap root.
- Temukan cara untuk memilih bidang yang terlihat dengan cara, bahwa semua akar dapat dibedakan dan tersebar luas di atasnya, jika memungkinkan. Meskipun penempatan frame output yang sempurna tidak diperlukan, saya berhak menolak untuk menerima jawaban yang memilih frame dengan cara yang tidak dapat diterima, misalnya. selalu pada koordinat yang sama, semua root berada dalam satu titik, dll.
- Gambar output harus memiliki ukuran 1024 * 1024 piksel.
- Waktu render maksimum 10 menit
- Menggunakan nilai floating-point presisi tunggal sudah cukup
Keluaran
Outputnya harus berupa gambar grafik raster dalam format file pilihan Anda, dapat dibaca oleh perangkat lunak standar untuk sistem operasi merek X. Jika Anda ingin menggunakan format yang langka, pertimbangkan untuk menambahkan tautan ke situs web tempat orang dapat mengunduh pemirsa untuk itu.
Keluarkan file ke stdout. Jika bahasa Anda tidak mendukung meletakkan sesuatu untuk stdout atau jika Anda menemukan opsi ini kurang nyaman, temukan cara lain. Dengan cara apa pun, harus dimungkinkan untuk menyimpan gambar yang dihasilkan.
Batasan
- Tidak ada perpustakaan pemrosesan gambar
- Tidak ada perpustakaan yang menghasilkan fraktal
- Kode terpendek menang
Ekstensi
Jika Anda menyukai tugas ini, Anda bisa mencoba mewarnai titik-titik sesuai dengan kecepatan konvergensi atau kriteria lainnya. Saya ingin melihat beberapa hasil menarik.
Jawaban:
Python,
827777 karakterMenemukan batas tampilan (dan root) dengan menemukan titik konvergensi untuk sekelompok sampel acak. Kemudian menggambar grafik dengan menghitung titik konvergensi untuk setiap titik awal dan menggunakan fungsi hash untuk mendapatkan warna acak untuk setiap titik konvergensi. Lihatlah sangat dekat dan Anda dapat melihat akar ditandai.
Inilah hasil untuk contoh polinomial.
sumber
Jawa,
1093 1058 10991077 karakterInput adalah argumen baris perintah - mis
java F 1 0 0 -1
. Jalankan . Output adalah stdout dalam format PPM (ASCII pixmap).Skala dipilih menggunakan Fujiwara terikat pada nilai absolut dari akar kompleks polinomial; Saya kemudian kalikan dengan 1,5. Saya menyesuaikan kecerahan dengan tingkat konvergensi, sehingga akar akan berada di patch paling terang. Oleh karena itu logis untuk menggunakan putih daripada hitam untuk menandai perkiraan lokasi akar (yang biayanya 41 dolar untuk sesuatu yang bahkan tidak dapat dilakukan "dengan benar". Jika saya memberi label semua titik yang konvergen ke dalam 0,5 piksel dari diri mereka sendiri kemudian beberapa root keluar tanpa label, jika saya memberi label semua titik yang menyatu dalam 0,6 piksel dari mereka sendiri maka beberapa root keluar berlabel lebih dari satu piksel, jadi untuk setiap root saya memberi label titik pertama yang ditemui untuk konvergen ke dalam 1 pixel dari dirinya sendiri ).
Gambar untuk contoh polinomial (dikonversi ke png dengan GIMP):
sumber
x^6-9x^3+8
, dirancang dengan hati-hati dengan memilih akar dan kemudian menggunakan Wolfram Alpha untuk menyederhanakan polinomial. Ok, saya curang dengan menukar rona di sekitar setelah itu di GIMP.Python, 633 byte
Setelah Mempercepat dan Mempercantik (756 byte)
Plot di bawah ini untuk fungsi Newton Fractal of log (z).
sumber
;
. Juga, hapus semua ruang yang mungkin.matplotlib
sini), jadi tidak ada jaminan bahwa itu masih berfungsi.