素数环问题

逃离我推掉我的手 2021-11-04 23:04 285阅读 0赞

**问题链接**：[https://www.nowcoder.com/questionTerminal/4437f37768eb45fe9b79d88db47ff32a?orderByHotValue=1&mutiTagIds=656&page=1&onlyReference=false][https_www.nowcoder.com_questionTerminal_4437f37768eb45fe9b79d88db47ff32a_orderByHotValue_1_mutiTagIds_656_page_1_onlyReference_false]

本文参考了问题链接中答案

## 问题描述 ##

一个环由n个圈组成，将自然数1-n放入圈内，使得任意相邻圈的两个数之和均为素数。第一个圈的元素均为1。下图为n=6时的一个例子：  
![在这里插入图片描述][20190807194120429.png]

## 程序样例 ##

### 输入为一个整数n ###

*  6
 *  8

### 输出分别为 ###

*  1 4 3 2 5 6  
    1 6 5 2 3 4
 *  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

## 解题思路: 栈的回溯调用，深度优先遍历(deep-first search) ##

当n为奇数时素数环不存在

*  证明：n为奇数时必然有偶数个奇数，排列成环时必然有两个奇数相邻，两个相邻的奇数相加就是偶数，偶数肯定不是素数。所以当n为奇数时素数环不存在。

以n=4为例：

*  栈的变化如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTYzMjE0_size_16_color_FFFFFF_t_70]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTYzMjE0_size_16_color_FFFFFF_t_70 1]
 *  遍历的图如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTYzMjE0_size_16_color_FFFFFF_t_70 2]

## 算法实现 ##

程序只适用n比较小的情况，如果n比较大，栈的递归调用深度过深，会导致栈溢出。此时需要自己定义一个栈来实现，而不该使用函数的栈递归调用。

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    
    static unsigned int n;
    static unsigned int *visited, *result;
    
    
    // isprime function judge num whether is prime.
    // please refer to https://blog.csdn.net/qq_36963214/article/details/90490364
    unsigned int isprime(unsigned int num)
    { 
    	unsigned int i, half;
    
    	if (num <= 1)
    		return 0;
    	if (num == 2 || num == 3)
    		return 1;
    	else if (num % 6 != 1 && num % 6 != 5)
    		return 0;
    
    	half = (int)sqrt(num);
    	for (i = 5; i <= half; i += 6)
    	{ 
    		if (num % i == 0 || num % (i + 2) == 0)
    			return 0;
    	}
    	return 1;
    }
    
    
    void dfs(unsigned int current)
    { 
    	int i;
        if (current == n)
        { 
        	if (isprime(result[current-1] + 1))
            { 
                for (i = 0; i < n - 1 ; i++)
                { 
                    printf("%d ", result[i]);
                }
                printf("%d\n", result[i]);
            }
        }
    
        else
        { 
            for (i = 2; i <= n; i++)
            { 
    
                if (visited[i] == 0 && isprime(i + result[current - 1]))
                { 
                    //printf("%d\n", i);
                    result[current] = i;
                    visited[i] = 1;
                    dfs(current + 1);
                    visited[i] = 0;
                }
            }
        }
    }
    
    int main()
    { 
    	int i;
        result = visited = NULL;
        visited = (unsigned int *)malloc((n + 1) * sizeof(unsigned int));
        if (visited == NULL)
        { 
            printf("visited malloc error.\n");
            exit(1);
        }
        result = (unsigned int *)malloc((n + 1) * sizeof(unsigned int));
        if (result == NULL)
        { 
            printf("result malloc error.\n");
            exit(1);
        }
    
        while (scanf("%d", &n) != 0)
        { 
    
            memset(visited, 0, (n + 1) * sizeof(unsigned int));
            memset(result, 0, (n + 1) * sizeof(unsigned int));
    
            result[0] = 1;
    
            // 当n为奇数时素数环不存在
            if ((n & 1)== 0)
            { 
                dfs(1);
            }
        }
        free(visited);
        free(result);
        visited = result = NULL;
        return 0;
    }

[https_www.nowcoder.com_questionTerminal_4437f37768eb45fe9b79d88db47ff32a_orderByHotValue_1_mutiTagIds_656_page_1_onlyReference_false]: https://www.nowcoder.com/questionTerminal/4437f37768eb45fe9b79d88db47ff32a?orderByHotValue=1&mutiTagIds=656&page=1&onlyReference=false
[20190807194120429.png]: /images/20211104/d5f1e3a92b1b43fcb2c1df164d15625b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTYzMjE0_size_16_color_FFFFFF_t_70]: /images/20211104/3f9a08efe58d43dcb103e6fefee803be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTYzMjE0_size_16_color_FFFFFF_t_70 1]: /images/20211104/407a14f93d4e4f28883684a23f688fda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTYzMjE0_size_16_color_FFFFFF_t_70 2]: /images/20211104/3f9042f417194fc699be3be53414b870.png