初试DFS之HDU1016

DFS和BFS是基础算法，可怜我现在才开始接触，不争气......

DFS入门题之HDU1016

提交7次才AC，前期四次超时，后期两次格式错误。

先贴上AC代码：

#include<iostream>
using namespace std;
int a[25],book[25],n,Case=1;
bool IsPrime[40]= {false,true,true,true,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false};
void dfs(int step)
{
    if(step==n+1&&IsPrime[a[1]+a[n]])
    {
        for(int i=1; i<n; i++)
            cout<<a[i]<<' ';
        cout<<a[n]<<endl;
        return ;
    }
    for(int i=2; i<=n; i++)
        if(book[i]==0&&IsPrime[i+a[step-1]])
        {
            a[step]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    return ;
}
int main()
{
    a[1]=1;
    while(cin>>n)
    {
        cout<<"Case "<<Case++<<':'<<endl;
        dfs(2);
        cout<<endl;
    }
    return 0;
}

强迫症版本：

#include<iostream>
using namespace std;
int a[25],book[25],n,Case=1;
bool IsPrime[40]= {false,true,true,true,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,true,false,false,false,true,false,false,false,false,false,true,false,true,false,false,false,false,false,true,false,false};
int dfs(int step)
{
    if(step==n+1&&IsPrime[a[1]+a[n]])
    {
        for(int i=1; i<n; i++)
            cout<<a[i]<<' ';
        cout<<a[n]<<endl;
    }
    for(int i=2; i<=n; i++)
        if(book[i]==0&&IsPrime[i+a[step-1]])
        {
            a[step]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    return 1;
}
int main()
{
    a[1]=1;
    while(cin>>n&&cout<<"Case "<<Case++<<':'<<endl&&dfs(2))
        cout<<endl;
    return 0;
}

题目很简单，意思也很容易理解，写出几个要注意的地方，望以后能对看到这篇帖子的入门小伙伴提供帮助。
①此题判断两数之和是否为质数，不可直接写函数一一判断，否则会超时。
注意题目说明n最大为20，那么两数相加之和最多也才只有38种情况，完全可以将所有情况预先判断好，存在数组IsPrime[]。
②注意输入输出，输出每种结果最后一个数后不可加空格，否则会提示Wrong Answer。