프로젝트 오일러 # 14

Question

나는 현재 해결하고

, Project Euler problem 14는 :

다음 반복 시퀀스가 ​​긍정적 인 정수의 집합에 대한 정의는 :

n → n/2 (n is even) 
n → 3n + 1 (n is odd) 

Using the rule above and starting with 13, we generate the following sequence: 
       13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 

Which starting number, under one million, produces the longest chain? 

내가 해결하기 위해 다음과 같은 알고리즘을 고안 문제 :

• 대신에 ea ch 번호를 별도로, 중복 계산이 많이 포함됩니다, 나는 1에서 거꾸로 시리즈를 개발하려고합니다. 즉, 숫자에서 시작하고 전에 요소를 예측.
• 여러 시리즈를 생성 할 수 있으므로 링크 된 목록을 사용하여 최근 시리즈 수를 저장하십시오. (아이디어는 더 긴 계열을 가진 요소 만 저장하는 것입니다.)
• 주어진 제한값 아래의 모든 숫자를 찾을 때까지 반복 할 것입니다. 한계 이하의 마지막 숫자는 가장 긴 시리즈를 갖습니다. 내가 예상대로

  void series_generate(long num) 
  { 
      long n = 1; 
      addhead(n);    //add 1 to list. 
      while (n < num) 
      { 
        series *p; 
        for (p = head; p != NULL; p = p->next) 
        { 
          long bf = p->num - 1; 
          if (p->num%2 == 0 && bf != 0 && bf%3 == 0) { 
            bf /= 3; 
            if (bf != 1) 
              addhead(bf); 
            if (bf < num) 
              n++; 
          } 
          p->num *= 2; 
          if (p->num < num) 
            n++; 
  
        }  
      }  
  } 
  

  Here is the link to complete code. 그러나, 나는 대답을하지 않는다 :

여기 내 코드입니다. 누구든지이 알고리즘이 작동하지 않는 이유를 추측 할 수 있습니까?

Answer 1

레벨 당 레벨의 Collatz 트리를 뒤로 만들려고합니다. 따라서 내부 루프의 k 번째 반복 이후에 목록에는 정확히 k 단계가 필요한 모든 숫자가 포함되어 Collatz 시퀀스에서 1에 도달합니다 (오버플로가 발생하지 않음).

이러한 접근에는 두 가지 심각한 문제가 있습니다.

1. 레벨의 크기는 기하 급수적으로 증가하며, 크기는 대략 3 레벨마다 대략 두 배가됩니다. 지나치게 많지 않은 레벨을 저장하는 데 필요한 메모리가 충분하지 않습니다.
2. k의 가장 큰 멤버는 2 ^k입니다. num 구성원의 사용 된 유형에 따라 레벨이 31, 32, 63 또는 64 인 경우 오버플로가 발생합니다. 그런 다음 서명 된 유형을 사용하면 정의되지 않은 동작이 발생하고 목록의 음수 일 수 있습니다. 부호없는 유형을 사용하는 경우 목록에 0이 포함되며 모든 것이 건방진 것으로 간주됩니다.

때마다 27 번 단계가 111 단계가 필요하므로 오버플로가 발생하므로 잘못된 결과가 발생합니다.