Bagaimana jika kita mengambil matematika yang luar biasa (yaitu, persamaan linear) dan
JavaScript kita yang sama hebatnya, dan kemudian menempatkan satu sama lain? Dalam kondisi keterbatasan dan kekhasan lingkungan-js, masalah matematika sederhana dapat berubah menjadi sangat aneh dan penuh dengan perangkap js-stones. Pada konferensi
HolyJS 19 terakhir di Moskow, satu persamaan linear semacam itu (di antara tugas-tugas lain dari
SEMrush ) menyebabkan
kehebohan .
Dan ya, ini lagi judul dari Menghibur JavaScript: Saya meminta Anda untuk memotong semua orang yang peduli.
Tentu saja, semua yang dijelaskan di bawah ini - ini hanya upaya sembrono untuk simbiosis dua hal indah untuk bersenang-senang - tidak boleh dianggap serius. Dan materi ini tidak akan ada jika bukan karena minat yang hidup dari para peserta konferensi, yang berkat khusus untuk mereka!
Kata-kata
1. Temukan semua solusi integer dari persamaan:
9 +~ x >> 6 / 3 = -x / 3
2. Temukan semua solusi integer dari persamaan:
9 +~ x >> 6 / 3 = -x / 3 | 0
Persamaan kedua berbeda dari yang pertama hanya dalam operasi tambahan di sisi kanan.
Perkiraan matematika
Kita beralih ke persamaan pertama. Dan untuk memulainya, kita akan memahami prioritas operasi yang digunakan,
sesuai tabel :
(9 +(~ x)) >> (6 / 3) = -x / 3
Kami mengambil negasi bitwise dari
x , lalu menambahkannya ke 9. Hasil penambahan digeser bitwise ke kanan dengan jumlah bit yang sama dengan hasil membagi 6 dengan 3.
Jelas, masalahnya terletak pada penggunaan operasi bitwise pada
x yang diinginkan. Tetapi untuk menemukan beberapa akar kondisional untuk alasan lebih lanjut, ada baiknya mencoba membawa persamaan ke analog matematika perkiraan.
Operasi bitwise bekerja dengan operan sebagai bilangan bulat 32-bit yang ditandatangani. Bitwise TIDAK dapat diganti dengan negasi
bilangan bulat dari kenaikan:
(9 -(x + 1)) >> (6 / 3) = -x / 3 (8 - x) >> 2 = -x / 3
Pergeseran bitwise ke kanan (sambil mempertahankan tanda) dapat diganti dengan pembagian
bilangan bulat dengan dua hingga derajat yang sama dengan operan di sebelah kanan:
(8 - x) / 2^2 = -x / 3 (8 - x) / 4 = -x / 3
Tentu saja, penggantian ini sangat sewenang-wenang, dan kami akan membicarakannya nanti. Dan sekarang kita memiliki persamaan linear yang biasa, satu-satunya root adalah -24. Ganti nilai di sisi kiri dan kanan persamaan asli:
9 +~ (-24) >> 6 / 3;
Kedua bagian itu sama, yang berarti semuanya tidak ada harapan dan -24 benar-benar solusi.
Cari yang malas
Jika kita menggambar grafik fungsi
f1 (x) = (8 -x) / 4 dan
f2 (x) = -x / 3 , maka tentu saja kita menemukan satu-satunya titik persimpangan dari dua garis pada
x = -24 .
Tapi kami membuat beberapa substitusi yang tidak sama dengan operasi bitwise di ekspresi kiri, jadi dalam kenyataannya grafik fungsi
f1 akan sedikit berbeda. Untuk setiap
x, nilai fungsi akan menjadi bilangan bulat yang berbeda dari nilai pada garis kontinu
f1 dengan kemungkinan pergeseran dalam rentang dari -1 ke 1. Ini berarti bahwa kita dapat membatasi area pencarian solusi ke kiri dan kanan -24, di mana nilai fungsi
f1 dan
f2 mulai berbeda lebih dari satu.
Untuk menemukan batas-batas area pencarian, Anda dapat 1) menyelesaikan ketidaksetaraan dengan modul, atau 2) melihat lebih dekat pada grafik fungsi. Kami akan menemukan bahwa
x layak untuk dilihat di segmen [-36, -12]:
| (8 - x) / 4 + x / 3 | <= 1
Untuk beralih pada seluruh solusi dalam beberapa rentang tertutup
[mohon, akhiri], kami menulis fungsi
findx :
const findx = (f, beg, end) => [...Array(end - beg + 1)].map((_, i) => i + beg).filter(f);
Fungsi mengembalikan array bilangan bulat yang nilai fungsi yang diteruskan
f dikurangi menjadi
true . Untuk menemukan solusi, kami merepresentasikan persamaan sebagai fungsi js menggunakan operator persamaan:
let eq1 = x => 9 +~ x >> 6 / 3 == -x / 3; findx(eq1, -36, -12);
Jadi,
x = [-24, -21, -18, -15] adalah solusi yang diinginkan untuk persamaan pertama.
Solusi grafis
Pencacahan tentu saja berhasil, tetapi mari kita tetap mencari tahu grafik fungsi
f1 sampai akhir dan menyelesaikan persamaan secara grafis. Selain itu, solusinya tidak menyiratkan kepemilikan wajib dari konsol browser.
Operator bitwise NOT hanya membuang bagian fraksional, sehingga hasilnya
- (x + 1) akan dibulatkan ke bawah. Operator bit shift sedikit lebih rumit. Kami menggantinya dengan pembagian integer, tetapi tergantung pada tanda nomor dividen, operasi ini membulatkan hasilnya baik turun atau naik:
10 >> 2;
Namun, kita tahu bahwa
x yang diinginkan ada dalam kisaran [-36, -12]. Dengan demikian, operan kiri pergeseran bitwise (
8 -x ) berada dalam kisaran [20, 44], yaitu selalu positif. Yang pada gilirannya berarti pembagian bilangan bulat dengan pembulatan ke bawah.
Setelah mengetahui sifat operasi, kita dapat menggambar grafik yang benar dari fungsi
f1 :
Kami akan menemukan empat titik persimpangan fungsi dalam koordinat yang sama
x = [-24, -21, -18, -15].
Persamaan kedua
Jadi, kita sampai pada persamaan kedua:
9 +~ x >> 6 / 3 = -x / 3 | 0
Ini berbeda dari yang pertama dengan penambahan bitwise OR. Jika operan kanan dari operasi semacam itu adalah nol, maka hasilnya hanyalah nilai operan kiri dengan bagian fraksional dibuang.
Untuk memulai, mari kita pergi melalui pencarian yang sama, cukup tentukan area pencarian. Karena sekarang fungsi
f2 memiliki karakter yang mirip dengan
f1 , untuk keandalan, kemungkinan pergeseran harus disimpulkan dan pencarian harus dibatasi di mana fungsi berbeda dalam nilai absolut lebih dari dua unit - ini adalah [-48, 0].
let eq2 = x => 9 +~ x >> 6 / 3 == -x / 3 | 0; findx(eq2, -48, 0);
Dan kami mendapat jawaban yang sama. Ada kecurigaan bahwa bagaimanapun juga, ada sesuatu yang salah. Tetapi kenyataannya adalah bahwa setelah merepresentasikan persamaan asli sebagai fungsi js, kami menggabungkan dua ekspresi (kiri dan kanan) melalui operator persamaan menjadi satu. Dan operator kesetaraan memiliki prioritasnya, yang lebih tinggi dari prioritas bitwise OR. Fungsi ini identik dengan yang berikut:
x => (9 +~ x >> 6 / 3 == -x / 3) | 0;
Dalam hal ini, bitwise ATAU tidak memiliki efek, karena
true | 0 = 1 . Untuk menghindari ini, perlu untuk secara eksplisit menunjukkan dalam fungsi tubuh bahwa kami membandingkan hasil dari dua subekspresi:
let eq2 = x => (9 +~ x >> 6 / 3) == (-x / 3 | 0); findx(eq2, -48, 0);
Jumlah solusi meningkat. Sekarang mari kita lihat grafik fungsi. Dengan analogi dengan
f1 , "tangga langkah" membangun fungsi yang dimodifikasi
f2 :
Tempat grafik fungsi saling tumpang tindih, tetapi kami hanya tertarik pada poin dengan nilai integer dari koordinat
x : [-32, -29, -28, -26, -25, -25, -24, -23, -22, -21, -19, -18, -15], hanya 12 solusi. Perpotongan dua "tangga" dengan langkah 3 dan 4 dapat ditemukan secara algoritmik, jika Anda mau.
Pertanyaan tambahan
Dalam masalah yang diusulkan pada konferensi ada pertanyaan tambahan: perlu untuk menemukan solusi minimum untuk persamaan 2. Tidak dikatakan bahwa ini adalah bilangan bulat, jadi jawaban
x = -32 - ternyata salah.
Menemukan solusi dengan kekerasan tidak akan berhasil di sini, tetapi menyelesaikannya secara grafis sangat sederhana. Ini adalah nilai
x- ke -33 terdekat di sebelah kanan:
Tampaknya
x = -32. (9). Tetapi ini masih belum benar. Karena lingkungan kita adalah JavaScript, itu berarti bahwa dalam representasi angka kita dibatasi oleh tipe data yang digunakan. Nomor jenisnya adalah float64,
angka floating-point presisi ganda (IEEE 754). Untuk mengingat ini dan menyebutkan perkiraan akurasi sudah cukup untuk mendapatkan rubah mewah!
Sisi gelap dari operasi bitwise
Seperti disebutkan di atas, operasi bitwise mengubah operan ke angka 32-bit yang diwakili oleh urutan 0 dan 1 - ini adalah kisaran [-2147483648, 2147483647]. Jika angka itu tidak cocok dengan itu, maka bit yang paling signifikan akan dibuang.
Dalam persamaan pertama, ini tidak memainkan peran apa pun, karena tidak ada operasi bitwise di sisi kanan. Namun di bagian kedua, konversi angka ini memberikan efek yang menarik.
Misalnya, angka -24 akan direpresentasikan sebagai:
11111111111111111111111111101000
Nilai negatif dari angka tersebut diperoleh dengan membalik (bitwise TIDAK) bit dalam catatan angka positif dengan penambahan satu.
Angka apa pun di luar rentang, setelah konversi yang berakhir dalam urutan 32-bit ini, akan sama dalam operasi biner dengan angka -24. Sebagai contoh, ini adalah angka:
4294967272 | 0;
Di sisi kanan persamaan, sebelum operasi bitwise, kami membagi
x dengan 3. Kami menemukan
x di antara "ekuivalen" -24 yang dapat dibagi dengan 3. Angka tersebut terdekat adalah 12884901864. Ganti dalam persamaan:
9 +~ 12884901864 >> 6 / 3 = -12884901864 / 3 | 0 9 +~ 12884901864 >> 2 = -4294967288 | 0 9 + 23 >> 2 = 8 8 = 8
Hasil pembagian dengan 3 (-4294967288) tidak sesuai dengan 32 digit yang diberikan; saat membalik bit, tandanya akhirnya hilang dan hanya 8 yang tersisa:
00000000000000000000000000001000
Selain itu, Anda dapat memverifikasi kebenaran hasil dengan memanggil fungsi
eq2 :
eq2(12884901864);
Jika Anda memikirkannya, di sebelah root ini Anda dapat menemukan proyeksi dari 11 solusi integer yang tersisa.
Dengan demikian, sejumlah besar solusi baru muncul, dan hanya setara positif terdekat -24 yang dipertimbangkan. Namun demikian, ini tidak semenarik tugas utama, dan ketika menganalisis keputusan dari para peserta, jawaban yang sangat jarang seperti itu dievaluasi secara terpisah. Agar tidak bingung, Anda bisa memperkenalkan batasan pada bilangan bulat yang diinginkan ke dalam kondisi masalah seperti yang ditandatangani 32-bit.
Dan kamu tidak bisa membuat! Kemudian, untuk menemukan root terkecil, Anda harus memperhatikan lingkungan
Number.MAX_SAFE_INTEGER dengan tanda negatif, karena angka ini bilangan bulat dan dengan float64 yang sangat presisi. Nah, kalau begitu sendiri.
Kesimpulan
Sebagai hasil dari konferensi, sebagian besar peserta menyelesaikan masalah dengan pencarian yang lengkap, sedangkan rentang untuk pencarian benar-benar berbeda karena berbagai alasan. Tapi seperti yang kita lihat, itu cukup untuk lari di ~ 50 bilangan bulat. Banyak yang jatuh ke dalam perangkap prioritas operasional. Seseorang juga memutuskan secara grafis bahwa itu menyenangkan. Unit dikejutkan oleh rilis 32 kategori. Anda bisa menggunakan kekuatan kasar untuk bergerak lebih jauh dalam tugas. Tetapi untuk mendapatkan hadiah tambahan, masih perlu melakukan beberapa analisis matematika dekat.
Saya benar-benar berharap Anda menyukai gagasan tugas yang tidak lazim seperti hiburan untuk format konferensi. Selama setahun terakhir, saya telah mengumpulkan beberapa tugas JavaScript yang "menghibur". Saya memutuskan untuk mengumpulkan semuanya di satu tempat. Ikuti tautan jika Anda tidak takut:
JavaScript Tertantang yang Tidak Terduga . Tugas-tugas
Look Complex dan
Broken Pipe , yang juga diusulkan di konferensi, telah ditata. Ya, ada banyak koleksi seperti itu, tetapi yang ini milik saya! Sekali lagi terima kasih untuk semuanya.