하스켈의 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);;
Collatz의 추측은 수학 Lothar Collatz, 처음으로 1937 년에 그것을 제안한 후라는 미해결 추측이다. 추측도 3n + 1 추측으로 알려져 있습니다, Stanislaw Ulam 후 Ulam의 추측 (), Shizuo Kakutani 후 Kakutani의 문제 (), 선생님 브라이언 Thwaites 후 Thwaites의 추측 (), 헬무트 Hasse 후 Hasse의 알고리즘 () 또는 시러큐스 문제; 숫자 관련된 시퀀스에 우박 시퀀스 또는 우박 번호, 또는 놀라운 숫자로 언급됩니다.
북아 어떤 자연의 번호를 가지고 n은 심지어 경우 n은 3을 곱하면 홀수 경우 얻을 수 1을 추가하여 n을 2 / 2 얻으려면 그것을 나누어 3n + 1. 이 과정을 반복 무기한. 추측은 어떤 번호로 시작 상관없이, 당신은 항상 결국 1에 도달하게됩니다. 그것은이라는 평가가있다 "절반 또는 트리플 플러스 1", 가끔 HOTPO했다. [4]
폴 에르 되시가 Collatz은 추측에 대해 말했다 : "수학은 아직 이런, 열세, 혼란과 어려운 문제에 대한 준비가되지 않습니다." 그는 미국에게 자사의 솔루션에 대한 500 달러를 제안했다.
2006 년, 연구자 커츠 사이먼과, JH하여 이전 작업에 건물 콘웨이는 1970 년대, 그 Collatz 문제의 천연 일반화가 undecidable입니다이었다. 이 증거가 일반화 달려 그러나, 그것은 원래의 Collatz 문제에 적용할 수 없습니다.
-------------------------------------------------------- certification dumps | apple braindumps | oracle 9i certification dumps
어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 scjp + 91 = 101이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. microsoft certification 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 + 91 = 101이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 cisco certification 지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 ccvp 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.
하스켈과 자바스크립트
하스켈로 푼 답안입니다.
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)
Collatz의 추측은 수학
Collatz의 추측은 수학 Lothar Collatz, 처음으로 1937 년에 그것을 제안한 후라는 미해결 추측이다. 추측도 3n + 1 추측으로 알려져 있습니다, Stanislaw Ulam 후 Ulam의 추측 (), Shizuo Kakutani 후 Kakutani의 문제 (), 선생님 브라이언 Thwaites 후 Thwaites의 추측 (), 헬무트 Hasse 후 Hasse의 알고리즘 () 또는 시러큐스 문제; 숫자 관련된 시퀀스에 우박 시퀀스 또는 우박 번호, 또는 놀라운 숫자로 언급됩니다.
북아 어떤 자연의 번호를 가지고 n은 심지어 경우 n은 3을 곱하면 홀수 경우 얻을 수 1을 추가하여 n을 2 / 2 얻으려면 그것을 나누어 3n + 1. 이 과정을 반복 무기한. 추측은 어떤 번호로 시작 상관없이, 당신은 항상 결국 1에 도달하게됩니다. 그것은이라는 평가가있다 "절반 또는 트리플 플러스 1", 가끔 HOTPO했다. [4]
폴 에르 되시가 Collatz은 추측에 대해 말했다 : "수학은 아직 이런, 열세, 혼란과 어려운 문제에 대한 준비가되지 않습니다." 그는 미국에게 자사의 솔루션에 대한 500 달러를 제안했다.
2006 년, 연구자 커츠 사이먼과, JH하여 이전 작업에 건물 콘웨이는 1970 년대, 그 Collatz 문제의 천연 일반화가 undecidable입니다이었다. 이 증거가 일반화 달려 그러나, 그것은 원래의 Collatz 문제에 적용할 수 없습니다.
--------------------------------------------------------
certification dumps | apple braindumps | oracle 9i certification dumps
어떤 자연수 n이 있을
어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 scjp + 91 = 101이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. microsoft certification 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 + 91 = 101이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 cisco certification 지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 ccvp 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.