하스켈의 Int형은 최대값이 2,147,483,647입니다. 그런데 113383은 2,482,111,348까지 올라갑니다. 이 값은 Int의 최대값을 넘어가기 때문에 -1,812,855,948가 됩니다. 그 다음에는 무한루프에 빠집니다. 그래서 step 함수의 타입이 Int -> Int인 이상 [1..113382]을 넘어서는 범위에선 정상적으로 작동하지 않습니다.
type signature를 지워버리면 이 문제를 간단히 해결할 수 있습니다. GHC의 자료형 추론 기능은 정수값의 경우 그 범위가 무한대인 Integer를 기본으로 하기 때문입니다.
하지만 Integer는 Int보다 훨씬 느리다는 단점이 있습니다. 제가 내놓는 해결책은 이렇습니다. Int의 최대값 밑에선 Int로 빨리 계산을 하고, 위에선 느리더라도 Integer로 계산하는 거죠. 이제 계산은 5초만에 끝납니다. 굉장하죠? 코드는 아래와 같습니다.
{-# OPTIONS -fbang-patterns #-}
import System.CPUTime (getCPUTime)
-- Int로 계산하는 함수
step :: Int -> Int -> Int
step !len 1 = len
step !len !a
| even a = step (len+1) $! div a 2
| a < upperBound = step (len+1) $! 3*a+1
| otherwise = bigStep (len+1) $! 3*(fromIntegral a)+1
where upperBound = div (maxBound :: Int) 3 - 1
-- Integer로 계산하는 함수
bigStep :: Int -> Integer -> Int
bigStep !len 1 = len
bigStep !len !a
| odd a = bigStep (len+1) $! 3*a+1
| a > lowerBound = bigStep (len+1) $! div a 2
| otherwise = step (len+1) $! div (fromIntegral a) 2
where lowerBound = fromIntegral $ (maxBound :: Int) * 2 :: Integer
walk = step (1::Int)
main = do
n <- getLine >>= return . read
print $ maximum $ map walk [1..n]
getCPUTime >>= print . (/1000000000000) . fromIntegral
참고로 문제의 113383을 Int로 계산할 경우 진행은 아래와 갔습니다. 맨 마지막에 강조한 부분이 무한루프입니다.
let tnpo n =
let rec next result =
let x = List.hd result in
if x = 1 then result
else if (x mod 2) = 0 then next ( (x/2)::result )
else next ( (3*x+1)::result )
in
List.rev ( next [n] )
;;
Integer>>threeNPlusOne
| n list |
list := OrderedCollection new.
n := self.
[ (list add: n) = 1 ] whileFalse: [ n := n even ifTrue: [ n / 2 ] ifFalse: [ n * 3 + 1 ] ].
^list.
let rec threeone x =
if x = 1 then [1]
else if (x mod 2) = 0 then x :: (threeone (x/2))
else x :: (threeone (3*x+1))
;;
List.map (Printf.printf "%d ") (threeone 50);;
하스켈과 자바스크립트
하스켈로 푼 답안입니다.
threeOnePlus n = takeWhile (/=1) (iterate f n) ++ [1] where f x = if even x then div x 2 else 3*x+1자바스크립트로 푼 답안입니다.
function threeOnePlus(n) { var lst = [] while( n != 1) { lst.push(n) if( n % 2 == 0 ) n = n/2 else n = 3*n+1 } lst.push(1) return lst }C++ 템플릿 메타프로그래밍을 이용한 풀이
Rica님의 C++ 템플릿 메타프로그래밍을 이용한 풀이
1부터 M까지의 cycle length 중 가장 큰 cycle length 구
http://colus.egloos.com/3365017
위와 같이 하스켈로 풀었습니다. strict도 나름대로 시도해보았지만 안되는 건 마찬가지더군요. 1000000까지 돌리면 스택 오버플로가 나버리거나 프로그램이 끝나지를 않습니다. 1000000까지 가능하게 하려면 어떻게 최적화 해야 할까요?
컴파일러는 GHC를 썼습니다. Hugs나 NHC 등으로 하면 될까요?
maximum [1..1000000]에서
maximum [1..1000000]에서 스택 오버플로우가 나신다면 십중팔구 ghci에서 실행시키셨겠군요. ghci는 ghc에 딸려오는 인터프리터로 엄청 구립니다. ghc는 gcc frontend로 작동하는 컴파일러로서 제법 괜찮은 (바이트코드가 아니라)바이너리를 생성합니다. 제 컴퓨터(펜티엄D 2.6GHz, 1GB)에선 -O2 옵션주고 컴파일한 결과물은 계산을 끝내는데 40초 정도 걸립니다.
네 maximum [1..1000000]는
네 maximum [1..1000000]는 ghci에서 테스트 해봤습니다. 안보고도 아시다니 ^.^
ghc -O2 3np1.hs로 최적화 옵션을 주니 스택오버플로 에러는 안납니다. 그런데 실행을 시켜면 30분이 지났는데도 여전히 끝이 안납니다. 제 맥북은 Core2Duo 2.0GHz에 램은 2G나 되는데도요.
제가 올린 소스를 그대로 돌려보셨나요? 다른 구현으로 돌려보셨다면 좀 보여주세요 ^.^
하스켈의 Int형은
하스켈의 Int형은 최대값이 2,147,483,647입니다. 그런데 113383은 2,482,111,348까지 올라갑니다. 이 값은 Int의 최대값을 넘어가기 때문에 -1,812,855,948가 됩니다. 그 다음에는 무한루프에 빠집니다. 그래서 step 함수의 타입이 Int -> Int인 이상 [1..113382]을 넘어서는 범위에선 정상적으로 작동하지 않습니다.
type signature를 지워버리면 이 문제를 간단히 해결할 수 있습니다. GHC의 자료형 추론 기능은 정수값의 경우 그 범위가 무한대인 Integer를 기본으로 하기 때문입니다.
하지만 Integer는 Int보다 훨씬 느리다는 단점이 있습니다. 제가 내놓는 해결책은 이렇습니다. Int의 최대값 밑에선 Int로 빨리 계산을 하고, 위에선 느리더라도 Integer로 계산하는 거죠. 이제 계산은 5초만에 끝납니다. 굉장하죠? 코드는 아래와 같습니다.
{-# OPTIONS -fbang-patterns #-} import System.CPUTime (getCPUTime) -- Int로 계산하는 함수 step :: Int -> Int -> Int step !len 1 = len step !len !a | even a = step (len+1) $! div a 2 | a < upperBound = step (len+1) $! 3*a+1 | otherwise = bigStep (len+1) $! 3*(fromIntegral a)+1 where upperBound = div (maxBound :: Int) 3 - 1 -- Integer로 계산하는 함수 bigStep :: Int -> Integer -> Int bigStep !len 1 = len bigStep !len !a | odd a = bigStep (len+1) $! 3*a+1 | a > lowerBound = bigStep (len+1) $! div a 2 | otherwise = step (len+1) $! div (fromIntegral a) 2 where lowerBound = fromIntegral $ (maxBound :: Int) * 2 :: Integer walk = step (1::Int) main = do n <- getLine >>= return . read print $ maximum $ map walk [1..n] getCPUTime >>= print . (/1000000000000) . fromIntegral참고로 문제의 113383을 Int로 계산할 경우 진행은 아래와 갔습니다. 맨 마지막에 강조한 부분이 무한루프입니다.
113383,340150,170075,510226,255113,765340,382670,191335,574006,287003,861010,43
0505,1291516,645758,322879,968638,484319,1452958,726479,2179438,1089719,3269158,
1634579,4903738,2451869,7355608,3677804,1838902,919451,2758354,1379177,4137532,2
068766,1034383,3103150,1551575,4654726,2327363,6982090,3491045,10473136,5236568,
2618284,1309142,654571,1963714,981857,2945572,1472786,736393,2209180,1104590,552
295,1656886,828443,2485330,1242665,3727996,1863998,931999,2795998,1397999,419399
8,2096999,6290998,3145499,9436498,4718249,14154748,7077374,3538687,10616062,5308
031,15924094,7962047,23886142,11943071,35829214,17914607,53743822,26871911,80615
734,40307867,120923602,60461801,181385404,90692702,45346351,136039054,68019527,2
04058582,102029291,306087874,153043937,459131812,229565906,114782953,344348860,1
72174430,86087215,258261646,129130823,387392470,193696235,581088706,290544353,87
1633060,435816530,217908265,653724796,326862398,163431199,490293598,245146799,73
5440398,367720199,1103160598,551580299,1654740898,827370449,-1812855948,-9064279
74,-453213987,-1359641960,-679820980,-339910490,-169955245,-509865734,-254932867
,-764798600,-382399300,-191199650,-95599825,-286799474,-143399737,-430199210,-21
5099605,-645298814,-322649407,-967948220,-483974110,-241987055,-725961164,-36298
0582,-181490291,-544470872,-272235436,-136117718,-68058859,-204176576,-102088288
,-51044144,-25522072,-12761036,-6380518,-3190259,-9570776,-4785388,-2392694,-119
6347,-3589040,-1794520,-897260,-448630,-224315,-672944,-336472,-168236,-84118,-4
2059,-126176,-63088,-31544,-15772,-7886,-3943,-11828,-5914,-2957,-8870,-4435,-13
304,-6652,-3326,-1663,-4988,-2494,-1247,-3740,-1870,-935,-2804,-1402,-701,-2102,
-1051,-3152,-1576,-788,-394,-197,-590,-295,-884,-442,-221,-662,-331,-992,-496,-2
48,-124,-62,-31,-92,-46,-23,-68,-34,-17,-50,-25,-74,-37,-110,-55,-164,-82,-41,-1
22,-61,-182,-91,-272,-136,-68,...
정확한 이유
Data.List 모듈을 import하고 maximum 대신 foldl1' max을 사용하면 ghci에서도 스택 넘침을 막을 수 있습니다. 스택 넘침: foldl과 foldr을 참조하세요.
OCaml
Smalltalk 버전
(실행 예)
100 threeNPlusOne.
-> an OrderedCollection(100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1)
제가 나름대로 생각해본 Haskell 코드입니다
파이썬 코드입니다.~
result = []
while(n is not 1): n = n/2 if n %2 is 0 else 3*n + 1; result.append(n)
일부러 한줄러 쓴게 아니라 코드로 쓰는법을 몰라서 ;;
OCaml
codepad.org에서 동작을 확인했습니다. 함수형 언어로 코딩하는건 어렵네요 ㄷㄷㄷ
프롤로그로 푼 답안입니다.
tnpo(1, [1]).
tnpo(I, [I|R]) :- T is I mod 2, T is 0 , U is I/2, tnpo(U, R), !.
tnpo(I, [I|R]) :- T is I mod 2, T is 1 , U is I*3+1, tnpo(U, R), !.
큰 수는 못다루겠어요.. 프롤로그에 익숙치 않네요.
scheme
(define (3n+1-list n) (cond ((= n 1) '(1)) ((even? n) (cons n (3n+1-list (/ n 2)))) (else (cons n (3n+1-list (+ (* n 3) 1))))))ruby
def f(n) return [1] if n == 1 return [n] | f(n/2) if n.even? return [n] | f(n*3+1) endor
def f(n) arr = [n] until n == 1 if n.even? then n = n / 2 else n = n * 3 + 1 end arr.push(n) end arr endruby
def f(n)
p n
n==1&&1||n.even?&&f(n/2)||f(n*3+1)
end
f(22)