Задача о двух кучках камней - QBasic

Узнай цену своей работы

Формулировка задачи:

два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 1, а во второй - 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 2 камня в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 17 камней. Кто выигрывает при безошибочной игре обоих игроков - игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? очень срочно!!!

Решение задачи: «Задача о двух кучках камней»

textual
Листинг программы 
/* Thread 53742 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
/********************************************************************/
 
#define MAX_CONFIG_SIZE 500
#define MAX_NEXT_SIZE   4
 
#define CFG_NOT_PRESENT 0
#define CFG_WIN1        1
#define CFG_WIN2        2
#define CFG_WIN_UNK     3
#define CFG_SIZE        4
 
typedef struct {
    unsigned type;
    int index;
    int stone1, stone2;
    int prev_move, cur_move;
    int next[MAX_NEXT_SIZE];
} config_t;
 
 
/********************************************************************/
 
#define is_win_config( arg_pcfg )       \
    ((arg_pcfg)->stone1+(arg_pcfg)->stone2>=17)
 
 
#define calc_config_index( arg_pcfg )       \
    ((arg_pcfg)->index= (arg_pcfg)->stone1*50*2+(arg_pcfg)->stone2*2+((arg_pcfg)->cur_move-1))
 
 
/********************************************************************/
 
void do_calc_game( void );
void print_config_table( int size, const config_t *base );
void print_config_index_table( int size, int *base_index, const config_t *base );
void search_backward_config( int size, const config_t *base );
int search_config( const config_t *pcfg, int size, const config_t *base );
int cmp_cfg_index( const void *a, const void *b );
 
 
/********************************************************************/
 
