Haskell에서 인수화 방법을 구현합니다

StackOverflow https://stackoverflow.com/questions/1855561

  •  13-09-2019
  •  | 
  •  

문제

내가 뭐하는 거지 질문 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 제대로 작동하지 않습니다. 나는 각각의 주요 요인에 대한 지수의 모든 가능한 값을 구분하고 요인을 제공 할 제품을 찾기를 원합니다. 단지 요인을 반환하도록 어떻게 수정할 수 있습니까? N?

도움이 되었습니까?

해결책

일부 코드 골프의 경우 매우 간단한 멋진 파워 세트 기능을 썼습니다.

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

이 알고리즘의 결핍은 원래 세트를 포함하지 않지만 원하는 것처럼 보이지 않기 때문에 완벽합니다.

이것을 변환하는 방법과 결합하십시오 primePowerFactors n INT 목록으로 말하면

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

이러한 종류의 알고리즘은 아마도 목록 이해력으로 표현하기가 조금 더 어렵을 것입니다.

다른 팁

가장 먼저, 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)],
   ...
]

가능한 모든 요소의 주요 인자화가 필요하지만, 함수는 하나의 주요 인자화 만 반환하는 것으로 보입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top