قد يكون باردًا ، وتم إيقاف التسخين ، وكانت قوى الحوسبة (والتدفئة) لا شيء ، لكنها كانت خاملة. فلماذا لا تحملهم بشيء غير مفيد ، والذي سوف يسخن ويسلي.لكن سأبدأ من بعيد. في اليوم الآخر ، واجهت مشكلة لمدرسة ثانوية بالصياغة التالية: "تمت كتابة العديد من الأرقام الطبيعية المتتالية في صف بطريقة تجعل مجموع كل ثلاثة أرقام متتالية قابلة للقسمة بالكامل على أقصى اليسار من هذه الثلاثة. "ما هو الحد الأقصى لعدد الأرقام التي يمكن كتابتها إذا كان رقم السطر الأخير فرديًا؟"مع هذا التقييد ، من السهل إثبات أنه في كل ثلاثية من الأرقام الفردية سيكون هناك أكثر من أرقام زوجية. وبما أن الفرق بينهما لا يمكن أن يكون أكثر من واحد ، فإن الحد الأقصى لطول التسلسل يقتصر على خمسة أرقام. وكمثال ، يمكننا إعطاء التسلسل 4 5 3 2 1 .يمكن العثور على دليل مفصل هنا.ولكن ماذا لو أزلنا القيد المشار إليه على غرابة الرقم الأخير؟ ثم على اليمين يمكنك إضافة الأرقام 7 6 8 ، لتوسيع التسلسل إلى ثمانية أرقام. يمكنك أيضًا إضافة اثني عشر ، وإرفاق التسعة المفقودين إلى اليسار. حسنًا ، وربما لن يكون هذا هو التبادل الوحيد وليس الأطول.في الواقع ، في محاولة للتفكير المنطقي ، لم أجد دليلاً على قيود هذه التسلسلات وقررت إشراك آلة حاسبة في سخان المنزل للتحليل . بحث شامل شامل لجميع N ! أظهرت الخيارات بسرعة فشل الطريقة ، لكن تعداد الاتجاه سمح بتقدم كبير ، وكانت النتيجة متوقعة وغير متوقعة في نفس الوقت.اتضح أنه بالنسبة لجميع N حتى 29 بما في ذلك 29 ، تم العثور على مثل هذه التباديل للأرقام من 1 إلى N ، مع ذلك ، للأطوال 27 و 29 في متغير واحد. ولكن هناك فجوات. بالنسبة إلى التباديل ذات الأحجام 30 و 31 و 32 و 33 ، لا توجد حلول ؛ للرقم 34 ، هناك حل.هذه33 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
ثم مرة أخرى ، مسافتان. بالنسبة للقيم 37 و 38 ، فإن مثل هذه التسلسلات ليست مفردة ، ثم فشل. كنت حتى يائسة ، وتبين أن العشرة التالية كانت فارغة تمامًا ، لكن الحظ ابتسم ، لأن N = 51 لا يزال يتم العثور على التبادل الضروري.ها هي46 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
هناك حتى اثنان منهم ، لكنهما يتقاطعان في معظم الأحيان.علاوة على ذلك ، تم التخطيط للفراغ مرة أخرى ، على الأقل للأعداد 52 و 53 لا توجد حلول ، لكنني لم أتطلع إلى أبعد من ذلك. ومع ذلك ، مع كل خطوة ، يزداد وقت الانتظار بشكل كبير ، وقد أصبح المنزل أكثر دفئًا بالفعل ، قررت التوقف عند هذا الحد الآن.إذا قمت بتقليل العدد الموجود من الخيارات الممكنة في جدول واحد ، يمكنك بناء الرسم البياني التالي
حسنًا ، نعم ، هناك شيء للتأمل فيه.في المشكلة الأصلية ، لم يكن هناك شرط لبدء السلسلة الطبيعية من واحدة. الشيء الرئيسي هو أن جميع الأرقام من أ إلى ب موجودة في التسلسل. ولكن حاولت ، أن الأمر يزداد سوءًا ، وهناك خيارات أقل. وهو ، في الواقع ، يمكن تفسيره. كلما كان الرقم أكبر في الموضع الأيسر من الثلاثي ، كلما كان من الممكن الحصول على تعدد أقل من مجموع الاثنين الآخرين ، أي الخيارات المتاحة أقل. حسنًا ، يبقى سؤال الحد الأعلى لأطوال هذه التسلسلات مفتوحًا. مع نمو الأبعاد ، ينخفض احتمال النجاح بشكل واضح ، ولكن هل يتم إبطاله؟ أو علاوة على ذلك ، سيواجهون ، ولو نادرا ، مثل هذه التباديل (غير) المثيرة للاهتمام.أخيرًا ، ربما يمكنك إحضار رمز برنامج التدفئة ،صحيح أنه على هاسكلimport 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