接帮人家做网站的网站,电商网站建设分析,平阳手机网站制作,江浦做网站第1题#xff1a;拦截导弹 某国为了防御敌国的导弹袭击#xff0c; 发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷#xff1a; 虽然它的第一发炮弹能够到达任意的高度#xff0c;但是以后每一发炮弹都不能高于前一发的高度。 某天#xff0c; 雷达捕捉到敌国的…
第1题拦截导弹 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。 某天 雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段 所以只有一套系统 因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度数据是不大于 30000 的正整数) 计算这套系统最多能拦截多少导弹。 时间限制 1000 内存限制 65536 输入 第一行是一个整数 N(不超过 15) 表示导弹数。 第二行包含 N 个整数 为导弹依次飞来的高度(雷达给出的高度数据是不大于 30000的正整数) 。 输出 一个整数 表示最多能拦截的导弹数。 样例输入 8 389 207 155 300 299 170 158 65 样例输出 6 要解决拦截导弹的问题可以使用动态规划的方法。
以下是使用C语言实现的代码
#include stdio.h#define MAX_MISSILES 15int max(int a, int b) {return (a b) ? a : b;
}int missileInterception(int missiles[], int n) {int dp[MAX_MISSILES] {0};int maxInterceptions 0;for (int i 0; i n; i) {dp[i] 1;for (int j 0; j i; j) {if (missiles[i] missiles[j]) {dp[i] max(dp[i], dp[j] 1);}}maxInterceptions max(maxInterceptions, dp[i]);}return maxInterceptions;
}int main() {int n;scanf(%d, n);int missiles[MAX_MISSILES];for (int i 0; i n; i) {scanf(%d, missiles[i]);}int maxInterceptions missileInterception(missiles, n);printf(%d\n, maxInterceptions);return 0;
}该代码使用一个一维数组dp来保存状态其中dp[i]表示以第i个导弹为结尾的最大拦截导弹数。
首先初始化dp数组的所有元素为1表示每个导弹都可以单独拦截。然后遍历导弹数组对于每个导弹missiles[i]在之前的导弹中查找高度小于等于当前导弹的导弹missiles[j]如果找到则更新dp[i]为dp[j]1表示以导弹missiles[i]结尾的最大拦截导弹数。最后找到dp数组中的最大值即为所求的最多能拦截的导弹数。
第2题神奇的数列 一个正整数数列 可以将它切割成若干个数据段 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于 每次切除一个数据段后该数据段前后的元素自动连接在一起成为邻居。 例如从数列“2 8 9 77 6 9 4” 中切除数据段“7 7 ” 后 余下的元素会构成数列“2 8 9 6 94” 请问若要将该数列切割成若干个数据段 则至少会切出来几个数据段? 样例 按下列顺序切割数列“2 8 9 7 7 6 9 4” 只要切割成 6 段 切割出“7 7” 余下 “2 8 9 6 9 4” 切割出 “6” 余下 “2 8 9 9 4” 切割出 “9 9” 余下 “2 8 4” 切割出 “2” 余下 “8 4” 切割出 “8” 余下 “4” 时间限制 1000 内存限制 65536 输入 第一行是一个整数 示共有多少组测试数据。 每组测试数据的输入包括两行 第一行是整数 N, N200,表示数列的长度 第二行是 N 个正整数。 输出 每个测试案例的输出占一行 是一个整数。 格式是 Case n: x n 是测试数据组编号 x 是答案 样例输入 2 8 2 8 9 7 7 6 9 4 16 2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9 样例输出 Case 1: 6 Case 2: 11 要解决神奇的数列问题可以使用贪心算法。
以下是使用C语言实现的代码
#include stdio.h#define MAX_LENGTH 200int min(int a, int b) {return (a b) ? a : b;
}int countSegments(int sequence[], int n) {int segments 1;for (int i 1; i n; i) {if (sequence[i] ! sequence[i - 1]) {segments;}}return segments;
}int main() {int t;scanf(%d, t);for (int i 1; i t; i) {int n;scanf(%d, n);int sequence[MAX_LENGTH];for (int j 0; j n; j) {scanf(%d, sequence[j]);}int segments countSegments(sequence, n);printf(Case %d: %d\n, i, segments);}return 0;
}该代码使用一个循环遍历数列对于每个数列元素sequence[i]如果它与前一个元素sequence[i-1]不相等则将段数segments加1。最后segments的值即为所求的切割数据段的数量。
第3题硬币 宇航员 Bob 有一天来到火星上 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了 一共有 n 种 每种只有一个 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物 想买来送给朋友 Alice 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零 只接受恰好 X 元。 时间限制 1000 内存限制 262144 输入 第一行包含两个正整数 n 和 x。 (1 n 200, 1 x 10000) 第二行从小到大为 n 个正整数 a1, a2, a3 … an (1 ai 10000) 输出 第一行是一个整数 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值(从小到大排列) 。 样例输入 5 18 1 2 3 5 10 样例输出 2 5 10 提示 输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币 则第一行输出 0 第二行输出空行。 要解决硬币问题可以使用动态规划的方法。
以下是使用C语言实现的代码
#include stdio.h
#include stdbool.h#define MAX_COINS 200
#define MAX_AMOUNT 10000bool dp[MAX_AMOUNT 1] {false};void findCoins(int coins[], int n, int amount) {dp[0] true;for (int i 0; i n; i) {for (int j amount; j coins[i]; j--) {if (dp[j - coins[i]]) {dp[j] true;}}}
}int main() {int n, amount;scanf(%d %d, n, amount);int coins[MAX_COINS];for (int i 0; i n; i) {scanf(%d, coins[i]);}findCoins(coins, n, amount);int count 0;for (int i 1; i amount; i) {if (dp[i]) {count;}}printf(%d\n, count);for (int i 1; i amount; i) {if (dp[i]) {printf(%d , i);}}printf(\n);return 0;
}该代码使用一个布尔数组dp来保存状态其中dp[i]表示是否存在一种硬币组合可以凑出金额i。
首先将dp[0]设置为true表示金额为0时不需要使用任何硬币。然后遍历硬币数组coins对于每个硬币coins[i]从amount向前遍历到coins[i]如果存在一种硬币组合可以凑出金额j-coins[i]则说明存在一种硬币组合可以凑出金额j将dp[j]设置为true。
最后统计dp数组中为true的元素个数即为必须被使用的硬币种类的数量。并输出这些必须使用的硬币面值。
第4题公共子序列 我们称序列 Z z1, z2, …, zk 是序列 X x1, x2, …, xm 的子序列当且仅当存在 严格上升 的序列 i1, i2, …, ik 使得对 j 1, 2, … ,k, 有xij zj。 比如 Z a, b, f, c 是 X a, b, c, f, b, c 的子序列。 现在给出两个序列 X 和 Y 你的任务是找到 X 和 Y 的最大公共子序列 也就是说要找到一个最长的序列 Z 使得 Z 既是 X 的子序列也是 Y 的子序列。 时间限制 3000 内存限制 65536 输入 输入包括多组测试数据。 每组数据包括一行 给出两个长度不超过200 的字符串 表示两个序列。 两个字符串之间由若干个空格隔开。 输出 对每组输入数据 输出一行 给出两个序列的最大公共子序列的长度。 样例输入 abcfbc abfcab programming contest abcd mnp 样例输出 4 2 0 要解决最大公共子序列问题可以使用动态规划的方法。
以下是使用C语言实现的代码
#include stdio.h
#include string.h#define MAX_LENGTH 200int max(int a, int b) {return (a b) ? a : b;
}int longestCommonSubsequence(char X[], char Y[], int m, int n) {int dp[MAX_LENGTH 1][MAX_LENGTH 1];for (int i 0; i m; i) {for (int j 0; j n; j) {if (i 0 || j 0) {dp[i][j] 0;} else if (X[i - 1] Y[j - 1]) {dp[i][j] dp[i - 1][j - 1] 1;} else {dp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];
}int main() {char X[MAX_LENGTH 1];char Y[MAX_LENGTH 1];while (scanf(%s %s, X, Y) ! EOF) {int m strlen(X);int n strlen(Y);int length longestCommonSubsequence(X, Y, m, n);printf(%d\n, length);}return 0;
}该代码使用一个二维数组dp来保存状态其中dp[i][j]表示序列X的前i个字符和序列Y的前j个字符的最大公共子序列的长度。
首先将dp[i][0]和dp[0][j]都设置为0表示当一个序列的长度为0时最大公共子序列的长度为0。
然后从1到m和1到n的循环遍历如果X[i-1]等于Y[j-1]则说明X的第i个字符和Y的第j个字符相同将dp[i][j]设置为dp[i-1][j-1]的值加1表示当前字符可以加入最大公共子序列。
如果X[i-1]不等于Y[j-1]则说明X的第i个字符和Y的第j个字符不相同需要在X的前i-1个字符和Y的前j个字符的最大公共子序列和X的前i个字符和Y的前j-1个字符的最大公共子序列之间取最大值即dp[i-1][j]和dp[i][j-1]的最大值。
最后dp[m][n]即为X和Y的最大公共子序列的长度。
