Perselisihan yang muncul secara berkala di forum tematik tentang apakah seorang programmer membutuhkan matematika telah lama menjadi tempat umum dan area perang suci. Berada di sisi (kanan) kami di perbatasan yang memisahkan antara yang baik dari yang jahat, saya ingin membagikan satu contoh yang dengan jelas menunjukkan betapa itu sangat dibutuhkan dan bahkan (kami tidak akan takut dengan kata ini) diperlukan.
Pertimbangkan masalah pemrograman yang menarik, yang memiliki karakter yang agak olimpiade.
Pnp: Dari titik ini ke depan, para pendukung gagasan bahwa pemrograman hari ini terdiri dari halaman web yang dirancang dengan indah dapat berhenti membaca, Anda benar sekali, Anda tidak perlu matematika ...
Nah, Anda tidak perlu memaksakan hal itu, Anda tidak lebih buruk dari kami, dan pekerjaan Anda sangat penting, karena saya sudah sepakat bahwa kami memiliki ide berbeda tentang pemrograman ...
Ya, Anda benar bahwa olimpiade ini tidak akan dapat, dengan bantuan kerangka kerja terakhir, untuk menggambar tujuh garis tegak lurus merah dalam satu baris kode ...
Namun demikian, saya menganggapnya sebagai ide saya yang benar (ini adalah properti fatal dari materi yang sangat terorganisir dalam bentuk tubuh protein), oleh karena itu saya akan menyajikan argumen dalam dukungannya.Saya merumuskan masalah - berapa banyak jumlah panjang K yang berakhir dengan tombol p yang diberikan dapat diketik pada tombol telepon (keyboard) jika kita perlu bergerak di sekitar tombol dengan ksatria catur. Dapat dipahami bahwa Anda melihat keyboard (saya masih memiliki ponsel biasa, bukan smartphone, jadi saya melihatnya setiap hari, pembaca yang lebih maju harus menghubungi Internet untuk bantuan) dan Anda tahu bagaimana kuda catur berjalan (mudah ke google). matematika tidak ada hubungannya dengan sejauh ini, jika Anda tidak memiliki pikiran untuk menghitung opsi.
Solusi pertama cukup jelas - kami mengambil semua 10 tombol satu demi satu (kami menunjukkan nomor mereka dengan n untuk umum), mempertimbangkan semua kemungkinan jumlah K panjang dari itu dan menghitung yang berakhir pada tombol yang diinginkan. Angka-angka yang dihasilkan dirangkum dan jawabannya siap. Jumlah total opsi yang dilihat kira-kira dinyatakan sebagai n * B (K), di mana B (K) adalah jumlah kemungkinan pergerakan panjang K. Bahkan, Anda perlu mempertimbangkan jumlah posisi n, karena B (p, K) jelas tergantung pada jumlah tombol tetapi sebagai estimasi pertama turun.
Sebelum melanjutkan untuk mencari B, orang dapat secara signifikan mengurangi jumlah opsi dengan menerapkan (tidak, belum matematika) akal sehat. Karena pergerakan tombol pada tergantung pada latar belakang, kita dapat membalikkan tugas dan mencari semua jumlah panjang K mulai dari tombol p yang diinginkan. Maka jumlah total opsi adalah B (p, K), yang n kali lebih sedikit. Wow, kami baru saja menemukan cara untuk mempercepat pencarian solusi 10 kali - keren, mari kita lihat berapa banyak yang tersisa.
Kita perlu mengevaluasi B (p, K), untuk itu kita menentukan bahwa pada setiap langkah kita memiliki 2 hingga 3 opsi untuk pengembangan acara. Maka (secara umum, ini adalah kombinatorik, tetapi secara intuitif jelas) bahwa jumlah total opsi akan dari 2 ** K hingga 3 ** K (selanjutnya saya menggunakan K-1 sebagai K). Kami bahkan dapat meningkatkan estimasi ini dengan beralih ke model probabilistik. Mempertimbangkan keberadaan jari pada setiap tombol saat ini sama-sama memungkinkan (pernyataan yang kuat, kemungkinan besar salah, tetapi dapat diterima dengan perkiraan kasar), kita dapat menghitung jumlah rata-rata opsi pemindahan 7 * 2 + 2 (tombol 4 dan 6) * 3 = 20/9 ~ 2.22 . Maka estimasi akan menjadi 2.22 ** K, dan kami tahu pasti bahwa kami memiliki minimal 2 ** K. Kemudian untuk K = 100 kita mendapatkan batas bawah 2 ** 100 = (2 ** 10) ** 10> (10 ** 3) ** 10 = 10 ** 30.
Jika kita mempertimbangkan satu opsi dalam nanodetik (dan ini tidak mudah bahkan pada PC desktop yang kuat), maka kita memerlukan 10 ** 30/10 ** 9 = 10 ** 21 detik. Selanjutnya, kita ingat mnononis yang indah "π detik sama dengan satu abad" dan waktu yang diperlukan adalah 10 ** 21 / 3.14 * 10 ** 9 ~ 3 * 10 ** 11 abad. Tampaknya bagi saya bahwa sedikit pembaca akan hidup untuk melihat akhir perhitungan menggunakan metodologi yang diusulkan. Peserta pameran itu mengerikan, hanya faktorial yang lebih buruk darinya.
Kami akan meningkatkan solusi berdasarkan fakta bahwa kami tertarik pada sejumlah opsi, tetapi bukan opsi itu sendiri. Anda dapat menawarkan rumus yang jelas B (p, K) = jumlah B (p ', K-1) untuk semua p' di mana kita dapatkan dalam 1 langkah dari p. Kita mulai dari tombol terakhir dan menetapkan bobot 1, kemudian melaksanakan prosedur menjumlahkan bobot saat ini ke yang berikutnya, ulangi ke kedalaman yang diinginkan.
Kami menggambarkan apa yang dikatakan dengan contoh, dimulai dengan angka 1 {1234567890}:
bobot awal {1000000000},
setelah transfer pertama {0000010100} (2 opsi),
setelah transfer kedua {2010001001} (5 opsi),
setelah {0102040300} ketiga (10 opsi) dan seterusnya.
Algoritma ini sederhana, dapat diimplementasikan bahkan dengan tangan Anda. Estimasi umum waktu eksekusi adalah K iterasi, di mana masing-masing untuk n bobot kita memodifikasi tidak lebih dari n bobot terkait, total
n ** 2 * K. Untuk kasus yang dibahas sebelumnya, 10 * 10 * 100 = 10 ** 4 - cukup banyak.
Tetap hanya untuk mengevaluasi durasi setiap operasi - ini adalah penambahan (pertanyaan sampah), tetapi bukan penambahan sederhana (dari tempat ini lebih terinci). Kami telah menetapkan batas bawah dari respons ke 2 ** K, yaitu, kami pasti membutuhkan setidaknya K bit untuk mewakili hasilnya. Batas atas adalah 3 ** K, untuk kasus kami 3 ** 100 = (3 ** 5) ** 20 <(2 ** 8) * 20 = 2 ** 160, artinya, kami dijamin dapat masuk ke dalam 160 bit. Kita dapat berasumsi bahwa 128 bit sudah cukup untuk kita, karena 2.2 ** 100 <2 ** 128, tetapi menerima pernyataan iman seperti itu menakutkan, jadi kita memerlukan angka dengan setidaknya 160 bit atau dengan 49 angka desimal, tergantung pada perpustakaan nomor Anda akurasi tinggi.
PNP: Jangan menawarkan floating point, kami membutuhkan hasil yang sepenuhnya akurat.Dalam asumsi yang diterima, operasi penambahan akan menempati 160/8 = 20 byte / 4 = 5 penambahan bilangan bulat 32 bit, yang sama sekali tidak mempengaruhi urutan waktu (tetap linier dalam K), tetapi secara signifikan dapat meningkatkan waktu perhitungan nyata (beberapa kali).
Bagaimanapun, hasilnya sangat luar biasa - kami mengubah tugas dari yang pada dasarnya tidak dapat diselesaikan dalam waktu yang wajar menjadi sepenuhnya dapat dipecahkan: jika satu operasi penambahan dasar dilakukan dalam mikrodetik (dan ini mudah untuk memastikan bahkan pada papan Arduino), maka total waktu tidak akan melebihi 10 ** 4 * 20 / 10 ** 6, kurang dari satu detik) dan kami melakukannya tanpa matematika.
Namun demikian, dan jika kita membutuhkan K yang lebih besar - tentu saja, urutan perhitungan linier - ini luar biasa, tetapi hal itu dapat (dan akan) menyebabkan kerugian waktu yang signifikan untuk nilai-nilai besar. Ternyata Anda dapat secara signifikan meningkatkan waktu yang diharapkan, perhatikan tangan Anda.
Apa yang kami lakukan pada setiap langkah perhitungan (pseudo-code):
= 0;
1
2
* ( 1 2)
* 1 2.
=
2 ( 1 * )
0 1, . '=* =(...((*)*)...). , =***. , . **3,
***3 — , ? , …
— , **3 , , , ( ) ( ), . , 100 99 8. , 2*log2(), ( =100 1000/10=100 ) ,
2*log2()***3. , , , . , , log2(K), , , 100.
- ( , ), , , .