棋子排列问题
用给定数量的红、绿、蓝三种颜色棋子排成一个圆环,要求任意相邻的棋子不能同色。棋子总数不超过20,每种颜色至少有1个棋子。求满足上述要求的全部排列结果,输出排列总数和所有排列结果(不考虑循环相似的),每行显示一种排列结果(分别用字母R、G、B表示红、绿、蓝),并记录到文件result.txt中。
C++ 关于棋子的排列问题(小菜鸡求救大佬)
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
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; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
- ¥15 活动选择题。最多可以参加几个项目?
- ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
- ¥15 vs2019中数据导出问题
- ¥20 云服务Linux系统TCP-MSS值修改?
- ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
- ¥20 怎么在stm32门禁成品上增加查询记录功能
- ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
- ¥50 NT4.0系统 STOP:0X0000007B
- ¥15 想问一下stata17中这段代码哪里有问题呀