[완료] 더해서 임의의 n이 되는 자연수의 집합
글쓴이: kibaejjang / 작성시간: 수, 2009/02/18 - 11:01오전
더해서 임의의 n이 되는 자연수의 집합을을 만들려면 어떻게 해야 하나요?
예를들어, 5를 주면 {4,1}, {3,2}, {3,1,1}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1}
이런 집합을 찾고 싶습니다.
Forums:
더해서 임의의 n이 되는 자연수의 집합을을 만들려면 어떻게 해야 하나요?
예를들어, 5를 주면 {4,1}, {3,2}, {3,1,1}, {2,2,1}, {2,1,1,1}, {1,1,1,1,1}
이런 집합을 찾고 싶습니다.
효율을 생각하지
효율을 생각하지 않고 간단히 생각해 본다면,
우선 주어진 수 부터 1까지의 내림차수의 수 목록을 만들 수 있겠네요.
그 수열의 첫 수에서부터 자기보다 작은 수들과 순서대로 더하기를 해 봐서
원하는 값 보다 크면 바로 종료하고, 원하는 값이 나오거나 더 적은 값이 나오면
계속 recursive하게 체크를 할 수 있겠네요.
이 문제가 다분히 수학적인거라 Haskell로 구현해 볼 수 있지 않을까 하다가
저도 인터넷문서 보고 따라해보고 만 단계라 어려워 구현을 못했는데
호기심으로 인터넷을 뒤져보니 누가 구현해 놓은게 있군요.
http://davidvollbracht.com/2008/7/1/30-days-of-tech-day-30-haskell-decompose
다음의 코드면 계산이 되네요
decompose n = nub (decompositions n (floor ((toRational n)/2)))
decompositions n 0 = [[n]]
decompositions n m = nmCombinations ++ decompositions n (m - 1) where
nmCombinations = [a ++ b | a <- (decompose (n - m)), b <- (decompose m)]
단, 이 코드는 주어진 값도 포함해서 출력합니다.
잘 보시면 원하시는 C나 C++코드로도 변환하실 수 있을 듯...
-------------------------------------------------
$yes 4 8 15 16 23 42
-------------------------------------------------
$yes 4 8 15 16 23 42
정확히 일치하는 문제네요...
전혀 감을 못 잡고 있었는데.. 감사합니다.
HASKELL이란 것도 처음 알았습니다.
더 빠르게
더 빠르게 작동하도록 다른 방식으로 만들어봤습니다.
_decompose 0 _ = [ [] ] _decompose n 1 = [ [ (n,1) ] ] _decompose n max = ( _decompose n (max-1) ) ++ [ (i,max) : sub_decomposition | i <- [1 .. n `div` max] , sub_decomposition <- _decompose (n-max*i) (max-1) ] decompose n = map (concat . (map $ uncurry replicate)) $ _decompose n n--------------------Signature--------------------
Light a candle before cursing the darkness.
앗, 제가 Haskell
앗, 제가 Haskell 이라는 언어에 흥미를 갖게 해 주신 분이셨군요.
위 코드는 참 깔끔하고 이해하기 쉬운 코드인 것 같습니다.
-------------------------------------------------
$yes 4 8 15 16 23 42
-------------------------------------------------
$yes 4 8 15 16 23 42
다이나믹의
다이나믹의 응용이로군요.
뭐 막쌍 써보고나니 위의 코드하고 똑같짐서도...
Decomposing의 경우수를 구하는 다이나믹 알고리즘 점화식은 다음과 같습니다.
이걸 경우의 수가 아니라 조합을 저장하는 배열로 바꾸면 되는군요.
이마만큼 해줬는데 이거 못짜면 그냥 전과하는게 나을겁니다 = _=)+
위의 분이 써주신
위의 분이 써주신 것하고 이 수학식하고 대응시키면서 이해하려고 노력하고 있습니다.
전산과는 아니지만..^^ 함 c로 구현해 보고 올리도록 노력해보겠습니다.
도와주셔서 감사~!
댓글 달기