UVa - 100 The 3n + 1 problem

특별 수 문제
그러나 특히 하나의 기록 으로 중복 계산 을 피하 여 복잡 도 를 낮 추 는 목적 을 달성 할 수 있다. 복잡 도가 높 은 이 유 는 이미 계 산 된 주기 길이 의 중복 계산 이기 때문에 이미 계 산 된 수의 주기 길 이 를 보존 해 야 한다.
제목
다음 알고리즘 을 고려 하 십시오: 1. n 2. 출력 n 3. n = 1 을 입력 한 다음 4. n 이 홀수 라면 n 5. 다른 상황: n 6. 2 로 전환 합 니 다. 예 를 들 어 입력 22 에 대해 서 는 출력 이 22 11 34 17 52 26 40 10 5 16 8 4 1 입 니 다.이 알고리즘 은 모든 정수 에 대해 1 로 종 료 될 것 으로 추정 된다.비록 알고리즘 이 매우 간단 하지만, 아직 이 추측 이 정확 한 지 아 닌 지 는 확실 하지 않다.그러나 모든 정수 n (0 < n < 1, 000, 000) 에 대해 이미 검증 을 거 쳤 다.주어진 n 에 대해 서 는 이 알고리즘 이 모두 몇 개의 수 를 출력 했 는 지 계산 할 수 있 습 니 다. 마지막 1 을 포함 하여 이 수 는 n 의 주기 길이 라 고 합 니 다.위의 예 에서 22 의 주기 길 이 는 16 이다.모든 두 개의 숫자 i 와 j 에 대해 i 와 j 사이 의 수 에서 주기 길이 가 가장 큰 그 수의 주기 길 이 를 구한다.
AC 코드
이 코드 는 서로 다른 OJ 에서 의 운행 시간 UVa - 100 20ms POJ - 1207 16ms SDUSTOJ - 1049 224 ms (백 스테이지 데이터 가 특별히 카드 시간 을 초과 하여 복잡 도 를 높 일 수 밖 에 없 음)

#include 
#include 
#include 
int s[1000100];

int problem( int n )
{
    int num = 1;
    while( n != 1 )
    {
        if( n % 2 != 0 )
            n = n * 3 + 1;
        else
            n /= 2;
        num++;
    }
    return num;
}

int main()
{
    int i, j;
    memset( s , 0 , sizeof(s) );
    while( ~scanf("%d%d",&i,&j) )
    {
        printf("%d %d",i,j);
        if(i > j)  //   ,            i,j
        {
            int t = i;
            i = j;
            j = t;
        }
        int m = 0;
        for( int k = i ; k <= j ; k++ )
        {
            if( !s[k] )  //
                s[k] = problem(k);
            m = s[k] > m ? s[k] : m;
        }
        printf(" %d
",m);
    }
    return 0;
}