标签：方案 台阶 03 int U4 C++ 数为 return include

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

加法原理和乘法原理

递推的概念

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

}

View Code

 

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

}

View Code

 

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

}

View Code

 

错排问题

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

}

View Code

 

 

 

 

 

 

 

 

作业部分：

作业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;

}

【时间复杂度】

View Code

 

作业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;

}

View Code

 

作业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;

}

View Code

 

作业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;

}

View Code

 

 

 

标签：方案,台阶,03,int,U4,C++,数为,return,include
From： https://www.cnblogs.com/jayxuan/p/17813488.html