include <iostream> #include <cmath> using namespace std; class CQueen { public: CQueen(); CQueen(int n); // 构造函数 void IniQueen(int n); // 初始化n后问题 void GetFirstAndSum(); // 求出所有解的总和及第一个解 private: int m_n; // 皇后数 long m_sum; // 总解数 int* m_FirstX; // 第一个解向量 bool m_bPlace(int k); // 当主生了x[0.x(k-1]时,判断x[K]能否放置 void m_BackTrack(int t); // 回溯方法 }; CQueen::CQueen(int n) { m_n = n; m_sum = 0; m_FirstX = new int[m_n]; } void CQueen::IniQueen(int n) { m_n = n; m_sum = 0; delete[] m_FirstX; m_FirstX = new int[m_n]; } bool CQueen::m_bPlace(int k) { for (int j = 0; j < k; j++) { if (abs(k - j) == abs(m_FirstX[j] - m_FirstX[k]) || m_FirstX[j] == m_FirstX[k]) { return false; } } return true; } void CQueen::m_BackTrack(int t) { if (t >= m_n) { m_sum++; return; } for (int i = 0; i < m_n; i++) { m_FirstX[t] = i; if (m_bPlace(t)) { m_BackTrack(t+1); } } } void CQueen::GetFirstAndSum() { cout << "n后数\t解数\t\t第一个解" << endl; for (int n = 4; n <= 14; n++) { IniQueen(n); m_BackTrack(0); cout << n << "\t" << m_sum << "\t\t("; for (int i = 0; i < n - 1; i++) { cout << m_FirstX[i] + 1 << ","; } cout << m_FirstX[n - 1] + 1 << ")" << endl; } } int main() { CQueen queen(4); queen.GetFirstAndSum(); return 0; }
时间: 2024-03-29 14:37:05 浏览: 12
这段代码实现了八皇后问题的求解,可以扩展到n皇后问题。这个问题是经典的回溯问题,目的是在一个n*n的棋盘上放置n个皇后,使得它们互不攻击,即在同一行、同一列或同一对角线上没有两个皇后。
在代码中,CQueen类表示n皇后问题的解。IniQueen函数用于初始化问题,m_bPlace函数用于判断在当前皇后放置位置时是否与之前的皇后发生冲突,m_BackTrack函数是回溯函数,用于递归地搜索所有可能的解,m_sum表示所有解的总数,m_FirstX表示第一个解的向量。
GetFirstAndSum函数用于计算所有解的总数和第一个解。在main函数中,首先创建一个4皇后的问题,然后调用GetFirstAndSum函数计算4到14皇后问题的解。在输出解时,用括号表示第一个解的向量。
需要注意的是,该算法只求出了解的总数和第一个解,如果需要所有解,需要对回溯函数进行修改。此外,该算法只适用于n比较小的情况,对于大规模的n皇后问题,需要使用更高效的算法。
相关问题
#include <iostream> #include<algorithm> #include<cmath> #include <queue> using namespace std;
#include <iostream>:这是C++标准库中的头文件,用于输入输出流操作,包括cin、cout等。
#include<algorithm>:这是C++标准库中的头文件,用于提供各种算法操作,如排序、查找等。
#include<cmath>:这是C++标准库中的头文件,用于提供数学函数操作,如绝对值、平方根等。
#include <queue>:这是C++标准库中的头文件,用于提供队列操作,包括入队、出队等。
using namespace std;:这是C++的命名空间声明,表示使用std命名空间,可以直接使用std中的函数和对象。
#include<iostream> #include<cstdio> using namespace std;是什么意思
#include<iostream> #include<cstdio> using namespace std; 是C++中的预处理指令,用于引入头文件和命名空间。
1. #include<iostream> 是引入iostream头文件,其中包含了输入输出流的定义,例如cout和cin等。
2. #include<cstdio> 是引入cstdio头文件,其中包含了C语言标准输入输出函数的定义,例如printf和scanf等。
3. using namespace std; 是使用std命名空间,std是C++标准库的命名空间,其中包含了很多常用的函数和类。
这些预处理指令的作用是为了在程序中能够使用输入输出流和标准库函数,使得程序更加方便和简洁。