4
프로젝트 오일러 (http://projecteuler.net/problem=14)의 문제 14를 해결하려고하는데 하스켈을 사용하여 막 다른 골목에 섰습니다.프로젝트 오일러 번호 14 하스켈
이제는 숫자가 충분히 작아서 무차별 한 행동을 할 수는 있지만 그게 내 운동의 목적이 아니라는 것을 알고 있습니다. 나는 체인이 알고 40처럼 다른 번호를 검색 할 때 이제
for 13: the chain is 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
My map should contain :
13 - (True, 10)
40 - (False, 13)
20 - (False, 40)
10 - (False, 20)
5 - (False, 10)
16 - (False, 5)
8 - (False, 16)
4 - (False, 8)
2 - (False, 4)
1 - (False, 2)
:
- the first Integer (the key) holds the number
- the Tuple (Bool, Interger) holds either (True, Length) or (False, Number)
where Length = length of the chain
Number = the number before him
예 : 나는의 의미와 유형 Map Integer (Bool, Integer)의 Map의 중간 결과를 암기하는 것을 시도하고있다 (10 - 1) length 등이 있습니다. 10 개를 검색하면 길이가 (10 - 3) length이고 맵을 업데이트 할뿐만 아니라, 여전히 (False, _)의 경우 20, 40을 업데이트하려고합니다.
내 코드 :
import Data.Map as Map
solve :: [Integer] -> Map Integer (Bool, Integer)
solve xs = solve' xs Map.empty
where
solve' :: [Integer] -> Map Integer (Bool, Integer) -> Map Integer (Bool, Integer)
solve' [] table = table
solve' (x:xs) table =
case Map.lookup x table of
Nothing -> countF x 1 (x:xs) table
Just (b, _) ->
case b of
True -> solve' xs table
False -> {-WRONG-} solve' xs table
f :: Integer -> Integer
f x
| x `mod` 2 == 0 = x `quot` 2
| otherwise = 3 * x + 1
countF :: Integer -> Integer -> [Integer] -> Map Integer (Bool, Integer) -> Map Integer (Bool, Integer)
countF n cnt (x:xs) table
| n == 1 = solve' xs (Map.insert x (True, cnt) table)
| otherwise = countF (f n) (cnt + 1) (x:xs) $ checkMap (f n) n table
checkMap :: Integer -> Integer -> Map Integer (Bool, Integer) -> Map Integer (Bool, Integer)
checkMap n rez table =
case Map.lookup n table of
Nothing -> Map.insert n (False, rez) table
Just _ -> table
은 {-WRONG-} 부분에서 우리는 다음과 같은 예처럼 모든 값을 업데이트해야합니다
--We are looking for 10:
10 - (False, 20)
|
V {-finally-} update 10 => (True, 10 - 1 - 1 - 1)
20 - (False, 40) ^
| |
V update 20 => 20 - (True, 10 - 1 - 1)
40 - (False, 13) ^
| |
V update 40 => 40 - (True, 10 - 1)
13 - (True, 10) ^
| |
---------------------------
문제는 그것의 가능하면 내가 모르겠입니다 숫자를 업데이트하고 재 경기를 계속하는 것과 같은 기능으로 2 가지 일을하십시오. C 같은 언어에서 나는 (의사)과 같이 할 수 있습니다 : 우리가 참조에 의해 탄소 나노 튜브를 전송하기 때문에
void f(int n, tuple(b,nr), int &length, table)
{
if(b == False) f (nr, (table lookup nr), 0, table);
// the bool is true so we got a length
else
{
length = nr;
return;
}
// Since this is a recurence it would work as a stack, producing the right output
table update(n, --cnt);
}
마지막 명령이 작동합니다. 또한 우리는 항상 어떤 점에서 끝낼 것이고 cnt는 0이되어서는 안된다는 것을 알고 있습니다.
지도의 값 유형은 [정수형 정수 중 하나]로 더 관용적으로 표현됩니다 (http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Either). html)하지만, 아직 메모가 작성되지 않은 항목에 대해서는 매핑을 사용하지 않는 것이 더 편리하다고 생각합니다. –
업데이트 된 테이블을 다시 전달해야하는 이유는 무엇입니까? –
@groovy 전화 할 때 (내가 재현 중에있을 때) 나는 어떤 가치를 업데이 트해야하는지 모른다. 먼저 답변을 알고 나서 바닥에서부터 업데이트하기 전에 먼저 많은 재판을해야합니다. 예를 들어 10을 살펴보면 40, 20, 10으로 업데이트해야 할 것이 무엇인지 알기에 앞서 20, 40, 13로 가야합니다. – Thanatos