ccshelen   发表于 2020-2-13 21:01:30 |栏目:





n皇后问题素数环困难的串问题

n*n棋盘放n个棋子,要求每行每列每条对角线都只有一个棋子。
import java.util.Scanner;
public class lanqiao1 {
static int res;
public static void main(String[] args) {                     
              Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); //n*n棋盘,n个皇后
int []arr = new int[n]; //下标为行,值为列
dfs(arr,n,0);
              System.out.println(res);
}
private static void dfs(int[] arr,int n ,int row) {
if(row == n){
                    res++;
return;
}
for(int col=0;col<n;col++){
boolean ok=true;
// 检验这个皇后是否和之前已经放置的皇后有冲突
for(int i=0;i<row;i++){
if(arr == col || arr+i == row + col|| col - row == arr-i){
                                ok = false;
break;
}
}
if(ok){
                       arr[row] = col;
dfs(arr,n,row+1);
                       arr[row] = 0; //(此行可有可无)恢复原状,这种解法这里是否恢复状态都行,为啥?
}
}
}
}
1234567891011121314151617181920212223242526272829303132333435

对于对角线,发现了一个规律即:



有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻两个数(包括首尾)的和都为素数,称为素数环。
样例输入
6
样例输出
1 4 3 2 5 6
1 6 5 2 3 4
import java.util.Scanner;
public class lanqiao1 {
public static void main(String[] args) {                     
              Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int []r = new int[n];  
              r[0] = 1;
dfs(r,n,1);
}
private static void dfs(int []r,int n,int cur) {
//cur为当前下标
if(cur == n && isP(r[0]+r[n-1])){
for(int i = 0;i < n;i++){
                                System.out.print(r);
                                System.out.print(" ");
}
                        System.out.println();
return;
}
for(int i=2;i<=n;i++){
if(check(r,i,cur)){//检查这个数和前一个数的和是否为素数&&这个数在数组中是否已出现
                                r[cur] = i;
dfs(r,n,cur+1);
                                r[cur] = 0; //回溯
}
}
}
private static boolean isP(int num) {
//判断num是否为素数
for(int k = 2;k  <= num/2;k++){
if(num % k ==0)
return false;
}
return true;
}
private static boolean check(int[] r, int i, int cur) {
for(int e:r){
if(e==i || !isP(r[cur-1] + i)) return false;
}
return true;
}
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546

如果一个字符串包含两个相邻的重复子串,则称它是“容易的串”,其他串成为“困难的串”。例如:BB,ABCDACABCAB,ABCDABCD都是容易的,而D、DC、ABDAB、CBABCBA都是困难的。
输入正整数n和L,输出由前L个字符(26个大写英文字母)组成的、字典序第n个小的困难的串。例如,当L=3时,前7个困难的串分别为:A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA。
import java.util.Scanner;
public class lanqiao1 {
static int count;
public static void main(String[] args) {                     
              Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int L = sc.nextInt();
dfs(L,n,"");
}
private static void dfs(int l, int n, String pertix) {
for(char i ='A';i< 'A'+l;i++){
if(isHard(pertix,i)){
                                String x = pertix+i;
                                System.out.println(x);
                                count++;
if(count == n)
                                        System.exit(0);
dfs(l,n,x);
}
}
}
//CBABCA i  看i与下标为5的字母是否相同;看A+i与下标为3 4的字母是否相同;
//看CA+i与下标为1 2 3的字母是否相同;
private static boolean isHard(String pertix, char i) {
int count=0;
for(int j=pertix.length()-1;j>-1;j-=2){
                    String s1 = pertix.substring(j,j+count+1);
                    String s2 = pertix.substring(j+count+1)+i;
if(s1.equals(s2)) return false;
                    count++;
}
return true;
}
}
123456789101112131415161718192021222324252627282930313233343536

n皇后问题中

回复 显示全部楼层 使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作者相关信息

更多资源

精品推荐

极品资源

原创模板

下载排行

热门标签

快速回复 返回顶部 返回列表