再帰列挙配列@再帰遡及

再帰列挙配列@再帰遡及

* UVA - 524 Prime Ring Problem*

#include 
#include
#include
#include
#include
#include
#include
#include
#include 
using namespace std;

set<int> q;
int flag[20];
int a[20];
int n;
void dfs(int v)
{
    if(v == n && q.count(a[1]+a[n]))
    {
        for(int i = 1; i < n; i++)
            cout << a[i] << " ";
            cout << a[n] << endl;
    }
    else
    {
        for(int i=2; i<=n; i++)
        {
            if(!flag[i]&&q.count(i+a[v]))  ///  i    ，            
            {
                a[v+1]=i;
                flag[i]=1;              ///  
                dfs(v+1);
                flag[i]=0;              ///    
            }
        }
    }

}
int main()
{
    freopen("in.txt", "r", stdin);
    for(int i = 2; i <= 32; i++)
    {
        int j;
        for(j = i-1; j>=1; j--)
        {
            if(i%j == 0) break;
        }
        if(j == 1) q.insert(i);

    }
    int cas = 0;
    int f = 0;
    while(cin >> n)
    {
        memset(flag, 0, sizeof(flag));
        a[1] = 1;
        if(f) cout << endl;
        cout<<"Case "<":"<1;
        dfs(1);

    }

    return 0;
}

1~nの配列を生成する

#include 
#include
#include
#include
#include
using namespace std;

int A[1000];
void print_permutation(int n, int *A, int cur)
{
    if(cur == n)
    {
        for(int i = 0; i < n; i++)
        {
            printf("%d ",A[i]);
        }
        printf("
");
    }
    else
        for(int i = 1; i <= n; i++)
    {
        int ok = 1;
        for(int j = 0; j < cur; j++)
            if(A[j] == i) ok = 0; ///  i   A[0]~A[cur-1]    ，
                                  ///     
        if(ok)
        {
            A[cur] = i;
            print_permutation(n, A, cur+1);
        }
    }
}
int main()
{
    //freopen("in.txt", "r", stdin);
    print_permutation(4, A, 0);
    return 0;
}