递归问题

全排序

// 给定一个数组，打印出这个数组所有的组合
void DSF(int num[],int n,vector<int> &v,bool key[])
{
    if(v.size()>=n){
        for_each(v.begin(),v.end(),[](int n){
            printf("%d",n);
        });
        printf(" ");
        return ;
    }
    for(int i=0;i<n;i++){
        if(!key[i])
            continue;
        v.push_back(num[i]);
        key[i]=false;
        DSF(num,n,v,key);
        v.pop_back();
        key[i]=true;
    }
}
void sortAll(int num[],int n)
{
    if(num==nullptr||n<=0){
        return ;
    }
    vector<int> v;
    bool key[n];
    for(int i=0;i<n;i++){
        key[i]=true;
    }
    DSF(num,n,v,key);
}
int main()
{
    int num[]={1,5,6,7,2};
    sortAll(num,sizeof(num)/sizeof(int));
    return 0;
}

---

素数环

// 给定一个数组判断，如果通过这个数组的值组成的环，相邻两个元素相加都是素数，则是素数环，则返回true，否则返回false
bool prime(int num[],int n,vector<int> &v,bool key[],bool value[])
{
    if(v.size()>=n){
        int temp=v.back();
        if(value[temp+num[0]]==true){
            for_each(v.begin(),v.end(),[](int n){
                printf("%d ",n);
            });
            printf("\n");
            return true;
        }
        return false;
    }
    for(int i=1;i<n;i++){
        if(key[i]==false)
            continue;
        int temp=v.back();
        if(value[temp+num[i]]==true){
            v.push_back(num[i]);
            key[i]=false;
            if(prime(num,n,v,key,value)==true){
                return true;
            }
            v.pop_back();
            key[i]=true;
        }
    }
    return false;
}

bool ring(int num[],int n)
{
    if(num==nullptr||n<=0){
        return false;
    }
    int primenumber[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,53,59,61,67,71,73,79,83,89,97};
    bool value[100];
    int j=0;
    for(int i=0;i<100;i++){
        if(i==primenumber[j]){
            value[i]=true;
            j++;
            continue;
        }
        value[i]=false;
    }
    vector<int> v;
    bool key[n];
    for(int i=0;i<n;i++){
        key[i]=true;
    }
    v.push_back(num[0]);
    key[0]=false;
    return prime(num,n,v,key,value);
}
int main()
{
    int num[]={1,2,2,3};
    bool key=false;
    key=ring(num,sizeof(num)/sizeof(int));
    if(key){
        cout<<"ok"<<endl;
    }else{
        cout<<"false"<<endl;
    }
    return 0;
}

---

八皇后问题

// sum表示有多少可行的占位
// num数组的下标代表的是行数，值代表的是列数，例如num[3]=6;代表的是第四行的皇后占的是第七个位置
// num数组只要保证8个行中分布都是0~7之间的数字并且不重复，就可以确保皇后不会在行或者列上冲突
int sum=0;
bool eightqueen(int num[],bool key[],int index)
{
    if(index==8){
        for(int i=0;i<8;i++){
            if(key[i]==true){
                key[i]=false;
                num[index-1]=i;
                for(int j=0;j<index-1;j++){
                    if(index-1-j==num[index-1]-num[j]||index-1-j==num[j]-num[index-1]){
                        key[i]=true;
                        return false;
                    }
                }
                key[i]=true;
                sum++;
                for(int j=0;j<index;j++){
                    cout<<num[j]<<" ";
                }
                cout<<endl;
                return true;
            }
        }
        return false;
    }
    for(int i=0;i<8;i++){
        if(key[i]==false){
            continue;
        }
        key[i]=false;
        num[index-1]=i;
        bool check=true;
        for(int j=0;j<index-1;j++){
            if(index-1-j==num[index-1]-num[j]||index-1-j==num[j]-num[index-1]){
                check=false;
                break;
            }
        }
        if(check==true)
            eightqueen(num,key,index+1);
        key[i]=true;
    }
    return false;
}
bool eightqu(void)
{
    int num[8];
    bool key[8];
    for(int i=0;i<8;i++){
        key[i]=true;
        num[i]=0;
    }
    return eightqueen(num,key,1);
}
int main()
{
    eightqu();
    cout<<sum<<endl;
    return 0;
}