我有穷举代码，但是我觉得这道题 其实可以用递归做。

学习

不会

这是一个ACM题目，周一的时候我刚在图书馆看到，特此奉上书中的详解：

// 某保密单位机要人员 A，B，C，D，E 每周需要工作5天，休息2天。

//

// 上级要求每个人每周的工作日和休息日安排必须是固定的，不能在周间变更。

// 此外，由于工作需要，还有如下要求：

// 1. 所有人的连续工作日不能多于3天（注意：周日连到下周一也是连续）。

// 2. 一周中，至少有3天所有人都是上班的。

// 3. 任何一天，必须保证 A B C D 中至少有2人上班。

// 4. B D E 在周日那天必须休息。

// 5. A E 周三必须上班。

// 6. A C 一周中必须至少有4天能见面（即同时上班）。

//

// 你的任务是：

// 编写程序，列出ABCDE所有可能的一周排班情况。工作日记为1，休息日记为0   

// A B C D E 每人占用1行记录，从星期一开始。

//

//【输入、输出格式要求】

// 程序没有输入，要求输出所有可能的方案。

// 每个方案是7x5的矩阵。只有1和0组成。           

// 矩阵中的列表示星期几，从星期一开始。

// 矩阵的行分别表示A，B，C，D，E的作息时间表。

// 多个矩阵间用空行分隔开。

// 例如，如下的矩阵就是一个合格的解。请编程输出所有解(多个解的前后顺序不重要)。

//      0110111

//      1101110

//      0110111

//      1101110

//      1110110

//  用C语言编写

#include "stdlib.h"

int getOnes( int val )

{

    int counts = 0;

    int i = 0;

    for( i = 0 ; i < 8*sizeof(val) ; i++ ){

        counts += ((1<<i)&val)>0?1:0;

    }

    return counts;

}

void printSchedule( char* info, int schedule, int size )

{

    int i;

    printf("%s: %02X (", info,schedule );

    for(i = size*8-1; i >= 0 ; --i){

        printf("%d", ((1<<i)&schedule)>0?1:0 );

    }

    printf(")\n");

}

void printResult( unsigned char schedule )

{

    int i;

    for(i = 6; i >= 0 ; --i){

        printf("%d", ((1<<i)&schedule)>0?1:0 );

    }

    printf("\n");

}

int main(int argc, char const *argv[])

