西安响应式网站建设哪家强,访问网站速度很慢,中国互联网站建设中心,高端企业网站建设规定一、n皇后问题
1、概述 n皇后要求在一个nn的棋盘上放置n个皇后#xff0c;使得他们彼此不受攻击#xff0c;皇后可以攻击同一行、同一列、同一斜线上的敌人#xff0c;所以n皇后问题要求寻找在棋盘上放置这n个皇后的方案#xff0c;使得任意两个皇后都不在同一行、同一列或…一、n皇后问题
1、概述 n皇后要求在一个n×n的棋盘上放置n个皇后使得他们彼此不受攻击皇后可以攻击同一行、同一列、同一斜线上的敌人所以n皇后问题要求寻找在棋盘上放置这n个皇后的方案使得任意两个皇后都不在同一行、同一列或同一斜线上。 2、子集树解法
1判断是否遍历过叶子结点tn若没有则遍历子集树判断placet即该层从1到n是否存在有成立的情况。
2place剪枝函数遍历1到t如果存在一个点满足同一列同一对角线那么舍弃这个叶节点反之保留叶节点。由于每一层保存的点存放在x数组该数组显性约束了不满足同一行的条件数组中的索引1就是行号数组值为列号。
3若已经满足tn即已经遍历过叶子结点则输出该可行解。 3、排列树解法
1判断是否遍历过叶子结点tn若没有则遍历排列树对后续层进行全排列判断placet即该层从1到n是否存在有成立的情况。
2place剪枝函数此时由于对后续层全排列第一层的列数不能存在于后续层不需要添加同一列的检查其他与子集树一致。
3若已经满足tn即已经遍历过叶子结点则输出该可行解。 4、代码
//n皇后问题
import java.util.Scanner;
public class Queen {static int x[]new int[100];static int n;static int sum0;public static void main(String [] args){nnew Scanner(System.in).nextInt();//排列树提前添加x数组值保证能够进行排列for(int i1;in;i)x[i]i;Backstack2(1);} //子集树算法public static void Backstack(int t){if(tn){sum;for(int i1;in;i){for(int j1;jn;j){if(x[i]j)System.out.print(Q );else System.out.print(. );}System.out.println();}System.out.println();}else{for(int i1;in;i){x[t]i;if(place(t))Backstack(t1);}}}public static boolean place(int t){for(int i1;it;i)if((Math.abs(x[i]-x[t])Math.abs(i-t))||x[i]x[t])return false;return true;}//排列树算法public static void Backstack2(int t){if(tn){sum;for(int i1;in;i){for(int j1;jn;j){if(x[i]j)System.out.print(Q );else System.out.print(. );}System.out.println();}System.out.println();}else{for(int it;in;i){swap(i,t);if(place2(t))Backstack2(t1);swap(i,t);}}}public static void swap(int i,int t){int tmpx[i];x[i]x[t];x[t]tmp;}public static boolean place2(int t){for(int i1;it;i){if(Math.abs(x[i]-x[t])Math.abs(i-t))return false;}return true;}
}5、结果 通过Q和 . 区分皇后的位置。 二、含重复元素的全排列
1、概述 给定一个可包含重复数字的序列按任意顺序返回所有不重复的全排列如输入【1,1,2】输出【1,1,2】【1,2,1】【2,1,1】。
2、算法 排列树问题在原有问题上添加条件x[t]x[i]t!i当前交换的两个数若相同且不是同一个数则剪枝注意循环中使用continue表示下面的交换和扩展的操作不再进行但循环继续。 3、代码
//含重复元素的全排列
import java.util.Scanner;
public class repeatperm {public static void main(String []args){String mnew Scanner(System.in).nextLine();String []numbersm.split(\\s);int x[]new int[numbers.length1];for(int i0;inumbers.length;i)x[i1]Integer.parseInt(numbers[i]);perm(x,1);} //全排列public static void perm(int[] x,int t){int nx.length-1;if(tn){for(int i1;in1;i)System.out.print(x[i] );System.out.println();}else{for(int it;in1;i){//约束条件保证不再重复if(x[t]x[i]t!i)continue;swap(t,i,x);perm(x,t1);swap(t,i,x);}}}public static void swap(int t,int i,int []x){int tmpx[i];x[i]x[t];x[t]tmp;}
}三、 组合
1、概述 输入n和k从1~n中任意不放回抽取k个值的所有情况输入n4k2输出【1,2】【1,3】【1,4】【2,3】【2,4】【3,4】。
2、算法 子集树在叶子结点未遍历结束前每一层的值都为上一层的节点值到n之间所有的遍历。 3、代码
//组合问题
import java.util.Scanner;
public class combination {public static void main(String[] args){int nnew Scanner(System.in).nextInt(); //n4int knew Scanner(System.in).nextInt(); //k2int x[]new int [k1];combine(n,k,1,x);}public static void combine(int n,int k,int t,int x[]){if(tk){for(int i1;ik;i)System.out.print(x[i] );System.out.println();}else{for(int ix[t-1]1;in;i){x[t]i;combine(n,k,t1,x);}}}
}
四、组合总和
1、概述 输入n和k输出1-9的任取k个数的组合中组合加和等于n的所有可能情况。
2、算法 子集树算法与上一道题相同只需要在输出的时候添加限制总和等于n的输出。另外可以进行改进对于问题规模过大的情况如果未完成的组合组合总和已经大于等于n则进行剪枝。
3、代码
//组合总和
import java.util.Scanner;
public class combinationsum {public static void main(String[] args){int nnew Scanner(System.in).nextInt(); //n7,判断条件和int knew Scanner(System.in).nextInt(); //k3int x[]new int [k1];combine(n,k,1,x);}public static void combine(int n,int k,int t,int x[]){if(tk){int sum0;for(int j:x)sumj;if(sumn){for(int i1;ik;i)System.out.print(x[i] );System.out.println();}}else{for(int ix[t-1]1;i9;i){x[t]i;combine(n,k,t1,x);}}}
}
