d396: 00524 - Prime Ring Problem

出處：UVA524

檢測平台：https://zerojudge.tw/ShowProblem?problemid=d396

有一個環（ring）是由 n 個圈圈所組成的（在這裡 n 一定是個偶數），我們想要把 1 到 n 的自然數各放到一個圈圈中，使得相鄰 2 個圈圈中的數的和一定是質數。下圖為 n=6 的情形。

每組測試資料只包含一整數 n（0 < n <= 16）

看到上面的輸入範圍就決定暴力DFS解了，但為了幫忙加速一下，還是建立一個1~31(15+16)的質數表來加速運算。

程式碼如下：

如果有任何疑問歡迎留言或私訊討論。

prime = [0 , 0 , 1 , 1 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0
 , 1 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 
 0 , 0 , 1 , 0 , 1]

a = []
n = 0
index = 0
def dfs(d , d1 , count , ss):
  if prime[d+d1] == 0: return
  if count == n:
    if prime[1 + d1] == 1:
      print(ss)
    return

  global a
  for i in range(2 , n+1):
    if a[i] == 1: continue
    a[i] = 1
    dfs(d1 , i , count+1 , ss + str(i) + " ")
    a[i] = 0
  


try:
  while True:
    ans= ""
    a = []
    index += 1
    n = int(input())
    a = [0]*(n+1);
    ans = "1 "
    a[1] = 1
    print("Case " + str(index) + ":" )
    for i in range(2 , n+1 , 2):
      a[i] = 1
      #ans += str(i) + " "
      dfs(1 , i , 2 , ans + str(i) + " ")
      a[i] = 0
      
except EOFError:pass