企业网站建设的案例,科技网站大全,成都开发网站建设,做健身网站开题报告目录
1. 部分复制字符串(★)
2. 按字典顺序排列问题(★★)
3. 地下城游戏(★★★)
附录
动态规划 1. 部分复制字符串
将字符串2小写字母复制到字符串1#xff1a;编写程序,输入字符串s2,将其中所有小写字母复制到字符串数组strl中。例如#xff1a;aal1bb22cc33de4AA55…
目录
1. 部分复制字符串(★)
2. 按字典顺序排列问题(★★)
3. 地下城游戏(★★★)
附录
动态规划 1. 部分复制字符串
将字符串2小写字母复制到字符串1编写程序,输入字符串s2,将其中所有小写字母复制到字符串数组strl中。例如aal1bb22cc33de4AA55BB”,生成的strl为aabbccde。
代码
#includestdio.hint main()
{int sum0,t0,i;char s[50],s1[50];scanf(%s,s);for(i0;s[i]!\0;i){if(s[i]as[i]z){s1[t]s[i];}}s1[t]\0;printf(%s,s1);
}
输入输出 aal1bb22cc33de4AA55BB aabbccde 2. 按字典顺序排列问题
输入若干英文单词将每个单词的首字母转换成大写字母其他字母为小写并按字典顺序排列原题为代码填空题以下代码已补全
代码
#include stdio.h
#include stdlib.h
#include string.hint cmp(const void *a, const void *b)
{return strcmp(*(char **)a, *(char **)b);
}int main(int argc, char *argv[])
{int n 0;int i;printf(how many words?\n);scanf(%d, n);char **s new char *[n];for (i 0; i n; i){s[i] new char[100];scanf(%s, s[i]);char *t s[i];while (*t ! \0){if (t s[i] (*t a *t z))*t *t - a A;if (t s[i] (*t A *t Z))*t *t - A a;t;}}qsort(s, n, sizeof(char *), cmp);for (i 0; i n; i){printf(%s\n, s[i]);}return 0;
}
输入输出 how many words? 3 by boy book Book Boy By 3. 地下城游戏
一些恶魔抓住了公主P并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士K最初被安置在左上角的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快到达公主骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。
例如考虑到如下布局的地下城如果骑士遵循最佳路径 右 - 右 - 下 - 下则骑士的初始健康点数至少为 7。
-2 (K)-33-5-1011030-5 (P)
说明: 骑士的健康点数没有上限。 任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。
代码
#include bits/stdc.h
using namespace std;class Solution
{
public:int calculateMinimumHP(vectorvectorint dungeon){int row dungeon.size();int col dungeon[0].size();int dp[row][col] {0};dp[row - 1][col - 1] max(1 - dungeon[row - 1][col - 1], 1);for (int i row - 2; i 0; i--){dp[i][col - 1] max(dp[i 1][col - 1] - dungeon[i][col - 1], 1);}for (int i col - 2; i 0; i--){dp[row - 1][i] max(dp[row - 1][i 1] - dungeon[row - 1][i], 1);}for (int i row - 2; i 0; i--){for (int j col - 2; j 0; j--){dp[i][j] max(min(dp[i 1][j], dp[i][j 1]) - dungeon[i][j], 1);}}return dp[0][0];}
};int main()
{Solution s;vector vector int nums {{-2,-3,3},{-5,-10,1},{10,30,-5}};cout s.calculateMinimumHP(nums) endl;return 0;
}
输出 7 附录
动态规划
基本概念
动态规划每次决策依赖于当前状态又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的这种多阶段最优化决策解决问题的过程就称为动态规划(DP)。动态规划算法通常用于求解具有最优性质的问题
算法设计
1找出最优解的性质并描述其结构特征 2递归定义最优值 3以自底向上的方式计算最优值 4根据计算最优值时得到的信息构造出最优解
具体步骤
(1)划分阶段按照问题的时间或空间特征把问题分为若干个阶段。在划分阶段时注意划分后的阶段一定要是有序的或者是可排序的否则问题就无法求解。 (2)确定状态和状态变量将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然状态的选择要满足无后效性。 (3)确定决策并写出状态转移方程因为决策和状态转移有着天然的联系状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策状态转移方程也就可写出。但事实上常常是反过来做根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。 (4)寻找边界条件给出的状态转移方程是一个递推式需要一个递推的终止条件或边界条件。
能采用动态规划求解的问题的一般要具有3个性质
(1) 最优化原理如果问题的最优解所包含的子问题的解也是最优的就称该问题具有最优子结构即满足最优化原理。 (2) 无后效性即某阶段状态一旦确定就不受这个状态以后决策的影响。也就是说某状态以后的过程不会影响以前的状态只与当前状态有关。 (3) 有重叠子问题即子问题之间是不独立的一个子问题在下一阶段决策中可能被多次使用到。该性质并不是动态规划适用的必要条件但是如果没有这条性质动态规划算法同其他算法相比就不具备优势动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术它在实现的过程中不得不存储产生过程中的各种状态所以它的空间复杂度要大于其它的算法。
