递归

方法归纳

判断是否为递归问题

取决于是否每次执行的是相同的工作起到相同的功能
例如汉诺塔中的每次n个碟子移动时，总是需要先将n-1个碟子移到中间碟子中
可以用一般式n表示该问题

总结

1.结束时的条件
2.分析一层递归需要实现的功能
3.返回值是如何，传送给上一级的信息

汉诺塔


#include< iostream>
using namespace std;
void  hanoi(int n, char one, char two, char three);
//one是原始柱，two是中间柱子，three是结尾柱
void move(char x,char y);
void move(char x, char y)//输出
{
    cout << x << "->" << y << endl;
}
void  hanoi(int n,char one,char two,char three)
{
    if (n == 1)
        move(one, three);
    else
    {
        hanoi(n - 1, one,three,two);
        move(one, three);
        //每次执行的操作
        hanoi(n - 1, two, one, three);
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    char one = '1', two = '2', three = '3';
    hanoi(n, one, two, three);
    return 0;
}

汉诺塔问题分析与总结

1.< 判断是否递归>模拟汉诺塔移动，因为大的总在小的下面，所以当最大的碟子放在C上时，n-1个在C上，这时可以忽略这个这个最大的碟子，也就是把问题看成n-1个碟子从B柱子移动到C柱子（A为原始柱，B为中间柱，C为目标柱），所以这个是一个递归问题（每次都需要将n-1个碟子送到中间柱子上）
2.< 结束操作与条件>
分析n-1的终点是什么？必定是只剩一个碟子（这里可以用极限n=1）
3.< 每层执行的功能>
即执行从A上移动n-1个碟子到B上，再将A最大碟子移动到C上，再将B上n-1个碟子移到C上

二分法求数组最大子序列


#include< iostream>
#include< cstdlib>//malloc
using namespace std;
int Maxnumber(int x, int y, int z)//判断最大的值
{
    return x > y ? x > z ? x : z : y > z ? y : z;
}
int Max(int arry[], int left, int right)
{
    if (left == right)
        return arry[left];
    int center = (left + right)/2;
    int Tempsum=0,Maxleftsum=0,Maxrightsum=0;
    //求出从中间点向左右衍生的最大子序列值
    for (int x = center; x >= left; x--)
    {
        Tempsum += arry[x];
        Maxleftsum = Tempsum > Maxleftsum ? Tempsum : Maxleftsum;
    }
    Tempsum = 0;
    for (int x = center + 1; x <= right; x++)
    {
        Tempsum += arry[x];
        Maxrightsum = Tempsum > Maxrightsum ? Tempsum : Maxrightsum;
    }
    return Maxnumber(Maxrightsum + Maxleftsum, Max(arry, left, center), Max(arry, center + 1, right));
    //只需要比较左边最大值，右边最大值和从中间开始的最大值
}
int main()
{
    int* arry, x,Maxsum=0,Tempsum=0;
    cin >> x;
    arry = (int*)malloc(x * sizeof(int));//动态数组
    for (int y=0; y <= x - 1; y++)
        cin >> arry[y];
    Maxsum = Max(arry, 0, x-1);
    if (Maxsum < 0)
        cout << 0;
    else
        cout << Maxsum; 
    return 0;
}

总结

1.< 是否为递归>每次都进行二分，都是将总的分为2，再从左边最大值和右边最大值还有中间衍生的最大值这3者中取最大值。
2.< 结束条件>二分的结果必定是只剩一个
3.< 每次实现功能以及返回信息>算出3者大小，返回最大值