언어 자료구조 알고리즘/디딤돌 알고리즘 (C언어)

[C언어 알고리즘] 6.1.3 순열 알고리즘 테스트 코드 작성

언제나 휴일 언제나휴일 2016. 12. 1. 10:48
반응형

[C언어 알고리즘] 6.1.3 순열 알고리즘 테스트 코드 작성


 먼저 시뮬레이션에 사용할 초기 바구니에 넣을 공의 집합을 생성하는 함수를 작성할게요.

Array * InitSimulation()

{

    int ball = 0;

    Array *bucket = 0;

 먼저 동적 배열을 생성합니다.

    bucket = New_Array();

 0번 공부터 9번 공까지 순차적으로 이동하면서 배열에 순차 보관합니다.

    for(ball = 0; ball<=9; ++ball)

    {

 보관할 자료형이 포인터 형식이 아니므로 강제 형변환하여 보관할게요.

        Array_PushBack(bucket,(Element)ball);

    }

 공을 보관한 배열을 반환합니다.

    return bucket;

}

 

 이제 테스트 코드를 작성합시다.

 int main()

{

 테스트를 위해 스택이 필요하므로 변수를 선언합시다.

    EHStack *ehs = 0;

 경험 정보도 필요하므로 변수를 선언합시다.

    Heuristic *heu = 0;

 

 초기에 공을 보관할 배열을 위한 변수도 선언합니다.

    Array *bucket = 0;

 알고리즘 내부에서는 현재 경험에서 다음 경험 목록을 조사해야 합니다. 이 때 다음 경험 목록을 보관할 배열이 필요하므로 이를 위한 변수도 선언합시다.

    Array *next_heus = 0;

 조사한 경험 목록을 순차적으로 방문해야 하므로 반복자도 선언합시다.

    Iterator seek=0, end=0;

 먼저 바구니에 담을 공의 집합을 동적으로 생성하는 InitSimulation 함수를 호출합니다.

    bucket = InitSimulation();

 

 순열 알고리즘 테스트 코드를 작성하기 전에 동적 알고리즘을 다시 한 번 살펴봅시다.

 

동적 알고리즘

    초기 경험 정보를 생성

    스택에 초기 경험 정보 Push

    반복(스택이 빌 때까지)

        스택에서 경험 정보를 Pop

        꺼낸 온 경험에서 발생할 수 있는 다음 경험 정보 조사

        반복(다음 경험 정보들을 순차적으로)

            조건(결과에 도달하지 않았다면)

                스택에 경험 정보를 Push

            그렇지 않다면

                결과에 보관

 

 먼저 스택을 생성합니다.

    ehs = New_EHStack();

 초기 경험 정보를 생성하고 이를 스택에 보관합니다.

    heu = MakeInitHeuristic(bucket);

    EHStack_Push(ehs,heu);

 스택이 빌 때까지 반복합니다.

    while( ! EHStack_IsEmpty(ehs) )

    {

 스택에서 경험 정보를 꺼내옵니다.

        heu = (Heuristic *)EHStack_Pop(ehs);

 현재 경험정보에서 다음 경험 정보를 조사합니다. 이를 위해 다음 경험 정보를 보관할 동적 배열도 생성합니다.

        next_heus = New_Array();

        FindNextHeuristics(heu,next_heus);

 조사한 다음 경험 정보의 시작과 끝을 얻어옵니다.

        seek = Array_Begin(next_heus);

        end = Array_End(next_heus);

 순차적으로 이동하면서 다음 경험 정보를 참조합니다.

        for(seek=seek; seek != end; ++seek)

        {

            heu = (Heuristic *)(*seek);

 만약 결론에 도달했다면 이를 출력하고 동적 경험 정보를 소멸할게요. 여기에서는 3개의 공을 꺼냈을 때 결론에 도달한 것으로 할게요.

            if(GetOutCount(heu) == 3)

            {

                ViewHeuristic(heu);

                DeleteHeuristic(heu);

            }

 결론에 도달하지 않으면 다시 스택에 보관합니다.

            else

            {

                EHStack_Push(ehs,heu);

            }

        }

 다음 경험 정보를 보관했던 동적 배열을 소멸합니다.

        Delete_Array(next_heus);

    }

 시뮬레이션에 사용한 버켓과 스택을 소멸합니다.

    Delete_Array(bucket);

    Delete_EHStack(ehs);

    return 0;

}

 

 출력 결과가 하나의 콘솔 화면의 범위를 벗어나서 확인하기 까다롭다면 콘솔 명령 화면에서 다음과 같이 실행해 보세요.

[그림 6.3] 콘솔 명령어에서 파이프 사용

[그림 6.3] 콘솔 명령어에서 파이프 사용

 

 [그림 6.3]처럼 콘솔 명령어를 사용하면 >> 뒤에 명시한 파일로 출력합니다. 결과 파일을 더블 클릭하여 원하는 모든 결과를 출력하는지 확인해 보세요.

반응형