乐趣区

关于数据结构:递归与递推N皇后问题-素数环

N 皇后问题

在 N * N 的方格棋盘搁置了 N 个皇后,使得它们不互相攻打(即任意 2 个皇后不容许处在同一排,同一列,也不容许处在与棋盘边框成 45 角的斜线上。
你的工作是,对于给定的 N,求出有多少种非法的搁置办法。

Input
共有若干行,每行一个正整数 N≤10,示意棋盘和皇后的数量;如果 N =0,示意完结。
Output
共有若干行,每行一个正整数,示意对应输出行的皇后的不同搁置数量。
Sample Input
1
8
5
0
Sample Output
1
92
10

这道题我老是 Time Limit, 有空还要优化一下,有大佬请帮我看下

//// 求 N * N 的格子摆放皇后的摆法(求有几种摆法而不是能够放多少个皇后)(递归)//#include<iostream>
//#include<algorithm>
//#include<string>
//#include<string.h>
//#include<cstdio>
//#include<queue>
//#include<stack> 
//#include<set> 
//using namespace std;
//int n,cnt;
//int vis[3][50];//vis[3]第一个中括号来辨别不同拜访类型三种类型,0(vis[0][])示意判断 同一列 的格子是否被拜访过
////1(vis[1][])示意判断 右斜对角 的格子是否被拜访过,2(vis[2][])示意判断 左斜对角 的格子是否被拜访过
////#include<bits/stdc++.h>// 万能头文件
//void dfs(int row){// 把 queen 所在的行传入 dfs 
//    if(row == n + 1){// 递归进口条件、边界(如果超过第 n 行了) 
//        cnt++;// 递归终止回溯一次,记录一次个数 
//        return ; 
//    }
//    for(int i = 1; i <= n; i++){//        if(vis[0][i] == 0 && vis[1][n + row - i] == 0 && vis[2][i + row] == 0){//            vis[0][i] = vis[1][n + row - i] = vis[2][i + row] = 1;
//            dfs(row + 1);
//            vis[0][i] = vis[1][n + row - i] = vis[2][i + row] = 0;// 在深搜遍历的时候每一个格子的同行同列、左右对角都被拜访标记了
//            // 然而回溯的时候只是找到了一个适合的格子,(除该以后格子外)其余格子要从新复原为未拜访 
//        }
//    }
//}
//int main(){//    memset(vis,0,sizeof(vis));
//    while(cin >> n,n != 0){
////    int cnt = 0;// 记录皇后搁置的数量, 应定义为全局变量  
////    int n;// 因为深搜外面也用到该变量,应定义为全局变量
//        cnt = 0; 
//        dfs(1); 
//        cout << cnt << endl;
//    }
//    return 0;
//}
// 

另一种办法,引入 check 函数,但实质还是递归

//// 求 N * N 的格子摆放皇后的摆法(求有几种摆法而不是能够放多少个皇后)(递归)//#include<iostream>
//#include<algorithm>
//#include<string>
//#include<string.h>
//#include<cstdio>
//#include<queue>
//#include<stack> 
//#include<set> 
//using namespace std;
//int n,cnt;
//int a[10];//a[i]示意第 i 行上的 queen 放于 a[i]列上,如 a[3] = 7 示意第 3 行第 7 列的格子有 queen 
////#include<bits/stdc++.h>// 万能头文件 
//// 字符翻转 
//bool check(int x, int y){// 传入行值和列值(相当于 a[i]), 看是否和 queen 所在的值绝对应或同行同列斜对角 
//    for(int i = 1; i <= x; i++){// 只用看在某行格子放 queen 之后,其前 x 行所对应的格子满足不满足条件, 一个一个格子枚举比照 
//        if(a[i] == y){//check 同列是否满足,应为是按行放,每行只放一个,同行无需验证 
//            return false;// 判断 a[i]的值是否等于 1,2,3,4,5,6 等 dfs 外面 for(的 i 值),排除同列的
//            // 不满足这个 if 及上面两个 if 就算找到了,完结 check 进行赋值操作 a[row] = i 
//        }
//        if(i + a[i] == x + y){//check / 对角线是否满足 
//            return false;
//        }
//        if(i - a[i] == x - y){//check \ 对角线是否满足 
//            return false;
//        }    
//    }
//    return true;// 留神要放在 for 循环里面,for 全副执行之后没问题再返回 true. 都没有问题,返回 queen 能够放在这个格子 
//} 
//void dfs(int row){// 把 queen 所在的行传入 dfs 
//    if(row == n + 1){// 递归进口条件、边界(如果超过第 n 行了) 
//        cnt++;// 递归终止回溯一次,记录一次个数 
//        return ; 
//    }
//    for(int i = 1; i <= n; i++){//        if(check(row,i)){//check 一下第 row 行的皇后能不能放在第 row 行第 i 列上
//            a[row] = i; // 能够放就给第 row 行的第 i 个 (列) 格子放上 
//            dfs(row + 1);
//            a[row] = 0;// 进行完每次回溯把相应的第 row 行还原置零,从新开始,即没次 dfs 完后 row 行的皇后地位回到第一列开始往后找 
//        }      
//    }
//}
//int main(){//    while(cin >> n,n != 0){
////    int cnt = 0;// 记录皇后搁置的数量, 应定义为全局变量  
////    int n;// 因为深搜外面也用到该变量,应定义为全局变量
//        cnt = 0; 
//        dfs(1); 
//        cout << cnt << endl;
//    }
//    return 0;
//}
// 

Prime Ring Problem

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, …, n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.
Sample Input
6
8
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<cstdio>
#include<queue>
#include<stack> 
#include<set> 
using namespace std;
/*
素数环指的是将从 1 到 n 这 n 个整数围成一个圆环,若其中任意 2 个相邻的数字相加,后果均为素数
*/ 
int n,a[30],vis[30];// n 是数字的个数,a[i]是需遍历的数组,vis[]是标记数组是否被拜访过 
bool Prime(int yy)// 判断素数
{for(int i=2; i<=sqrt(yy); i++)
    {if(yy%i==0)
        {return false;}
    }
    return true;
}
void dfs(int t){// 此处的 t 只是传参,跟 main 函数外面的 t 没有关系 
    if(t == n && Prime(a[t - 1] + a[0])){// t 是从 0 开始,当 t = n 时阐明 a[0,...t - 1]都填入了合规的数 
        for(int i = 0; i < t - 1; i++){//num 从 0 开始 
            printf("%d",a[i]);
        }
        printf("%d\n",a[t - 1]);//a[num - 1]就是传入的 num 下标对应的值 
    }else{// 尝试能够填入 a[i]的每一种可能性(穷举) 
        for(int i = 2; i <= n; i++){// i 代表所有的可能性 
            if(vis[i] == 0 && Prime(i + a[t - 1])){// i 没有应用过,还没连贯在环上并且 i 和他前一位的和是素数 
                // 此处 i = 2 是因为,dfs(1)从 1 开始并且 1 = a[1-1], 所以从 2 开始枚举(看 2 与 1 之和是否素数以及)
                vis[i] = 1;// 用过的数标记 1
                a[t] = i; // 满足条件给所求数组的第一个地位 a[1]赋值
                dfs(t + 1);// 在 a[1] = i 根底上 对 i 之后的每个数持续递归判断
                vis[i] = 0;// 进行完每次通过 n 此 dfs 后, 该回溯的时候把相应的 i 还原置零,不便下一个传入的 t 持续枚举 
            }
        }
    } 
} 
int main(){
    int t = 1;// 定义一个用来记录 case 后序号的变动 
    a[0] = 1;
    while(cin >> n){memset(vis,0,sizeof(vis));// 标记数组 vis 初始化为 0
        printf("Case %d:\n",t++);// 输入一下头部格局,case 前面的数字自增 
        dfs(1);// 传入 1 开始进行深搜 
        printf("\n");
    }
}

退出移动版