本文共 1536 字，大约阅读时间需要 5 分钟。

DFS算法求解素数环问题

问题描述

输入正整数n，把整数1,2,3,…,n组成一个环，使得相邻两个整数之和均为素数，输出从整数1开始逆时针排列。

问题分析

该问题可以有多种求解算法，本次使用DFS算法求解。

算法设计

package com.bean.algorithmbasic;import java.util.Arrays;import java.util.Scanner;public class PrimeCircleDemo {		/*	 * 输入正整数n，把整数1,2,3,...,n组成一个环，	 * 使得相邻两个整数之和均为素数，输出从整数1开始逆时针排列。	 * 同一个环应该只输出一次。n<=16.	 * */	public static void dfsSearch(int[] res, int[] visited, int n, int cursor) {		if (cursor == n && isPrime(res[0] + res[n - 1])) {			StringBuffer str = new StringBuffer();			for (int i : res) {				str.append(i + " ");			}			System.out.println(str.substring(0, str.length() - 1));			return;		}		for (int i = 2; i <= n; i++) {			if (visited[i - 1] == 0) {				if (cursor > 0) {					if (!isPrime(i + res[cursor - 1]))						continue;				}				res[cursor] = i;				//设置标记				visited[i - 1] = 1;				//搜索下一个位置				dfsSearch(res, visited, n, cursor + 1);				//清除标记				visited[i - 1] = 0;			}		}	}	/*	 * 判断是否为素数	 * */	public static boolean isPrime(int n) {		//如果n==1直接返回，因为1不是素数		if (n == 1)			return false;		//设置标记		boolean flag = true;		//从i=2开始，直到i的平方根为止		for (int i = 2; i <= Math.sqrt(n); i++) {			if (n % i == 0) {				flag = false;				break;			}		}		return flag;	}	public static void main(String[] args) {		Scanner scanner = new Scanner(System.in);		while (scanner.hasNext()) {			int n = scanner.nextInt();			int[] res = new int[n];			int[] visited = new int[n];			res[0] = 1;			Arrays.fill(visited, 0);			//调用搜索算法			dfsSearch(res, visited, n, 1);		}		scanner.close();	}}

输入：6

运行结果：

1 4 3 2 5 6

（完）

转载地址：http://rwtdi.baihongyu.com/