标签：04 int U4 感染 cin C++ 折线 交点 递推

上节课作业部分(点击跳转)

 

排列组合

排列

 组合：

 

 练习题目

 题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;

}

View Code

 

题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;

}

View Code

 

 

作业部分：

 

 

[蜜蜂路线]：

每个位置只能走到后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;

}

View Code 

[骨牌铺法]

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;

}

View Code

[求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;

} 

View Code

 

 

标签：04,int,U4,感染,cin,C++,折线,交点,递推
From： https://www.cnblogs.com/jayxuan/p/17831346.html