机试小课堂丨搜索周·例题讲解③《Prime Path》

【声明：本文为原创文章,未经同意,严禁转载和抄袭,违者将追究其法律责任】

苏世机试小课堂，考研机试不再慌！

公主号：苏世学社考研  苏世计算机考研

Prime Ring Problem

Time Limit:4000/2000MS（Java/Others）

Memory Limit:65535/32768K（Java/Others）

Description

A ring iscompose of n circles as shown in diagram. Put natural number 1, 2, ..., n intoeach circle separately, and the sum of numbers in two adjacent circles shouldbe a prime.

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

Input

n (0 < n< 20).

Output

The outputformat is shown as sample below. Each row represents a series of circle numbersin the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographicalorder.

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

答案

①读题:

给出一个n，对1到n这n个数排序，构造一个环，使得相邻两数之和为素数，这个环叫做素数环。

②想出思路：

用深度优先搜索（DFS）遍历每一种情况，依次输出即可。

③动手编程：

④测试样例：

⑤提交代码：

进入下面的链接提交代码：

http://acm.hdu.edu.cn/showproblem.php?pid=1016

⑥返回评测结果：

至此，这道题我们就已经完成了。

本题总结

经典题型素数环，从1出发，一层一层推下去判断是否符合条件，然后回溯记录路径即可。

未完待续

苏世学社旗下品牌，专注于计算机考研

计算机考研一手资讯，原创高质量干货

深度的学习分享丨咨询前辈丨个性化指导