{

    // result

    int schedule_a = 0;

    int schedule_b = 0;

    int schedule_c = 0;

    int schedule_d = 0;

    int schedule_e = 0;

    // possible schedules

    unsigned char pos_schedules[0xFF] = {0};

    int pos_schedules_count = 0;

    int free_day_one = 0;

    int free_day_two = 0;

    unsigned char schedule;

    // rule 1

    unsigned short rule_1 = 0x000F;

    unsigned short rule_1_checker = 0;

    unsigned short rule_1_result = 0;

    // rule 2

    unsigned char rule_2 = 0;

    // rule 3

    unsigned char rule_3 = 0;

    unsigned char rule_3_result = 0;

    // rule 4

    unsigned char rule_4 = 0;

    // rule 5

    unsigned char rule_5 = 0;

    // rule 5

    unsigned char rule_6 = 0;

    // helpers

    int i;

    int total_schedules = 0;

    // search for the possible schedules

    for(free_day_one = 0; free_day_one < 7; ++free_day_one){

        for(free_day_two = free_day_one; free_day_two < 7; ++free_day_two){

            // rule 0, 每周需要工作5天，休息2天

            if( free_day_one != free_day_two  ){

                // get a schedule

                schedule = (~(1<<free_day_one)) & (~(1<<free_day_two)) & 0x7F;

                // rule 1, 所有人的连续工作日不能多于3天

                //          （注意：周日连到下周一也是连续）

                // expand schedule 7 days (8 bits) to 14 days ( 16 bits )

                rule_1_checker   = schedule;

                rule_1_checker <<= 7;

                rule_1_checker  |= schedule;

                rule_1 = 0x000F;

                rule_1_result = 1;

                for(i = 0; i < 14-3; ++i){

                    rule_1_result = rule_1_result

                                && ((rule_1_checker&rule_1)!=rule_1);

                    rule_1 <<= 1;

                }

                if( rule_1_result ){

                    pos_schedules[pos_schedules_count++] = schedule;

                    // printSchedule("schedule",schedule,sizeof(schedule) );

                    // printf("day1:%d day2:%d\n", free_day_one,free_day_two);

                }

            }

        }

    }

    // get candler

    for (schedule_a = 0; schedule_a < pos_schedules_count; ++schedule_a){

    for (schedule_b = 0; schedule_b < pos_schedules_count; ++schedule_b){

    for (schedule_c = 0; schedule_c < pos_schedules_count; ++schedule_c){

    for (schedule_d = 0; schedule_d < pos_schedules_count; ++schedule_d){

    for (schedule_e = 0; schedule_e < pos_schedules_count; ++schedule_e){

        // rule 2, 一周中，至少有3天所有人都是上班的。

        rule_2 = pos_schedules[schedule_a] &

                 pos_schedules[schedule_b] &

                 pos_schedules[schedule_c] &

                 pos_schedules[schedule_d] &

                 pos_schedules[schedule_e] ;

        if( getOnes(rule_2) < 3 ){

            continue;

        }

        // rule 3, 任何一天，必须保证 A B C D 中至少有2人上班。

        rule_3_result = 1;

        for (i = 0; i < 7; ++i){

            rule_3   = (pos_schedules[schedule_a]&(1<<i))>0?1:0;

            rule_3 <<= 1;

            rule_3  |= (pos_schedules[schedule_b]&(1<<i))>0?1:0;

            rule_3 <<= 1;

            rule_3  |= (pos_schedules[schedule_c]&(1<<i))>0?1:0;

            rule_3 <<= 1;

            rule_3  |= (pos_schedules[schedule_d]&(1<<i))>0?1:0;

            rule_3_result = rule_3_result && (getOnes(rule_3)>=2);

        }      

        if( ! rule_3_result ){

            continue;

        }

        // rule 4, B D E 在周日那天必须休息。

        rule_4 = 1;

        rule_4 = rule_4 && ((pos_schedules[schedule_b]&0x01)==0);

        rule_4 = rule_4 && ((pos_schedules[schedule_d]&0x01)==0);

        rule_4 = rule_4 && ((pos_schedules[schedule_e]&0x01)==0);

        if ( ! rule_4 ){

            continue;

        }

        // rule 5, A E 周三必须上班。

        rule_5 = 1;

        rule_5 = rule_5 && ((pos_schedules[schedule_a]&0x10)>0);

        rule_5 = rule_5 && ((pos_schedules[schedule_e]&0x10)>0);

        if ( ! rule_5 ){

            continue;

        }

        // rule 6, A C 一周中必须至少有4天能见面（即同时上班）。

        rule_6 = pos_schedules[schedule_a] & pos_schedules[schedule_c];

        if( getOnes(rule_6) < 4 ){

            continue;

        }

            

        // passed all rules

        // printf("result\n");

        // printSchedule("schedule_a",pos_schedules[schedule_a],

        //              sizeof(pos_schedules[schedule_a]) );

        // printSchedule("schedule_b",pos_schedules[schedule_b],

        //              sizeof(pos_schedules[schedule_b]) );

        // printSchedule("schedule_c",pos_schedules[schedule_c],

        //              sizeof(pos_schedules[schedule_c]) );

        // printSchedule("schedule_d",pos_schedules[schedule_d],

        //              sizeof(pos_schedules[schedule_d]) );

        // printSchedule("schedule_e",pos_schedules[schedule_e],

        //              sizeof(pos_schedules[schedule_e]) );

            

        printResult(pos_schedules[schedule_a]);

        printResult(pos_schedules[schedule_b]);

        printResult(pos_schedules[schedule_c]);

        printResult(pos_schedules[schedule_d]);

        printResult(pos_schedules[schedule_e]);

        printf("\n");

            

        total_schedules++;

    } } } } }

    // printf("total counts %d\n", total_schedules);

    return 0;

}

算法问题，长长见识

