HDU 1016 素数环（dfs + 回溯）

梦里梦外; 2023-06-04 13:57 21阅读 0赞

### 嗯... ###

## ##

### 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1016 ###

## 一道很典型的dfs+回溯： ##

### 根据题意首先进行初始化，即第一个位置为1，然后进行dfs，枚举2~n之间的每一个数，如果这个数没被使用并且它和环中上一个数形成素数环，那么就把它加入环中，打上标记，然后继续dfs，最后回溯。当环上的个数正好等于n并且第一个数和最后一个数也能组成素数，则输出，输出时注意格式，很严格！ ###

# #

## dfs这里还有一个剪枝： ##

### 只有n为偶数时才可能形成素数环！因为当n为奇数时，在1~n中奇数的个数比偶数多一，所以一定会形成两个奇数相邻，则构不成素数.... ###

## AC代码： ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<cstring>
     3 #include<iostream>
     4 
     5 using namespace std;
     6 
     7 int n, ring[25], vis[25];
     8 
     9 inline bool is_prime(int x){
    10     for(int i = 2; i * i <= x; i++){
    11         if(x % i == 0) return 0;
    12     }
    13     return 1;
    14 }
    15 
    16 inline void dfs(int x){
    17     if(x == n && is_prime(ring[x] + ring[1])){
    18         for(int i = 1; i < n; i++)
    19             printf("%d ", ring[i]);//输出格式要严格 
    20         printf("%d\n", ring[n]);
    21         return;
    22     }
    23     for(int i = 2; i <= n; i++){
    24         if(!vis[i] && is_prime(ring[x] + i)){
    25             vis[i] = 1;
    26             ring[x + 1] = i;
    27             dfs(x + 1);
    28             vis[i] = 0;
    29         }
    30     }
    31 }
    32 
    33 int main(){
    34     int k = 1;
    35     while(~scanf("%d", &n)){
    36         memset(ring, 0, sizeof(ring));
    37         memset(vis, 0, sizeof(vis));
    38         ring[1] = 1;
    39         printf("Case %d:\n", k);
    40         k++;
    41         if(n % 2 == 0 && n > 0) dfs(1);
    42         printf("\n");
    43     }
    44     return 0;
    45 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11409638.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/8bea8484164c48339e2c2d4c67b93c24.png