Acwing_藍橋_遞歸

一.關於由數據範圍反推演算法複雜度及其演算法

關於輸入輸出：問題規模小於105：cin，scanf都差不多，但是要是大於105推薦使用scanf和printf。

二.關於遞歸

1.定義

自己調用自己

2.注意事項：

  • 判斷遞歸結束的邊界
  • 少調用局部變數，會佔用很大的記憶體
  • 要怎麼調用自身

3.每個遞歸都可以轉化成遞歸搜索樹

例如計算斐波那契數列可以轉化成如下（這裡不討論剪枝，也就是不把重複的剪掉）

三.遞歸練習

1.遞歸實現指數型枚舉

//www.acwing.com/problem/content/94/

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;



const int N = 16;

int n;
int st[N];//表示狀態：0表示還不考慮，1表示選，2表示不選

void dfs(int u)
{
    if(u > n) // 終止條件
    {
        for(int i = 1; i <= n; i++)
            if(st[i] == 1) printf("%d ", i);
        puts("");
        return;
    }

    st[u] = 1; 
    dfs(u + 1);
    st[u] = 0;//回溯，要恢復原來的狀態

    st[u] = 2; 
    dfs(u + 1);
    st[u] = 0;
}

int main()
{
    scanf("%d", &n);
    dfs(1);
    return 0;
}

2.遞歸實現排列型枚舉

//www.acwing.com/problem/content/96/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 10;
int st[N];
bool used[N];
int n;

void bfs(int u)
{
    if (u > n)
    {
        for (int i = 1; i <= n; i++) printf("%d ", st[i]);
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!used[i]) //表示i沒有被用過
        {
            used[i] = true;
            st[u] = i;
            bfs(u+1);
            st[u] = 0;
            used[i] = false;
        }
    }
}

int main()
{
    scanf("%d", &n);
    bfs(1);
    return 0;
}

關於上面遞歸演算法的時間複雜度分析：

第一層中的基本操作是for循環進行深搜，遍歷為O(n),然後遞歸中有n個這樣的函數，也就是n個分支。第二層也是一個for循環，然後循環中有n-1個分支，時間複雜度是O(n*(n-1))。第三層就是O(n*(n-1)(n-2)),以此類推，最後一層是的時間複雜度是O(nn!)。所以總的時間複雜度是O(n*(1+n+n*(n-1)+...+n!)),該循環是大於O（n!）的，經過放縮法可以證明是小於O（3n！）。所以最終時間複雜度為O（n*n!）

3.遞歸實現組合型枚舉

//www.acwing.com/problem/content/95/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int N = 30;
int n,m;
int st[N];
bool path[N];

void dfs(int u,int t)
{
    if(u == m)
    {
        for(int i = 0 ; i < m ; i ++ ) printf("%d ", st[i]);
        printf("\n");
        return;
    }
    for(int i = t; i <= n ; i++)
    {
        if(u==0&&i + m - 1 > n ) break;
        if(!path[i])
        {
            st[u] = i;
            path[i] = true;
            dfs(u+1,i+1);
            if(u)path[i] = false;
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    dfs(0,1);
    return 0;
}
Tags:

VirMach 便宜 VPS