5-3 【背包问题】设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w[1],w[2],...,w[n]。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解；否则无解。
思路：按照题中所给的背包问题递归定义，可以理解为从w[n]开始检查，直到n和s达到0,检查完毕。
5-4 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第一行，第2行。...，第8行上布放棋子。在每一行中有8个位置可选择，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。
思路：抄参考答案；书里的方法已经很经典了。
col[i]:标志第i列是否放置了皇后，是1，下同.
md[k]:标志第k条主对角线是否安置了皇后。k=7+i-j-1
sd[k]:标志第k条次对角线是否放置了皇后，k=i+j
q[i]:记录第i行皇后在第几列。
执行的时候用函数Queen(1) 从第一行开始.
思路：按照题中所给的背包问题递归定义，可以理解为从w[n]开始检查，直到n和s达到0,检查完毕。
Boolean bag(int s,int n){
if(s< 0||s >0&&n< 1) return False;
if(s==0) return Ture;
if(bag(s-w[n],n-1)==True) {cout<< w[n]<< ',';return Ture}
return bag(s,n-1);
}
5-4 【八皇后问题】设在初始状态下在国际象棋棋盘上没有任何棋子(皇后)。然后顺序在第一行，第2行。...，第8行上布放棋子。在每一行中有8个位置可选择，但在任一时刻，棋盘的合法布局都必须满足3个限制条件，即任何两个棋子不得放在棋盘上的同一行、或者同一列、或者同一斜线上。试编写一个递归算法，求解并输出此问题的所有合法布局。
思路：抄参考答案；书里的方法已经很经典了。
col[i]:标志第i列是否放置了皇后，是1，下同.
md[k]:标志第k条主对角线是否安置了皇后。k=7+i-j-1
sd[k]:标志第k条次对角线是否放置了皇后，k=i+j
q[i]:记录第i行皇后在第几列。
void Queen(int i){
for(int j=0;j< 8;j++){
if(col[j]+md[8+i-j-1]+sd[i+j]==0){//没有被攻击
col[j]=md[8+i-j-1]=sd[i+j]=1; //修改攻击范围
q[i]=1; //安置皇后
if(i==8){ //如果已经是第八个皇后了
for(j=0;j< 8;j++) //这个j不影响外层的j么？
cout<< q[j]<< ','<< endl;
}
else Queen(i+1); //安置下一行
col[j]=md[8+i-j-1]=sd[i+j]=0; //撤销，尝试其他位置
q[i]=0;
}
}
}
执行的时候用函数Queen(1) 从第一行开始.
Comments (0)