Mungkin menjadi dingin, pemanasan dimatikan, dan kekuatan komputasi (dan pemanasan) tidak ada, tetapi mereka menganggur. Jadi mengapa tidak mengisinya dengan sesuatu yang tidak berguna , yang akan menghangatkan dan menghibur.Tapi saya akan mulai dari jauh. Beberapa hari yang lalu saya menemukan masalah untuk sebuah sekolah menengah dengan kata-kata berikut: “Beberapa bilangan alami berturut-turut dituliskan sedemikian rupa sehingga jumlah setiap tiga angka berturut-turut dibagi seluruhnya dengan angka paling kiri dari tiga ini. "Berapa jumlah maksimum angka yang bisa ditulis jika nomor baris terakhir ganjil?"Dengan pembatasan ini, mudah untuk membuktikan bahwa dalam setiap tiga kali angka ganjil akan ada lebih dari angka genap. Dan karena perbedaan di antara mereka tidak boleh lebih dari satu, panjang maksimum urutan dibatasi hingga lima angka. Dan sebagai contoh, kita dapat memberikan urutan 4 5 3 2 1 .Bukti terperinci dapat ditemukan di sini.Tetapi bagaimana jika kita menghapus batasan yang ditunjukkan pada keanehan nomor terakhir? Kemudian di sebelah kanan Anda dapat menambahkan angka 7 6 8 , memperluas urutan menjadi delapan angka. Anda juga dapat menambahkan selusin, dan lampirkan sembilan yang hilang di sebelah kiri. Yah, dan mungkin ini bukan satu-satunya dan bukan permutasi terpanjang.Sebenarnya, mencoba untuk bernalar secara logis, saya tidak menemukan bukti keterbatasan urutan tersebut dan memutuskan untuk melibatkan komputer dalam analisis pemanas rumah . Pencarian lengkap dan menyeluruh dari semua N ! opsi dengan cepat menunjukkan kegagalan metode, tetapi enumerasi terarah memungkinkan kemajuan yang signifikan, dan hasilnya diharapkan dan tidak terduga pada saat yang sama.Ternyata untuk semua N hingga dan termasuk 29 permutasi angka dari 1 hingga N benar - benar ditemukan, bagaimanapun, untuk panjang 27 dan 29 dalam satu varian. Tapi kemudian ada celah. Untuk permutasi dengan ukuran 30, 31, 32, dan 33, tidak ada solusi, untuk angka 34, ada satu.seperti itu33 23 10 13 7 6 1 29 27 2 25 21 4 17 15 19 11 8 3 5 31 9 22 14 30 26 34 18 16 20 12 28 32 24
Kemudian lagi, dua spasi. Untuk nilai 37 dan 38, sekuens semacam itu tidak tunggal, dan kemudian gagal. Aku bahkan putus asa, sepuluh berikutnya ternyata benar-benar kosong, tetapi keberuntungan tersenyum, karena N = 51 permutasi yang diperlukan masih ditemukan.ini dia46 45 1 44 49 39 10 29 21 37 5 32 23 41 51 31 20 11 9 2 43 35 8 27 13 14 25 3 47 40 7 33 16 17 15 19 26 50 28 22 6 38 34 4 30 18 42 48 36 12 24
Bahkan ada dua dari mereka, tetapi mereka berpotongan sebagian besar.Lebih jauh lagi, kekosongan direncanakan lagi, setidaknya untuk angka 52 dan 53 tidak ada solusi, tetapi saya tidak melihat lebih jauh. Namun demikian, dengan setiap langkah, waktu tunggu tumbuh secara eksponensial, dan rumah sudah menjadi lebih hangat, saya memutuskan untuk berhenti di sana untuk saat ini.Jika Anda mengurangi jumlah opsi yang mungkin ditemukan dalam satu tabel, Anda dapat membuat bagan berikut
. Ya, ada sesuatu untuk direnungkan.Dalam masalah aslinya, tidak ada persyaratan untuk memulai seri alami dari satu. Hal utama adalah bahwa semua angka dari a hingga b ditemukan dalam urutan. Tapi saya mencoba, itu hanya menjadi lebih buruk, ada pilihan lebih sedikit. Yang sebenarnya bisa dijelaskan. Semakin besar angkanya di posisi kiri triple, semakin rendah multiplisitas dapat diperoleh dengan jumlah dua lainnya, yaitu semakin sedikit opsi yang tersedia. Nah, pertanyaan tentang batas atas dari panjang urutan seperti itu tetap terbuka. Dengan pertumbuhan dimensi, probabilitas keberhasilan jelas berkurang, tetapi apakah itu dibatalkan? Atau lebih lanjut, mereka akan, meskipun jarang, menghadapi permutasi yang menarik.Akhirnya, mungkin Anda bisa membawa kode program pemanasan,benar dia ada di Haskellimport Data.List (delete)
import Control.Parallel.Strategies
import System.Environment
pvc :: Int -> Int -> [Int] -> [[Int]]
pvc a b [] = [[a,b]]
pvc a b xs = [a:ys |
x <- xs,
mod (a + b + x) a == 0,
ys <- pvc b x (delete x xs)]
gen :: Int -> [[[Int]]]
gen n =
let ab = [(a, b) | a <- [1..n], b <- delete a [1..n]]
in map hlp ab `using` parList rseq
where
hlp (a,b) = pvc a b $ delete a $ delete b [1..n]
main = do
[n] <- getArgs
print $ concat $ gen $ read n