递归

一、定义

程序调用自身的编程技巧称为递归（recursion）。

递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

例1：Luogu P1170

分析：以兔八哥的坐标为原点，如果猎人横坐标与纵坐标互质则兔八哥危险

#include <iostream>
#include <cmath>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
int main()
{
    int n,ax,ay,bx,by;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>ax>>ay>>bx>>by;
        if(gcd(abs(ax-bx),abs(ay-by))==1)
            cout<<"no"<<endl;
        else
            cout<<"yes"<<endl;
    }
}

例2：全排列（字典序输出）Luogu P1691

基础：字典序输出

```#include #include #include using namespace std; int main() { string a; cin>>a; set set1; for(int i=0;i<a.length();i++) set1.insert(a[i]); set::iterator it=set1.begin(); cout<<*it;

}


示例代码（未优化，会TLE）：

#include #include #include using namespace std; string s; int n,cnt; set res; set::iterator it; void dfs(int k) { if(k==n) { if(res.count(s)==0) res.insert(s); return; } for(int i=k;i<n;i++) { swap(s[k],s[i]); dfs(k+1); swap(s[k],s[i]); } } int main() { cin>>n; cin>>s; dfs(0); for(it=res.begin();it!=res.end();it++) cout<<*it<<endl; cout<<res.size();

}

## 二、递推

例1：错排

推导：

显然D1=0，D2=1。当n≥3时，不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑第n位的情况。

当k排在第n位时，除了n和k以外还有n-2个数，其错排数为Dn-2。

当k不排在第n位时，那么将第n位重新考虑成一个新的“第k位”，这时的包括k在内的剩下n-1个数的每一种错排，都等价于只有n-1个数时的错排（只是其中的第k位会换成第n位）。其错排数为Dn-1。

通过一系列推导，可以得出：

D(n) = n! (1/0! - 1/1! + 1/2! - 1/3! - ..... + (-1)^n/n!)

简化公式：D(n) = [n!/e+0.5]

#include #define MAX 10000 using namespace std; int main() { int n; cin>>n; int d1,d2,d3; d1=0; d2=1; for(int i=3;i<=n;i++) { d3=(i-1)*(d2+d1); d1=d2; d2=d3; } cout<<d3; }

例2：染色问题：相邻两格，首尾颜色不同，输入有n格，输出有几种

/* 从后往前推 r???????g? 最后一位前面已经正确：f[n-1] r???????r? 最后一位前面不正确：2f[n-2] ∴f[n]=f[n-1]+2f[n-2] */ #include #define MAX 100005 using namespace std; int main() { int n,f[MAX]; cin>>n; f[1]=3;//有争议，可能为0，f[1]=0时只需要f[1],f[2]递推即可 f[2]=6; f[3]=6; for(int i=4;i<=n;i++) f[i]=f[i-1]+2*f[i-2]; cout<<f[n]; }

# 二分查找
## 一、定义

> 二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。

折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

##二、步骤
1.假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较。如果两者相等，则查找成功。
2.如果两者不相等，就利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
3.重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

例：Luogu P1290

#include #define MAX 50005 using namespace std; int n,m,l,arr[MAX]; bool check(int x) { int last=0,cnt=0; for(int i=1;i<=n;i++) if(arr[i]-last<x) cnt++; else last=arr[i]; if(cnt>m) return false; else return true; } int main() { cin>>l>>n>>m; for(int i=1;i<=n;i++) cin>>arr[i]; arr[++n]=l; int left1=0,right1=l,middle,ans; while(left1<=right1) { middle=(left1+right1)/2; if(check(middle)) { ans=middle; left1=middle+1; } else right1=middle-1; } cout<<ans; }


变：Luogu P2440

#include #define MAX 100005 using namespace std; int n,k,len[MAX],maxnum=0,ans; bool check(int x) { int sum=0; for(int i=1;i<=n;i++) sum+=len[i]/x; if(sum>=k) return true; else return false; } int main() { cin>>n>>k; for(int i=1;i<=n;i++) { cin>>len[i]; if(maxnum<len[i]) maxnum=len[i]; }

int left1=1,right1=maxnum,mid;
while(right1>=left1)
{

    mid=(right1+left1)/2;
    if(check(mid))
    {
        ans=mid;
        left1=mid+1;
    }

    else
        right1=mid-1;

}
cout<<ans; } ```

信奥集训营笔记：Day 3

递归与二分查找

递归

一、定义

CATALOG

FEATURED TAGS

FRIENDS