C++U4- 04 - 新递推2

 排列

 公式

 单选

 组合数

 单选

 递推练习

[直线分割平面问题]

【参考代码】

#include <iostream>
using namespace std;
int a[1010];  //a[i]:第i条直线最多能将 这个圆分割成的部分数 
int main() {
    //1、定义变量n,进行输入,数组a进行存储 
    int n;
    cin >> n;
    //2、初始条件，1条直线最多可以将圆分割成两部分 
    a[1] = 2;
    //3、递推出n条直线，a[i] = a[i - 1] + 交点数 + 1; 
    for(int i = 2; i <= n; i++){
        a[i] = a[i - 1] + i; //递推式 
    }
    //4、输出 
    //输出 n 条直线最多能将这个圆分割成的部分数
    cout << a[n];
    return 0;
}

[格子涂色问题]

【思路分析】
用 a[i] 表示把 i 个格子按要求涂色的涂法，易得：
当 i=1 时，有 1 个格子时有 3 种涂法；当 i=2 时，有 2 个格子时有 6 种涂法；当 i=3 时，有 3 个格子时有 6 种涂法。

当 i≥4 时，假设已经求出 a[1]~a[i−1]，求 a[i]，对于 a[i−1] 有两种情况：
（1）第 i−1 格的涂色合法，即在没有加入第 i 个格子的时候，第 i−1 个格子和第 i−2 个格子颜色不同且和第 1 个格子的颜色也不相同。当加入第 i 个格子，第 i 个格子的颜色已经是确定的。所以此时的方案数为：

a[i−1]×1=a[i−1]

（2）第 i−1 格的涂色不合法(对于整体的 i 个格子依然是合法的)，即在没有加入第 i 个格子的时候，即第 i−1 个格子和第 i−2 个格子颜色不同但是和第 1 个格子的颜色相同。当加入第 i 个格子，第 i 个格子有两种情况。此时的方案数为：

a[i−2]×1×2=2×a[i−2]
分类用加法原理，分步用乘法原理
综合以上两种情况：
a[i]=a[i−1]+2×a[i−2]，i≥4

1、定义变量n,进行输入,定义数组a,进行存储

2、初始条件,1个格子时有3种涂法, 2个格子时有6种涂法,3个格子时有6种涂法

3、递推式:a[i]=a[i-1]+2*a[i-2]

4、输出

【参考代码】
#include <iostream>
using namespace std;
long long a[66]; //a[i]:把i个格子 按要求涂色的涂法 
int main() {
    //1、定义变量n,进行输入,定义数组a,进行存储 
    int n;
    cin >> n;
    //2、初始条件,1个格子时有3种涂法, 2个格子时有6种涂法,3个格子时有6种涂法
    a[1] = 3; 
    a[2] = 6; 
    a[3] = 6;
    //3、递推式:a[i]=a[i-1]+2*a[i-2] 
    for(int i = 4; i <= n; i++){
        a[i] = a[i - 1] + 2 * a[i - 2];
    }
    //4、输出 
    cout << a[n]; //输出把 n 个格子按要求涂色的涂法
    return 0;
}