weixin_44138061
2018-12-17 07:39
采纳率: 25%
浏览 546

C++ 关于棋子的排列问题(小菜鸡求救大佬)

棋子排列问题
用给定数量的红、绿、蓝三种颜色棋子排成一个圆环,要求任意相邻的棋子不能同色。棋子总数不超过20,每种颜色至少有1个棋子。求满足上述要求的全部排列结果,输出排列总数和所有排列结果(不考虑循环相似的),每行显示一种排列结果(分别用字母R、G、B表示红、绿、蓝),并记录到文件result.txt中。

  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • bobhuang 2018-12-17 10:07
    已采纳
    /*
    棋子排列问题
    用给定数量的红、绿、蓝三种颜色棋子排成一个圆环,要求任意相邻的棋子不能同色。
    棋子总数不超过20,每种颜色至少有1个棋子。求满足上述要求的全部排列结果,
    输出排列总数和所有排列结果(不考虑循环相似的),每行显示一种排列结果(
    分别用字母R、G、B表示红、绿、蓝),并记录到文件result.txt中。
    */
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAX_COLOR 3
    #define MIN_N 3
    #define MAX_N 20
    
    // 颜色的字母符号
    static char *color_names = "RGB";
    
    // 颜色的顺序值
    enum {
        RED = 0,
        GREEN,
        BLUE,
    };
    
    /* ----------------------------------------------------------------------------
    * 算法思路:
    * 因为相邻棋子不能同色, 所以一个n个棋子的排列可以用一个(n-1)位的二进制数表示.
    * 假设RGB三色分别用0,1,2表示。第一个固定为某个颜色, 下一个颜色有2种可能
    * (当前颜色+1或+2), 分别用0和1表示. 则算法简化为遍历2 ^ (n-1), 判断是否满足3种
    * 颜色都有, 即可. 同时因为不需要考虑循环相似, 所以不用额外做变化和记录.
    */
    int main(void)
    {
        FILE *fd = NULL;
        int n; // 棋子个数
        unsigned long x; // 当前排列的二进制表示
        unsigned long end; // 当前排列的最后一个数字
        unsigned long y; // 用于当前排列按位输出
        unsigned long cur_color; // 当前位对应的颜色
        unsigned char used[MAX_COLOR]; // 标记某个颜色是否用过
        unsigned char all_used; // 计算是否所有颜色都用了
        char colors[MAX_N + 1]; // 当前排列的具体颜色值
        char colors_R[MAX_N + 1]; // 红色开始的排列
        char colors_G[MAX_N + 1]; // 绿色开始的排列
        char colors_B[MAX_N + 1]; // 蓝色开始的排列
        int i; // 循环变量
        int count = 0; // 总数
    
        fd = fopen("result.txt", "w");
        if (NULL == fd) {
            printf("can't open result.txt\n");
            return 0;
        }
    
        memset(colors, 0x00, (MAX_N + 1) * sizeof(char));
        memset(colors_R, 0x00, (MAX_N + 1) * sizeof(char));
        memset(colors_G, 0x00, (MAX_N + 1) * sizeof(char));
        memset(colors_B, 0x00, (MAX_N + 1) * sizeof(char));
    
        // 最少3个, 最多20个, 第一个颜色可以固定, 实际只要计算 n - 1 位的排列
        for (n = MIN_N - 1; n < MAX_N; n++) {
            end = (1ul << n) - 1;
            for (x = 0; x <= end; x++) {
                used[0] = used[1] = used[2] = 0; // 简单的赋值, 比循环更快
                y = x;
                cur_color = RED;
                used[cur_color] = 1;
                colors[0] = cur_color;
                for (i = 0; i < n; i++) {
                    cur_color = (cur_color + 1 + (y & 0x01ul)) % MAX_COLOR;
                    y >>= 1;
                    used[cur_color] = 1;
                    colors[i + 1] = cur_color;
                }
                all_used = used[0] & used[1] & used[2];
                if (all_used) { // 符合条件, 可以输出
                    count += 3;
                    for (i = 0; i <= n; i++) {
                        // 分别计算3种颜色开头的排列字符串
                        colors_R[i] = color_names[colors[i]];
                        colors_G[i] = color_names[(colors[i] + 1) % MAX_COLOR];
                        colors_B[i] = color_names[(colors[i] + 2) % MAX_COLOR];
                    }
                    fprintf(fd, "%s\n%s\n%s\n", colors_R, colors_G, colors_B);
                }
            }
        }
    
        printf("total: %d\n", count);
    
        fclose(fd);
    
        return 0;
    }
    
    
    
    已采纳该答案
    打赏 评论

相关推荐 更多相似问题