c++算法入门

1、递推

找规律

1、初始条件

2、基础规律

1、顺推

由开始，推结束状态，顺推

最常考的就是 斐波那契数列

#include <iostream>
using namespace std;

int a[110];

int main()
{
    int n;
    cin >> n;

    a[1] = 1; // 初始条件
    for (int i = 2; i <= n; i++)
    {
        a[i] = a[i - 1] + a[i - 2]; // 规律 关系式
    }
    cout << a[n];

    return 0;
}

2、逆推

由结束，推开始， 逆推

二、递归

递进+回归 合在一起是递归，利用函数实现（自己调用自己， 类似于梦中梦）

1、递进

函数自己调用自己

#include <iostream>
using namespace std;

void mf()
{
    cout << "进入下一层" << endl;
    mf();
}

int main()
{
    mf();

    return 0;
}

占用资源达到一定程度之后，强制结束（while（true) 不会）

2、回归

回归可以（一定范围内）让函数 正常结束

函数调用自己的时候加上限制条件

#include <iostream>
using namespace std;

void mf(int x)
{
    cout << x << ":进入下一层" << endl;
    x++;
    if (x < 5)
    {
        mf(x);
    }
    return;
}

int main()
{
    mf(0);

    return 0;
}

递进+回归合并在一起为递归

#include <iostream>
using namespace std;

void fun(int x)
{
    cout << x << " "; // 递进写
    x++;
    if (x <= 10)
    {
        fun(x);
    }
    return;
}

void fun2(int n)
{
    if (n < 10)
    {
        fun2(n + 1);
    }
    int a = 11 - n;
    cout << a << " "; // 回归写
    return;
}

int main()
{
    fun(1);
    cout << endl;
    fun2(1);

    return 0;
}