上节课作业部分(点击跳转)
排列组合
排列
组合：
练习题目
题2
编程题1，用递推求组合数
编程题3：
[【递推】直线分割平面问题]
【算法分析】 用 a[i] 表示 i 条直线最多能将这个圆分割成的部分数: 当 i=1 时，a[1]=2; 当 i=2 时，a[2]=4; 当 i=3 时，a[3]=7; 要分割成最多部分，则新加的直线要与之前的直线都要分别交于不同点。 当 i=4 时： 第 4 条直线要与前 3 条直线都要有不同的交点， 这 3 个交点构造出了 4 个部分(交点数 + 1) a[4]=a[3]+交点数+1=a[3]+3+1=11;当 i>=2 时， a[i]=a[i−1]+交点数+1，第 i 条直线和前 i−1 条直接都有不同的交点，且交点数为 i−1。得 a[i]=a[i−1]+i。
【参考代码】
include <iostream>
using namespace std;
const int N = 1e3 + 10; //a[i]:第i条直线最多能将 这个圆分割成的部分数
int a[N];int main() {
int n;
cin >> n;
//初始条件 ：1条直线最多可以将圆 分割成两部分
a[1] = 2;
for(int i = 2; i <= n; i++){
//a[i] = a[i - 1] + 交点数 + 1;
a[i] = a[i - 1] + i; //递推式
}
//输出 n 条直线最多能将这个圆分割成的部分数
cout << a[n];
return 0;
}
题4、
[【递推】折线分割平面问题]
本题可参考链接：https://www.cnblogs.com/ping2yingshi/p/12485742.html
【算法分析】 用 a[i] 表示 i 条折线最多能将平面分割成的部分数: 当 i=1 时，a[1]=2; 当 i=2 时，a[2]=7;除了初始的点之外每一个交点都代表着一个新增的区域，求折线最大分割平面数也即折线带来的最大交点数
假设已知 a[i−1]，对于第 i 条折线，折线中的每条线最多可以有 2∗(i−1) 个交点，折线转折处有 1 个交点，每一个交点会带来一个新区域，则递推公式为 a[i]=a[i−1]+4∗(i−1)+1。
【参考代码】
include <iostream>
using namespace std;
const int N = 10010;
int a[N];int main() {
int c;
cin >> c;
a[1] = 2;
for (int i = 2; i <= 10000; i++) {
a[i] = a[i - 1] + 4 * (i - 1) + 1;
}
for (int i = 1; i <= c; i++) {
int n;
cin >> n;
cout << a[n] << endl;
}
return 0;
}
作业部分：
[蜜蜂路线]：
每个位置只能走到后1或后2，反过来例如5只能从4和3走过来，那么方案数也是就4的方案加3的方案数；
【算法分析】 求蜜蜂从 x 到 y 所有可能的方案数。 a i 表示跨越 i 格的方案数。 从 1 到 2 可能的路径为：1->2，a[1] = 1; 从 1 到 3 可能的路径为: 1->2->3，1->3，a[2] = 2; 从 1 到 4 可能的路径为: 1->2->3->4，1->3->4，1->2->4，a[3] = 3;得出爬 n 个格子的方案数为：a
i
= a
i−1
+ a
i−2
。【参考代码】
include<iostream>
using namespace std;
const int N = 60;
long long a[N];int main() {
int n;
cin >> n;
a[1] = 1; //初始条件：爬上1个格子的方案数
a[2] = 2; //爬上2个格子的方案数
for (int i = 3; i <= 50; i++) {
a[i] = a[i - 1] + a[i - 2]; //爬i个格子的方案数 = 爬i-1个格子的方案数 + 爬i-2个格子的方案数
}
while (n--) {
int x, y;
cin >> x >> y;
cout << a[y - x] << endl; //从x格到y格，爬上y-x个格子的方案数
}
return 0;
}
[骨牌铺法]
f(i) = f(i-1)+f(i-2)
[流感传染]
【算法分析】 定义整型数组 a，下标从 1 开始存，防止越界。未被感染的置为 0，已被感染的置为 1，空的房子置为 −1。m−1 天感染，遍历数组 a，为防止在这一轮中，感染后的人感染下一轮的人，将上一轮已被感染的人的邻居置为2。然后再次遍历数组 a， a[i][j] 等于 2 则置为 1。
m−1 天感染结束后，统计被感染人数，并输出。
【参考代码】
include<iostream>
using namespace std;
const int N = 110;
int a[N][N];int main() {
int n, m, sum = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
char s;
cin >> s;
if (s == '.') a[i][j] = 0; //未被感染的
if (s == '@') a[i][j] = 1; //已被感染的
if (s == '#') a[i][j] = -1;//空的
}
}
cin >> m;
while (m > 1) { //m-1天
m--;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == 1) { //防止在这一轮中，感染后的人感染下一轮的人，将邻居置为2
if (a[i + 1][j] == 0) a[i + 1][j] = 2;
if (a[i - 1][j] == 0) a[i - 1][j] = 2;
if (a[i][j + 1] == 0) a[i][j + 1] = 2;
if (a[i][j - 1] == 0) a[i][j - 1] = 2;
}
}
}
for (int i = 1; i <= n; i++) { //这一轮被感染的人置为1
for (int j = 1; j <= n; j++) {
if (a[i][j] == 2) a[i][j] = 1;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == 1) sum++;
}
}
cout << sum;
return 0;
}
[求f(x,n)]
【算法分析】 定义浮点型数组 f，初始化为 x； 可以用递推的方法求出 f[n] 的值。 初始化：f[0]=x; for 循环：开始：i = 1；结束：i <= n；变化：加 1。 递推式为：f[i] = sqrt(n - i + 1 + f[i - 1]);【参考代码】
include <iostream>
include <cmath>
using namespace std;
double f[20];
int main(){
int x, n;
cin >> x >> n;
f[0] = x; //初始化
for(int i = 1; i <= n; i++){
f[i] = sqrt((n - i + 1) + f[i - 1]);
}
printf("%.2f",f[n]);
return 0;
}