【聲明：本文為原創(chuàng)文章,未經(jīng)同意,嚴禁轉(zhuǎn)載和抄襲,違者將追究其法律責任】

蘇世機試小課堂，考研機試不再慌！

公主號：蘇世學社考研? 蘇世計算機考研

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個數(shù)排序，構(gòu)造一個環(huán)，使得相鄰兩數(shù)之和為素數(shù)，這個環(huán)叫做素數(shù)環(huán)。

②想出思路：

用深度優(yōu)先搜索（DFS）遍歷每一種情況，依次輸出即可。

③動手編程：

④測試樣例：

⑤提交代碼：

進入下面的鏈接提交代碼：

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

⑥返回評測結(jié)果：

至此，這道題我們就已經(jīng)完成了。

本題總結(jié)

經(jīng)典題型素數(shù)環(huán)，從1出發(fā)，一層一層推下去判斷是否符合條件，然后回溯記錄路徑即可。

未完待續(xù)

蘇世學社旗下品牌，專注于計算機考研

計算機考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學習分享丨咨詢前輩丨個性化指導