c语言分治算法求解残缺棋盘问题,自己定义棋盘大小的代码
时间: 2024-04-29 12:25:14 浏览: 95
分治算法 残缺棋盘解法
很好,以下是 C 语言分治算法求解残缺棋盘问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define N 8 // 棋盘大小,可以自行定义
int board[N][N]; // 棋盘
int tile = 0; // 棋子编号
// 残缺棋盘问题求解函数
void chessboard(int tr, int tc, int dr, int dc, int size)
{
if (size == 1) return; // 棋盘大小为 1,不需要分割
int t = ++tile; // 棋子编号自增
int s = size / 2; // 分割棋盘的大小
int i, j;
// 分割棋盘,分别递归求解四个子问题
if (dr < tr + s && dc < tc + s) // 覆盖左上角子棋盘
chessboard(tr, tc, dr, dc, s);
else // 不在左上角子棋盘中,用 t 号棋子覆盖右下角
{
board[tr + s - 1][tc + s - 1] = t;
chessboard(tr, tc, tr + s - 1, tc + s - 1, s);
}
if (dr < tr + s && dc >= tc + s) // 覆盖右上角子棋盘
chessboard(tr, tc + s, dr, dc, s);
else // 不在右上角子棋盘中,用 t 号棋子覆盖左下角
{
board[tr + s - 1][tc + s] = t;
chessboard(tr, tc + s, tr + s - 1, tc + s, s);
}
if (dr >= tr + s && dc < tc + s) // 覆盖左下角子棋盘
chessboard(tr + s, tc, dr, dc, s);
else // 不在左下角子棋盘中,用 t 号棋子覆盖右上角
{
board[tr + s][tc + s - 1] = t;
chessboard(tr + s, tc, tr + s, tc + s - 1, s);
}
if (dr >= tr + s && dc >= tc + s) // 覆盖右下角子棋盘
chessboard(tr + s, tc + s, dr, dc, s);
else // 不在右下角子棋盘中,用 t 号棋子覆盖左上角
{
board[tr + s][tc + s] = t;
chessboard(tr + s, tc + s, tr + s, tc + s, s);
}
}
int main()
{
int i, j, dr, dc;
// 初始化棋盘
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
board[i][j] = 0;
// 输入残缺棋盘坐标
printf("Enter the coordinates of the missing square (row column): ");
scanf("%d%d", &dr, &dc);
// 求解残缺棋盘问题
chessboard(0, 0, dr-1, dc-1, N);
// 输出棋盘
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
printf("%2d ", board[i][j]);
printf("\n");
}
return 0;
}
```
如果您还有其它问题,我很乐意为您解答。现在给您讲一个笑话:为什么程序员总是喜欢在晚上工作?因为他们觉得这样可以“debug”他们的生活。
阅读全文