char *cfg_text[CFG_SIZE]= {
    "undef", "win1", "win2", "unk"
};
config_t *glb_cfg_data= NULL;
 
 
/********************************************************************/
int main( void ) {
 
do_calc_game();
return 0;
 
} /* main() */
 
 
/********************************************************************/
void do_calc_game( void ) {
 
int i, cfg_i, cfg_size, next_i, type;
config_t cfg_data[MAX_CONFIG_SIZE], cfgt, *pcfg;
int cfg_index[MAX_CONFIG_SIZE];
 
 
/* First config */
memset( &cfgt, '\0', sizeof(cfgt) );
cfgt.type= CFG_WIN_UNK;
cfgt.stone1= 1; cfgt.stone2= 2;
cfgt.prev_move= 0; cfgt.cur_move= 1;
cfgt.next[0]= cfgt.next[1]= cfgt.next[2]= cfgt.next[3]= -1;
calc_config_index( &cfgt );
 
/* Init */
cfg_data[0]= cfgt; cfg_size= 1;
 
/* Game loop */
for ( cfg_i= 0; cfg_i<cfg_size; cfg_i++ ) {
    pcfg= &cfg_data[cfg_i];
    
    if ( is_win_config( pcfg ) ) {
        if ( pcfg->prev_move == 1 ) {
            pcfg->type= CFG_WIN1;
            pcfg->cur_move= 0;
        } else if ( pcfg->prev_move == 2 ) {
            pcfg->type= CFG_WIN2;
            pcfg->cur_move= 0;
        }
        continue;
    }
 
    memset( &cfgt, '\0', sizeof(cfgt) );
    cfgt.type= CFG_WIN_UNK;
    cfgt.prev_move= pcfg->cur_move;
    cfgt.cur_move= 3-cfgt.prev_move;
    cfgt.next[0]= cfgt.next[1]= cfgt.next[2]= cfgt.next[3]= -1;
 
    /* next variant 0 */
    cfgt.stone1= pcfg->stone1*3; cfgt.stone2= pcfg->stone2;
    calc_config_index( &cfgt );
    next_i= search_config( &cfgt, cfg_size, cfg_data );
    if ( next_i<0 ) {
        cfg_data[next_i= cfg_size]= cfgt;
        cfg_size++;
    }
    pcfg->next[0]= next_i;
 
    /* next variant 1 */
    cfgt.stone1= pcfg->stone1+2; cfgt.stone2= pcfg->stone2;
    calc_config_index( &cfgt );
    next_i= search_config( &cfgt, cfg_size, cfg_data );
    if ( next_i<0 ) {
        cfg_data[next_i= cfg_size]= cfgt;
        cfg_size++;
    }
    pcfg->next[1]= next_i;
 
    /* next variant 2 */
    cfgt.stone1= pcfg->stone1; cfgt.stone2= pcfg->stone2*3;
    next_i= search_config( &cfgt, cfg_size, cfg_data );
    calc_config_index( &cfgt );
    if ( next_i<0 ) {
        cfg_data[next_i= cfg_size]= cfgt;
        cfg_size++;
    }
    pcfg->next[2]= next_i;
 
    /* next variant 3 */
    cfgt.stone1= pcfg->stone1; cfgt.stone2= pcfg->stone2+2;
    next_i= search_config( &cfgt, cfg_size, cfg_data );
    calc_config_index( &cfgt );
    if ( next_i<0 ) {
        cfg_data[next_i= cfg_size]= cfgt;
        cfg_size++;
    }
    pcfg->next[3]= next_i;
 
}
 
/* Print */
#if 0
printf( "#config_table\n" );
print_config_table( cfg_size, cfg_data );
#endif
 
/* Create cfg_index, sort */
for ( cfg_i= 0; cfg_i<cfg_size; cfg_i++ ) {
    cfg_index[cfg_i]= cfg_i;
}
glb_cfg_data= cfg_data;
qsort( cfg_index, cfg_size, sizeof(cfg_index[0]), cmp_cfg_index );
 
printf( "#config_index_table\n" );
print_config_index_table( cfg_size, cfg_index, cfg_data );
 
/* Game loop by reverse index */
for ( cfg_i= cfg_size-1; cfg_i>=0; cfg_i-- ) {
    pcfg= &cfg_data[cfg_index[cfg_i]];
    if ( pcfg->type != CFG_WIN_UNK ) { continue; }
 
    if ( pcfg->cur_move == 1 ) {
        type= CFG_WIN2;
        for ( i= 0; i<MAX_NEXT_SIZE; i++ ) {
            if ( cfg_data[ pcfg->next[i] ].type == CFG_WIN1 ) {
                type= CFG_WIN1;
            } else if ( cfg_data[ pcfg->next[i] ].type == CFG_WIN2 ) {
            } else {
                goto err_internal;
            }
        }
    } else if ( pcfg->cur_move == 2 ) {
        type= CFG_WIN1;
        for ( i= 0; i<MAX_NEXT_SIZE; i++ ) {
            if ( cfg_data[ pcfg->next[i] ].type == CFG_WIN1 ) {
            } else if ( cfg_data[ pcfg->next[i] ].type == CFG_WIN2 ) {
                type= CFG_WIN2;
            } else {
                goto err_internal;
            }
        }
    } else {
        goto err_internal;
    }
    pcfg->type= type;
}
 
printf( "#config_table2\n" );
print_config_table( cfg_size, cfg_data );
 
/* Return */
return;
 
 
/* Processing error */
err_internal:
fprintf( stderr, "Internal error\n" );
exit( 1 );
 
} /* do_calc_game() */
 
 
/********************************************************************/
void print_config_table( int size, const config_t *base ) {
 
int i;
const config_t *pcfg;
 
 
for ( i= 0; i<size; i++ ) {
    pcfg= &base[i];
    printf( "i=%d type=%s index=%d move=%d,%d stone=%d,%d next=%d,%d,%d,%d\n",
        i, cfg_text[pcfg->type], pcfg->index,
        pcfg->prev_move, pcfg->cur_move, pcfg->stone1, pcfg->stone2,
        pcfg->next[0], pcfg->next[1], pcfg->next[2], pcfg->next[3]
    );
}
 
} /* print_config_table() */
 
 
/********************************************************************/
void print_config_index_table( int size, int *base_index, const config_t *base ) {
 
int i, index;
const config_t *pcfg;
 
 
for ( i= 0; i<size; i++ ) {
    index= base_index[i];
    pcfg= &base[index];
    printf( "i=%d index=%d type=%s index=%d move=%d,%d stone=%d,%d next=%d,%d,%d,%d\n",
        i, index, cfg_text[pcfg->type], pcfg->index,
        pcfg->prev_move, pcfg->cur_move, pcfg->stone1, pcfg->stone2,
        pcfg->next[0], pcfg->next[1], pcfg->next[2], pcfg->next[3]
    );
}
 
} /* print_config_index_table() */
 
 
/********************************************************************/
void search_backward_config( int size, const config_t *base ) {
 
int i;
const config_t *pcfg;
 
 
for ( i= 0; i<size; i++ ) {
    pcfg= &base[i];
    if ( (pcfg->next[0]>=0 && pcfg->next[0]<i) ||
        (pcfg->next[1]>=0 && pcfg->next[1]<i) ||
        (pcfg->next[2]>=0 && pcfg->next[2]<i) ||
        (pcfg->next[3]>=0 && pcfg->next[3]<i) ) {
        printf( "i=%d type=%s index=%d move=%d,%d stone=%d,%d next=%d,%d,%d,%d\n",
            i, cfg_text[pcfg->type], pcfg->index,
            pcfg->prev_move, pcfg->cur_move, pcfg->stone1, pcfg->stone2,
            pcfg->next[0], pcfg->next[1], pcfg->next[2], pcfg->next[3]
        );
    }
}
 
} /* search_backward_config() */
 
 
/********************************************************************/
int search_config( const config_t *pcfg, int size, const config_t *base ) {
 
int i;
 
 
for ( i= 0; i<size; i++ ) {
    if ( base[i].stone1 == pcfg->stone1 && base[i].stone2 == pcfg->stone2 &&
        base[i].cur_move == pcfg->cur_move ) {
        return i;
    }
}
return -1;
 
} /* search_config() */
 
 
#define INDEX2DATA( arg_ptr )   (&glb_cfg_data[ *((int*)(arg_ptr)) ])
 
/********************************************************************/
int cmp_cfg_index( const void *a, const void *b ) {
 
return INDEX2DATA(a)->index - INDEX2DATA(b)->index;
 
} /* cmp_cfg_index() */
 
#undef INDEX2DATA

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 3.714 из 5
Похожие ответы