上机编程题目.doc

删数问题 【题目描述】 键盘输人一个高精度的正整数N（=240位），去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数．编程对给定的N和s，寻找一种方案使得剩下的数字组成的新数最小。 输入数据： N 一个高精度的正整数 s 要删除N中数字个数 输出数据要求： 最后剩下的最小数 输入输出样例： 输入： 135246 4 输出： 12 取数游戏 【题目描述】 给出2n(n=100)个自然数（数小于等于30000）。游戏双方分别为A方（计算机方）和B方（对弈的人）。只允许从数列两端取数。A先取，然后双方依次轮流取数。取完时，谁取的数字总和最大为取胜方；若双方和相等，属于A胜。试问A方是否有必胜的策略。 输入数据： N 2*N个自然数 输出数据要求： 共2N+2行，其中前2*N行为游戏经过。每2行分别为A方所取的数和B方所取的数（L/R----左端或右端）max，最小的为min，则该数列的极差定义为M=max-min。 编程任务：对于给定的数列，编程计算出极差M。 输入数据： N个正整数做成的一个数列 输出数据要求： 共3行，其中第一行显示某操作方式得到最大值max，第二行显示某操作方式得到的最小值min,最后1行显示所计算得出的极差M=max-min。 输入输出样例： 输入： 2 1 4 3 输出： max=41 min=28 M=max-min=13 4. 登山机器人问题 【题目描述】 登山机器人是一个极富挑战性的高技术密集型科学研究项目，它为研究发展多智能体系统和多机器人之间的合作与对抗提供了生动的研究模型。登山机器人可能携带有限的能量。在登山过程中，登山机器人需要消耗一定的能量，连续攀登的路程越长，其攀登速度就越慢。在对m种不同类型的机器人做性能测试时，测定出每个机器人连续攀登1米，2米，……，k米时所用的时间。现在要对这m个机器人做综合性能测试，举行机器人接力攀登演习，攀登的总高度为n米，规定每个机器人至少攀登1米，最多攀登k米，而且每个机器人攀登的高度必须是整数，即只能在整米处接力。安排每个机器人攀登适当的高度，使完成接力攀登用的时间最短。 输入数据： 第1行是正整数m，n和s分别表示机器人的个数、每个机器人最多可以攀登的高度和接力攀登的总高度。接下来的m行中，每行有n个正整数，分别表示机器人连续攀登1，2，…，n米所用的时间。 输出登山机器人接力到达终点的最短攀登时间。 5 10 25 24 49 75 102 130 160 192 230 270 320 23 48 75 103 139 181 224 274 344 415 22 49 80 180 280 380 480 580 680 780 25 51 80 120 170 220 270 320 370 420 23 49 79 118 158 200 250 300 350 400 输出： 2135 5. 汽车加油问题 【题目描述】 一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法使沿途加油次数最少。对于给定的n (n = 5000 )和k (k = 1000) 个加油站位置，编程计算最少加油次数。第一行有2 个正整数n 和k，表示汽车加满油后可行驶n 公里，且旅途中有k 个加油站。接下来的1 行中，有k+1 个整数，表示第k 个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。 输出。 7 7??????????????????????? ????? 1 2 3 4 5 1 6 6 输出： 4 6.0-1背包问题 【题目描述】 给定一个载重量为weight的背包，n个物品，其重量分别为w[i]，价值分别为p[i]，1=i=n，物体或者被装入背包，或者不被装入背包，只有两种选择。要求把物品装入背包，并使包内物品价值最大。（要求任选两种贪心策略） 输入数据： 第一行第一行第一行第一行贪心算法专题实例解析 【例1】删数问题 Description 键盘输人个高精度的正整数N，去掉其中任意s个数字后剩下的数字按原左右次序组成个新的正整数．编程对给定的N和s，寻找一种方案使得剩下的数字组成的新数最小一位管理项目的经理想要确定每个月需要的工人,他当然知道每月所需的最少工人数.当他雇佣或解雇一个工人,会有一些额外支出.一旦一个工人被,即使他不工作,他也将得到工资.这经理知道雇佣一个工人的费用,解雇一个工人的费用和一个