تنفيذ طريقة الحكم في هاسكل

Question

أنا أفعل السؤال 266. في Project Euler وبعد قليل من البحث، وجدت هذه الطريقة من العثور بسرعة على عوامل عدد. ما تفعله هو العثور على جميع التباديل للعوامل الرئيسية للرقم: هذه هي عواملها.

لدي بالفعل وحدة نمطية للعثور على عوامل الطاقة الرئيسية للرقم، على سبيل المثال:

Main> primePowerFactors 196
[(2,2),(7,2)]

هذا يظهر أساسا أن: 2^2 * 7^2 == 196. وبعد من هنا أريد أن أجد جميع التباديل من هذه القوى، لإعطاء عوامل 196 حتيا:

• (2^0)(7^0) = 1
• (2^1)(7^0) = 2
• (2^2)(7^0) = 4
• (2^0)(7^1) = 7
• (2^1)(7^1) = 14
• (2^2)(7^1) = 28
• (2^0)(7^2) = 49
• (2^1)(7^2) = 98

لقد توصلت إلى ما يلي:

factors n = [a|a<-map facs (primePowerFactors n), y <- [0..(snd $ last $ primePowerFactors n)]]
 where 
  facs (x,y) = (x,y)   
rSq n = toInteger $ round $ sqrt (fromInteger n)    
psr n = last $ dropWhile (<= rSq n) $ factors n
p = foldl' (*) 1 $ takeWhile (< 190) primes
answer = (psr p) `mod` (10^16)

لكن مشكلتي هي ذلك factors لا يعمل بشكل صحيح. أريد ذلك من خلال السماح بجميع القيم المحتملة للأسف لكل عامل رئيسي ثم ابحث عن المنتج لإعطاء العامل. كيف يمكن تعديلها للعودة فقط عوامل ن?

Answer 1

بالنسبة لبعض رمز الجولف، كتبت وظيفة لطيفة مجموعة الطاقة بسيطة جدا.

powerSet [] = []
powerSet (x:xs) = xs : map (x:) (powerSet xs) ++ (powerSet xs)

نقص هذه الخوارزمية هو أنه لا يشمل المجموعة الأصلية، ومع ذلك فإن هذا هو مثالي بالنسبة لك لأنها لا تبدو وكأنك تريد ذلك.

الجمع بين هذا مع وسيلة لتحويل الخاص بك primePowerFactors n في قائمة Ints، دعونا نقول

ppfToList = concatMap (\(x,y)->replicate y x)

باستخدام هؤلاء المساعدين، يتم إنشاء قائمة من العوامل من رقم N مع

factors n = nub . map product . powerSet . ppfToList . primePowerFactors $ n
-- will be out of order, you can add a call to `sort` to fix that

من المحتمل أن يكون هذا النوع من الخوارزمية أصعب بعض الشيء للتعبير عنها من حيث فهم قائمة.

Answer 2

أولاً، facs هي وظيفة الهوية:

facs (x,y) = (x,y)

ال y يرتبط في مباراة النمط على الجانب الأيسر بينما كنت ترغب في أن تكون y من فهم القائمة. الأسماء المتغيرة المنفصلة في فهم القائمة هي محلية لهذا الفهم ولا يمكن استخدامها في نطاق مختلف مثل where بند.

أيضا، y في الفهم القائمة محسوبة فقط من العوامل الأخيرة

y <- [0..(snd $ last $ primePowerFactors n)]

بالنسبة لكل عامل، يجب النظر في الأسهم، وليس فقط مجرد الأساس للعامل الأخير.

مشكلة أكثر جوهرية هي أن نوع العودة factors لا يبدو أن الوظيفة تتطابق مع نيتها:

*Euler> :t factors
factors :: Integer -> [(Integer, Int)]

هذا إرجاع قائمة صلاحيات العوامل الرئيسية بينما يجب أن تنتج قائمة بهذه البناء، مثل هذا:

[
   [(2,0), (7,0)],
   [(2,1), (7,0)],
   [(2,2), (7,0)],
   [(2,0), (7,1)],
   [(2,1), (7,1)],
   ...
]

هناك حاجة إلى العوامل الرئيسية لجميع العوامل الممكنة، ولكن يبدو أن الوظيفة تعود مجرد عامل رئيس واحد.