上节课作业部分(点击跳转)
加法原理和乘法原理
递推的概念
练习题1、[兔子数列]
【算法分析】 初始条件：第 1 个月有 1 对兔子，第 2 个月有 1 对兔子。当大于等于 3 个月时：第 i 个月兔子数 = 第 i−1 个月兔子数+第 i−2 个月兔子数。
【参考代码】
include <iostream>
using namespace std;
const int N = 60;
long long f[N]; //用来存储兔子数（f[i]：第 i 个月的兔子数）int main() {
int n;
cin >> n;
f[1] = 1; // 初始条件
f[2] = 1; // 初始条件
for(int i = 3; i <= n; i++) {
/ 第i个月兔子数 =
第i-1个月兔子数+第i-2个月兔子数 /
f[i] = f[i-1] + f[i-2];
}
cout << f[n]; // 输出第 n 个月的兔子数
return 0;
}
练习题2、[走楼梯]
【算法分析】 上第一级台阶的方案数为 1，上第二级台阶的方案数为 2，上到第 i 级台阶的方案数 = 上到第 i−1 级台阶的方案数 + 上到第 i−2 级台阶的方案数，通过递推的方法可求出上到第 n 级楼梯的方案数。【参考代码】
include <iostream>
using namespace std;
const int N = 60;
long long f[N]; //用来存储方案数（f[i]：上到第 i 级台阶的方案数）int main() {
int n;
cin >> n;
f[1] = 1; // 初始条件：上到第 1 级台阶的方案数为 1
f[2] = 2; // 初始条件：上到第 2 级台阶的方案数为 2
for(int i = 3; i <= n; i++) {
//上到第i级台阶的方案数 = 上到第i-1级台阶的方案数 + 上到第i-2级台阶的方案数
f[i] = f[i-1] + f[i-2];
}
cout << f[n]; // 输出上到第n级台阶的方案数
return 0;
}
练习题3、走楼梯升级版
【算法分析】 上第一级台阶的方案数为 1，上第二级台阶的方案数为 2，上第二级台阶的方案数为 4。上到第 i 级台阶的方案数 = 上到第 i−1 级台阶的方案数 + 上到第 i−2 级台阶的方案数 + 上到第 i−3 级台阶的方案数，通过递推的方法可求出上到第 n 级楼梯的方案数。
【参考代码】
include <iostream>
using namespace std;
const int N = 60;
long long f[N]; //用来存储方案数（f[i]：上到第 i 级台阶的方案数）int main() {
int n;
cin >> n;
f[1] = 1; // 初始条件：上到第 1 级台阶的方案数为 1 0->1
f[2] = 2; // 初始条件：上到第 2 级台阶的方案数为 2 0->1->2 0->2
f[3] = 4; // 初始条件：上到第 3 级台阶的方案数为 4 0->1->2->3 0->1->3 0->2->3 0->3
for(int i = 4; i <= n; i++) {
//上到第i级台阶的方案数 = 上到第i-1级台阶的方案数 + 上到第i-2级台阶的方案数 + 上到第i-3级台阶的方案数
f[i] = f[i - 1] + f[i - 2] + f[i - 3];
}
cout << f[n]; // 输出上到第n级台阶的方案数
return 0;
}
错排问题
练习题4、错排问题
【算法分析】 a i 表示 i 封信封都装错的方案数，初始化： 初始条件：1封信都装错的方案数为0 a 1 = 0 2封信都装错的方案数为1 a 2 = 1当 i 大于等于 3，递推式为:a[i]=(i−1)∗(a[i−2]+a[i−1])
【参考代码】
include<iostream>
using namespace std;
const int N = 30;
long long a[N];int main() {
int n;
cin >> n;
a[1] = 0; //初始条件：1封信都装错的方案数为0
a[2] = 1; //初始条件：2封信都装错的方案数为1
for (int i = 3; i <= n; i++) {
a[i] = (i - 1) * (a[i - 2] + a[i - 1]); //递推式
}
cout << a[n]; //输出把n封信都装错的方案数
return 0;
}
作业部分：
作业1、[部分背包问题]
【算法分析】
最优策略：每一次贪心地选当前单位重量价值最大的金币装入口袋。
【参考代码】
include <iostream>
include <algorithm>
using namespace std;
struct node {
int w, v; //w表示重量，v表示价值
double up; //单位重量价值
}a[110];
bool cmp(node x, node y) {
return x.up > y.up; //单位价值大的排在前面
}
int main() {
int n, m;
cin >> n >> m;
double ans = 0; //记录答案
for (int i = 1; i <= n; i++) {
cin >> a[i].w >> a[i].v;
a[i].up = a[i].v * 1.0 / a[i].w;
}
sort(a + 1, a + n + 1, cmp); //排序
for (int i = 1; i <= n; i++) {
if (a[i].w <= m) { //够的话全拿
ans += a[i].v;
m -= a[i].w;
}
else { //拿上能拿的部分
ans += m * a[i].up;
break; //直接退出循环
}
}
printf("%.2lf", ans);
return 0;
}
【时间复杂度】
作业2、[比赛安排]
【算法分析】
当只有两个比赛（两个时间段）的时候，选择参加哪个都是可以的，当有第三个比赛的时候，这时候就会发现优先选择前两个结束较早的那个比赛，才能完整的看第三个活动，所以尽早参加完一个比赛就有机会参加其它比赛（也就是按结束时间从早到晚排序）。
【参考代码】
include <iostream>
include <algorithm>
using namespace std;
struct node {
int s, e;//开始时间，结束时间
}a[1000010];
bool cmp(node a, node b) {
return a.e < b.e;
}
int main() {
int n, num = 1;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i].s >> a[i].e;
sort(a, a + n, cmp);
int last = a[0].e;
for (int i = 1; i < n; i++) {
if (a[i].s >= last) { //下一个活动的开始时间大于等于下一个活动的结束时间
num++;
last = a[i].e;
}
}
cout << num;
return 0;
}
作业3、跳木桩
【算法分析】 题目希望求出最大的体力消耗，应该让小码君每次跳到和自己高度差最大的木桩。 所有可以将木桩的高度进行从小到大排序，设置左右指针 l=0，r=n，先从地面 h 0 跳到 h r ，r--,再从 h r 跳到 h l ，l++，如此反复。【参考代码】
include <iostream>
include <algorithm>
using namespace std;
long long t;
int h[310];int main() {
int n, l, r;
cin >> n;
h[0] = 0;
for(int i = 1; i <= n; i++){
cin >> h[i];
}
sort(h, h + 1 + n);
l = 0;
r = n;
while(l < r){
t += (h[l] - h[r])(h[l] - h[r]);
l++;
t += (h[r] - h[l])(h[r] - h[l]);
r--;
}
cout << t;
return 0;
}
作业4、[找数字]
【算法分析】 用数组存最大值和最小值的各个位，最大值的各个位从左往右优先取 9。最小值的首位，可以假设其它位取 9 则首位最小能取多少，要注意首位不能取0，最小值的其它位也可以按照这个思路。【参考代码】
include <iostream>
include <algorithm>
using namespace std;
int a[110], b[110];
int main() {
int m, s;
cin >> m >> s;
int t = s, p = s;
if(m == 1&& s == 0){
cout << 0 << " " << 0;
return 0;
}
for (int i = 1; i <= m; i++) { //最大整数
if (t >= 9) { //t大于等于9则取最大的9
a[i] = 9;
t -= 9;
}
else { //否则取t
a[i] = t;
t = 0;
}
}
for (int i = 1; i <= m; i++) { //最小整数
if (i == 1) { //首位不能是0
int y = s - (m - 1) * 9; //除首位外其它位取9，则首位最小能取 s-(m-1)9
if (y > 0) { //y大于0，首位取y
b[i] = y;
s -= y;
}
else { //否则首位取1
b[i] = 1;
s -= 1;
}
}
else {
int y = s - (m - i) * 9; //从左往右第i位，i右边的位上取9，则i位最小能取 y=s-(m-i)9
if (y > 0) { //y大于0，直接取y
b[i] = y;
s -= y;
}
else { //y小于等于0，说明i右边的位不能全部取9，i位最小能取0
b[i] = 0;
}
}
}
if (m * 9 < p || p < 0 || p == 0 && m>1) { //所有位取9，各个位上的和仍小于p 、p小于0、各个位上的和为0，m>1均不满足
m = 1;
a[1] = -1, b[1] = -1;
}
for (int i = 1; i <= m; i++) {
cout << b[i];
}
cout << " ";
for (int i = 1; i <= m; i++) {
cout << a[i];
}
return 0;
}