算法笔记(3)| 递归

1.分治

分治的概念是指：将原问题划分为若干个小问题而结构与原问题相同或者相似的子问题，然后分别解决这些子问题，最后合并子问题，得到原问题的解。分治法的三个步骤：
(1)分解
(2)解决
(3)合并

分治法作为一种思想，其最常用的方法就是递归。

2.递归

递归简单来说就是反复调用自身函数，但是每次把问题的范围缩小，直到范围缩小到可以直接看到边界数据的结果。

递归逻辑中有两个重要的概念：
(1)递归式

是将原问题分解为若干个子问题的手段

(2)递归边界

是分解的尽头

使用递归求解n的阶乘n!

#include<stdio.h>
#include<iostream>
using namespace std;
int F(int n){
    if(n==0){
        return 1;
    }
    else{
        return F(n-1)*n;
    }
}

int main(){
    int n;
    cin>>n;
    cout<<F(n)<<endl;
    return 0;
} 

求斐波那契数列的第n项

斐波那契数列满足F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)(n>=3)

#include<stdio.h>
#include<iostream>
using namespace std;
int F(int n){
    if(n==1 || n==2){
        return 1;
    }
    else{
        return F(n-1)+F(n-2);
    }
}

int main(){
    int n;
    cin>>n;
    cout<<F(n)<<endl;
    return 0;
} 

全排列

把1-n这n个整数按照某个顺序摆放的结果称为n个整数的排列

#include<stdio.h>
#include<iostream>
using namespace std;
int num[11],n;
bool hashTable[11]={false};
void F(int index){  
    for(int i=1;i<=n;i++){
        if(hashTable[i]==false){
            hashTable[i]=true;
            num[index]=i;
            F(index+1);
            hashTable[i]=false;  //回溯 
        }
    }
    if(index==n+1){
        for(int j=1;j<=n;j++){
            cout<<num[j];
        }
        cout<<endl;
    }
}
    
int main(){
    cin>>n;
    F(1);
    return 0;
} 

n皇后问题

在一个n*n的国际象棋棋盘上放置n个皇后，使得这n个皇后两两均不在同一行、同一列、同一条对角线上，求出合法的方案数。

//将n列设为一个散列，只要每一个散列所对应的值（行）不同即可，最后再判断是否处于同一对角线上
#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
int num[11],n,count=0;
bool hashTable[11]={false};

void F(int index){  
    for(int i=1;i<=n;i++){
        if(hashTable[i]==false){
            hashTable[i]=true;
            num[index]=i;
            F(index+1);
            hashTable[i]=false;  //回溯 
        }
    }
    
    if(index==n+1){
        bool flag=true;
        for(int j=1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(abs(j-k) == abs(num[j]-num[k])){  //在同一对角线上 
                    flag=false;
                }
            }
        }
        if(flag) count++;
        return;
    }
}
    
int main(){
    cin>>n;
    F(1);
    cout<<count<<endl; 
    return 0;
}