分书和八皇后问题

2024-09-01 10:38

文章标签 问题皇后分书

本文主要是介绍分书和八皇后问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.分数问题：若干个人如何都拿到自己喜欢的书

#include<iostream>
#include<iomanip>
using namespace std;
int Num;  //方案数
int take[5];  //5本书分别给谁(用户编号)
bool assigned[5];  //5本书是否已分配
int like[5][5]={{0,0,1,1,0},{1,1,0,0,1},{0,1,1,0,1},{0,0,0,1,0},{0,1,0,0,1}};
void Try(int id)
{//递归终止条件：所有的读者都已分配到合适的书籍if(id==5){//方案数加1Num++;//输出方案细节cout<<"第"<<Num<<"个方案（按ABCDE次序）：";int i;for(i=0;i<5;i++)cout<<take[i]<<" ";cout<<endl;return;}//逐一为每本书找到合适的对着int book;for(book=0;book<=4;book++){//是否满足分书条件if((like[id][book]==1) && !assigned[book]){//记录当前这本书的分配情况take[id]=book;assigned[book]=true;//为下一位读者分配适合书籍Try(id+1);//将书退还(回溯),尝试另一种方案assigned[book]=false;}}
}int main()
{Num=0;  //分书方案数初始值int book;for(book=0;book<5;book++)assigned[book]=false;//从第0个人(A)开始分书Try(0);return 0;
}

运行结果：

2.八皇后问题：

#include<iostream>
#include<iomanip>
using namespace std;
const int Normalize=9;  //用来统一数组下标
int Num;  //方案数
int q[9];  //8个皇后所占用的行号
bool S[9];  //S[1]~S[8],当前行是否安全
bool L[17];  //L[2]~L[16],(i-j)对角线是否安全
bool R[17];  //R[2]~R[16],(i+j)对角线是否安全void Try(int col)
{//递归终止条件：所有列均已放上了皇后if(col==9){Num++;//输出方案细节cout<<"方案"<<Num<<"：";int i;for(i=1;i<=8;i++)cout<<q[i]<<" ";cout<<endl;return;}//依次尝试当前列的8行位置int row;for(row=1;row<=8;row++){//判断拟放置皇后的位置是否安全if(S[row] && R[col+row] && L[col-row+Normalize]){//记录位置信息(行号)q[col]=row;//修改三个方向的安全性标记S[row]=false;L[col-row+Normalize]=false;R[col+row]=false;//尝试放下一列Try(col+1);//回溯：回复三个方向原有安全性S[row]=true;L[col-row+Normalize]=true;R[col+row]=true;}}
}int main()
{//初始化Num=0;int i;for(i=0;i<9;i++)S[i]=true;  //各行都安全for(i=0;i<17;i++){L[i]=true;  //个对角线都安全R[i]=true;}Try(1);  //从第一列开始放皇后return 0;
}

执行结果：