#include <stdio.h>
int move_zero(int buffer[],int i)
{
    buffer[i]=1;
    buffer[i+1]=0;
    if(i+3>6)
    {
        buffer[i+3-7]=1;
        buffer[i+3-7+1]=0;
    }
    else if(i+3==6)
        {   
            buffer[i+3]=1;
            buffer[0]=0;
        }

        else
        {
            buffer[i+3]=1;
            buffer[i+3+1]=0;
        }
    return 0;
}
void print_buffer(int (*buffer)[7])
{
    int i,j;
    for(i=0;i<5;i++)
    {
        for(j=0;j<7;j++)
            printf("%d\t",buffer[i][j]);
        printf("\n");
    }
}
int main()
{
    int buffer[5][7]={
                        {0,1,1,0,1,1,1},
                        {0,1,1,0,1,1,1},
                        {0,1,1,0,1,1,1},
                        {0,1,1,0,1,1,1},
                        {0,1,1,0,1,1,1},
                     };
    int i[5]={0,0,0,0,0};
    int j = 0,temp = 0;
    for(i[0]=0;i[0]<6;i[0]++)//a
    {
        move_zero(buffer[0],i[0]);
        if(buffer[0][2] != 1)
            continue;
        for(i[1]=0;i[1]<6;i[1]++)//b
        {
            move_zero(buffer[1],i[1]);
            if(buffer[1][6] != 0)
                continue;
            for(i[2]=0;i[2]<6;i[2]++)//c
            {
                move_zero(buffer[2],i[2]);
                temp = 0;
                for(j=0;j<7;j++)
                {
                    if(buffer[0][j]==1 && buffer[2][j]==1)
                    temp+=1;
                }
                if(temp<4)
                    continue;
                for(i[3]=0;i[3]<6;i[3]++)//d
                {
                    move_zero(buffer[3],i[3]);
                    if(buffer[3][6]!=0)
                    continue;
                    temp =0;
                    for(j=0;j<7;j++)
                    {
                        if(buffer[0][j]+buffer[1][j]+buffer[2][j]+buffer[3][j]<2)
                            break;
                    }
                    if(j<7)
                        continue;
                   
                    for(i[4]=0;i[4]<6;i[4]++)//e
                    {
                        move_zero(buffer[4],i[4]);
                        if(buffer[4][2] != 1)
                            continue;
                        if(buffer[4][6] !=0)
                            continue;
                        print_buffer(&buffer[0]);
                        printf("\n");

                    }
                    

                }

            }
        }
       
    }
    return 0;

}

哎，我想到的就是这样了

这题到底考啥的啊 半天都没弄明白 穷举？ ……

[ 本帖最后由 fanpengpeng 于 2013-4-26 17:25 编辑 ]

楼主的上一个贴子里不是已经有人回答了这个问题么。还想怎样？

苦思半天 还是只能穷举 楼主看看这个 是不是你想要的那种递归 不过这里的递归比5层for循环没有任何优势 除了少写点代码

#include <stdio.h>

char *A[7] = {    /*  规则1  */
    "0110111",
    "0111011",
    "1011011",
    "1011101",
    "1101101",
    "1101110",
    "1110110"
};
char *B[5];        /*  所有人员的安排矩阵 每位人员的安排方式从A中抽取  */ 

void solve(int i) 
{
    if (i < 5) {    /*  递归穷举  */
        for (int j=0; j<7; j++) {
            B[i] = A[j];
            solve(i+1);
        }
    } else {    /*  规则检查  */
        /*  Rule 4, 5  */ 
        if (B[1][6]!='0' || B[3][6] != '0' || B[4][6]!='0' || 
            B[0][2]!='1' || B[4][2]!='1') return;
        /*  Rule 2, 3, 6  */
        int m, n, f, r2=0, r3=0, r6=0; 
        for (m=0; m<7; m++) {
            for (r3=0, f=1, n=0; n<5; n++) {
                if (n<4 && B[n][m]=='1') ++r3;
                if (B[n][m]=='0') f=0;    
            }
            if (r3 < 2) return;
            if (f == 1) ++r2;
            if (B[0][m]=='1' && B[2][m]=='1') ++r6;                        
        }
        if (r2<3 || r6<4) return;
        /*  Print  */
        for (m=0; m<5; m++)
            printf("%s\n", B[m]);
        printf("\n");    
    }
}

int main()
{
    solve(0);
    return 0;
}

分要多多的给