예전에 테스트 해본다고 해놓고 정작 만들어 놓고 테스트는 팽개쳤던 코드 꺼내서 테스트 완료함.


http://ideone.com/QHcQzp


테스트한 재귀 함수 구조는 두가지야.


첫번째.


bool possible;


void play_game1( u32 game_index );


inline void test_case1( const u32 game_index, const RESULT result_a, const RESULT result_b )

{

    const u32 team_a = matches[ game_index ].first;

    const u32 team_b = matches[ game_index ].second;


    if( suppose[ team_a ].counts[ result_a ] + 1 <=

        results[ team_a ].counts[ result_a ] &&


        suppose[ team_b ].counts[ result_b ] + 1 <=

        results[ team_b ].counts[ result_b ] )

    {

        suppose[ team_a ].counts[ result_a ]++;

        suppose[ team_b ].counts[ result_b ]++;

        play_game1( game_index + 1 );

        suppose[ team_a ].counts[ result_a ]--;

        suppose[ team_b ].counts[ result_b ]--;

    }

}


void play_game1( u32 game_index )

{

    if( game_index >= matches.size() )

    {

        possible = true;

        return;

    }


    test_case1( game_index, win, lose );

    if( possible ) return;


    test_case1( game_index, lose, win );

    if( possible ) return;


    test_case1( game_index, even, even );

    if( possible ) return;

}


재귀 단계가 깊어져서 게임수를 만족할때까지 문제 없으면 가능한 조합임을 전역변수에 체크하고 빠져나오는데,

일일이 빠져나가는 구조지. 이게 불합리해 보여서 longjmp 로 구현해봄.

난 평소에 이런거 iteration 으로 구현하니 컴파일러 최적화가 어떻게될지 궁금했걸랑.


그래서 한방에 빠져나가는 코드를 longjmp 로 구현해봄.


두 번째.


#include <setjmp.h>


jmp_buf env;


void play_game2( u32 game_index );


inline void test_case2( const u32 game_index, const RESULT result_a, const RESULT result_b )

{

    const u32 team_a = matches[ game_index ].first;

    const u32 team_b = matches[ game_index ].second;


    if( suppose[ team_a ].counts[ result_a ] + 1 <=

        results[ team_a ].counts[ result_a ] &&


        suppose[ team_b ].counts[ result_b ] + 1 <=

        results[ team_b ].counts[ result_b ] )

    {

        suppose[ team_a ].counts[ result_a ]++;

        suppose[ team_b ].counts[ result_b ]++;

        play_game2( game_index + 1 );

        suppose[ team_a ].counts[ result_a ]--;

        suppose[ team_b ].counts[ result_b ]--;

    }

}


void play_game2( u32 game_index )

{

    if( game_index >= matches.size() )

        longjmp( env, 1 );


    test_case2( game_index, win, lose );

    test_case2( game_index, lose, win );

    test_case2( game_index, even, even );

}


전역변수 possible 대신 context 를 보관할 env 를 추가했지.


결과는


viewimage.php?id=3dafdf21f7d335ab67b1d1&no=29bcc427b38577a16fb3dab004c86b6fb8c469a51a456a5485032fed780bd3a4c8d4def1a6ca178c3fe966bfbe7b7ee8713e683ab877a79a4f842183f3