Prime is problem - 素数环问题

题目描述：

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.

输入：: n (1 < n < 17).

输出：: The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.

样例输入：

6

8

样例输出：

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

为了解决该问题，我们可以采用回溯法枚举每一个值。当第一个数位为1确定时，我们尝试放入第二个数，使其和1的和为素数，放入后再尝试放入第三个数，使其与第二个数的和为素数，直到所有的数全部被放入环中，且最后一个数与1的和也是素数，那么这个方案即为答案，输出；若在尝试放数的过程中， 发现当前位置无论放置任何之前未被使用的数均不可能满足条件，那么我们回溯 改变其上一个数，直到产生我们所需要的答案，或者确实不再存在更多的解。

#include "stdafx.h"

#include <stdio.h>

using namespace std;

int prime[] = { , , , , , , , , , , ,  };

int number[];

bool hash[];

int n;

bool isPrime(int num)

{

    for (int i = ; i < ;i++)

        if (num == prime[i])

            return true;

    return false;

}

void printArray()

{

    if (isPrime(number[n] + number[]) == false)

        return;

    for (int i = ; i <= n; i++)

    {

        if (i != )

            printf(" ");

        printf("%d", number[i]);

    }

    printf("\n");

}

void DFS(int num)

{

    if (num >  && isPrime(number[num] + number[num - ]) == false)

        return;

    if (num == n)

    {

        printArray();

        return;

    }

    for (int i = ; i <= n; i++)

    {

        if (hash[i] == false)

        {

            hash[i] = true;

            number[num + ] = i;

            DFS(num + );

            hash[i] = false;

        }

    }

}

int main()

{

    int cas = ;

    while (scanf("%d", &n) != EOF)

    {

        cas++;

        for (int i = ; i < ; i++)

            hash[i] = false;

        number[] = ;

        printf("Case %d:\n", cas);

        hash[] = true;

        DFS();

        printf("\n");

    }

    return ;

}

巴特西

Prime is problem - 素数环问题

最新文章

热门文章