【算法设计与分析】第四章分治法

喜欢ヅ旅行 2023-07-14 08:19 99阅读 0赞

## 启发式规则： ##

**1. 平衡子问题**：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。  
**2. 独立子问题**：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。

## 分治法的求解过程 ##

**1.划分**：把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。  
**2.求解子问题**：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。  
**3.合并**：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。

## 递 归（Recursion） ##

递归就是子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。  
递归有两个基本要素：  
⑴ **边界条件**：确定递归到何时终止；  
⑵ **递归模式**：大问题是如何分解为小问题的。  
**优点：**  
递归算法结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此，它为设计算法和调试程序带来很大方便，是算法设计中的一种强有力的工具。  
**缺点：**  
因为递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。

## 递归与分治 ##

**【最大子段和问题】**  
给定由n个整数组成的序列(a1, a2, …, an)，最大子段和问题要求该序列形如  
的最大值（1≤i≤j≤n），当序列中所有整数均为负整数时，其最大子段和为0。例如，序列(-20, 11, -4, 13, -5, -2)的  
最大子段和为： 20  
**【求解】**  
最大子段和问题的分治策略是：  
（1）划分：按照平衡子问题的原则，将序列 ( a 1 , a 2 , … , a n ) (a\_1, a\_2, …, a\_n) (a1,a2,…,an)划分成长度相同的两个子序列 ( a 1 , … , a n / 2 ) (a\_1, …, a\_\{n/2\}) (a1,…,an/2)和 ( a n / 2 ＋ 1 , … , a n ) (a\_\{n/2\} ＋1, …, a\_n) (an/2＋1,…,an)，则会出现以下三种情况：  
①  a 1 , … , a n a\_1, …, a\_n a1,…,an的最大子段和＝ a 1 , … , a n / 2 a\_1, …,a\_\{n/2\} a1,…,an/2的最大子段和；  
② a 1 , … , a n a\_1, …, a\_n a1,…,an的最大子段和＝ a n / 2 ＋ 1 , … , a n a\_\{n/2\}＋1, …, a\_n an/2＋1,…,an的最大子段和；  
③ a 1 , … , a n a\_1, …, a\_n a1,…,an的最大子段和＝ Σ k = i j a k Σ\_\{k=i\}^ja\_k Σk=ijak ，且 1 < = i < = n / 2 1<=i<=n/2 1<=i<=n/2并且 n / 2 + 1 < = j < = n n/2+1<=j<=n n/2\+1<=j<=n  
（2）求解子问题：对于划分阶段的情况①和②可递归求解，情况③需要分别计算左半边和右半边  s 1 = m a x ( Σ k = i n / 2 a k ) , 1 < = i < = n / 2 s\_1=max(Σ\_\{k=i\}^\{n/2\}a\_k),1<=i<=n/2 s1=max(Σk=in/2ak),1<=i<=n/2和 s 2 = m a x ( Σ k = n / 2 + 1 j a k ) , n / 2 + 1 < = j < = n s\_2=max(Σ\_\{k=n/2+1\}^ja\_k),n/2+1<=j<=n s2=max(Σk=n/2\+1jak),n/2\+1<=j<=n，则 s 1 + s 2 s\_1+s\_2 s1\+s2是③的最大值。  
（3）合并：比较在划分阶段的三种情况下的最大子段和，取三者之中的较大者为原问题的解。

**代码实现：**

#include<bits/stdc++.h>
    using namespace std;
    int n,a[100010],ans;
    
    int calculate(int left,int right)
    { 
        int sum=0;
        if(left==right)
        { 
            if(a[left]>0)
                sum=a[left];
            else
                sum=0;
        }
        else
        { 
            int sum1=0,sum2=0,sum3=0;
            int mid=(left+right)/2;
            sum1=calculate(left,mid);
            sum2=calculate(mid+1,right);
            int tmp1=0,cnt1=0;
            for(int i=mid;i>=left;i--)
            { 
                cnt1+=a[i];
                tmp1=max(cnt1,tmp1);
            }
            int tmp2=0,cnt2=0;
            for(int i=mid+1;i<=right;i++)
            { 
                cnt2+=a[i];
                tmp2=max(cnt2,tmp2);
            }
            sum3=tmp1+tmp2;
            sum=max(sum1,max(sum2,sum3));
        }
        return sum;
    }
    int main()
    { 
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        ans=calculate(1,n);
        cout<<ans<<endl;
        return 0;
    }

【循环赛日程安排问题】  
设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表：  
（1）每个选手必须与其他n-1个选手各赛一次；  
（2）每个选手一天只能赛一次。  
按此要求，可将比赛日程表设计成一个 n 行n-1列的二维表，其中，第 i 行第 j 列表示和第 i 个选手在第 j 天比赛的选手。  
(a)  2 k ( k = 1 ) 2\_k(k=1) 2k(k=1)个选手比赛  
![在这里插入图片描述][20200314085126512.png]  
(b)  2 k ( k = 2 ) 2\_k(k=2) 2k(k=2)个选手比赛  
![在这里插入图片描述][2020031408461289.png]  
©  2 k ( k = 3 ) 2\_k(k=3) 2k(k=3)个选手比赛  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70]  
根据观察得到规律：  
（1）左上角：左上角为 2 k − 1 2\_\{k-1\} 2k−1个选手在前半程的比赛日程；  
（2）左下角：左下角为另 2 k − 1 2\_\{k-1\} 2k−1个选手在前半程的比赛日程，由左上角加 2 k − 1 2\_\{k-1\} 2k−1得到，例如 2 2 2^2 22个选手比赛，左下角由左上角直接加2得到， 2 3 2^3 23个选手比赛，左下角由左上角直接加4得到；  
（3）右上角：将左下角直接抄到右上角得到另 2 k − 1 2\_\{k-1\} 2k−1个选手在后半程的比赛日程；  
（4）右下角：将左上角直接抄到右下角得到 2 k − 1 2\_\{k-1\} 2k−1个选手在后半程的比赛日程；

**代码实现：**

#include<bits/stdc++.h>
    using namespace std;
    int n,a[10010][10010];
    
    void init(int k)
    { 
        int x=2,tmp=x;
        a[1][1]=1; a[1][2]=2;
        a[2][1]=2; a[2][2]=1;
        for(int p=1;p<k;p++)
        { 
            tmp=x,x*=2;
            for(int i=tmp+1;i<=x;i++)
                for(int j=1;j<=tmp;j++)
                    a[i][j]=a[i-tmp][j]+tmp;
            for(int i=1;i<=tmp;i++)
                for(int j=tmp+1;j<=x;j++)
                    a[i][j]=a[i][j-tmp]+tmp;
            for(int i=tmp+1;i<=x;i++)
                for(int j=tmp+1;j<=x;j++)
                    a[i][j]=a[i-tmp][j-tmp];
        }
    }
    
    int main()
    { 
        cin>>n;
        init(n);
        for(int i=1;i<=n;i++)
        { 
            for(int j=1;j<=n;j++)
            { 
                cout<<a[i][j]<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
        return 0;
    }

[20200314085126512.png]: /images/20230529/c11e31674fb84271b6210ba787500906.png
[2020031408461289.png]: /images/20230529/5244b636758b4781af8c1d0b788ecca8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2MDIyNA_size_16_color_FFFFFF_t_70]: /images/20230529/cff881dbd5ab45c593db844b5bc4009b.png