发布时间 : 星期一 文章C语言程序设计大赛资料更新完毕开始阅读1f9997d476a20029bd642d1b
38.09 1 2
9． 皇宫看守
太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；某些宫殿间可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。
请你编程计算帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。
输入数据：输入数据由文件名为intput.txt的文本文件提供。输入文件中数据表示一棵树，描述如下：
第1行 n，表示树中结点的数目。
第2行至第n+1行，每行描述每个宫殿结点信息，依次为：该宫殿结点标号i（0 对于一个n（0 < n <= 1500）个结点的树，结点标号在1到n之间，且标号不重复。 输出数据：输出到output.txt文件中。输出文件仅包含一个数，为所求的最少的经费。 如右图的输入数据示例： Sample Input 6 1 30 3 2 3 4 2 16 2 5 6 3 5 0 4 4 0 5 11 0 6 5 0 Sample Output 25 10． 游戏室问题 有一个游戏室里有多个游戏室，并且这每个游戏室里还有多个游戏室，每个游戏室里面还有游戏室，依此类推。进入每个游戏室都可得到一定的快乐，每个游戏室的门票价格都大于等于0，都有一个快乐值，并且只有进入了一个游戏室，才可以进入它内部的游戏室，小明现在有n元钱，问最大能得到多少的快乐。 11． *基因问题 已知两个基因序列如s：AGTAGT；t：ATTAG。现要你给序列中增加一些空格后，首先使得两个序列的长度相等，其次两个串对应符号匹配得到的值最大。基因只有四种分别用A、G、C、T表示，匹配中不允许两个空格相对应，任意两符号的匹配值由下表给出： A G C T ︺ A 5 -2 -1 -2 -4 G -2 5 -4 -3 -2 C -1 -4 5 -5 -1 T -2 -3 -5 5 -2 ︺ -4 -2 -1 -2 提示：定义问题l[i][j]为取第一个序列的前i项，和第二个序列的前j项，这两个序列加空格匹配的最大值。它的最优值与三个子问题有关，l[i-1][j-1]、l[i][j-1]、l[i-1][j]。 建立递归公式如下： 其中m[0][t[j]表示表中空格和t[j]匹配的对应值。 思考：本问题的初始化。 25 12． *田忌赛马 田忌与齐王赛马，双方各有n匹马参赛（n<=100），每场比赛赌注为1两黄金，现已知齐王与田忌的每匹马的速度，并且齐王肯定是按马的速度从快到慢出场，现要你写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。 分析：先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。本问题应用的算法是动态规划和贪心算法相结合解决的。从两人的最弱的马入手： 若田忌的马快，就让这两匹马比赛； 若田忌的马慢，干脆就让他对付齐王最快的马； 若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。 定义子问题：l(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。 则： 程序具体实现时，为了适合c数据从0开始，稍加变动，定义子问题：l(i，j)为齐王的从第i匹马开始到第i＋j匹马共j+1匹马与田忌的最快的j+1匹马比赛，田忌所获得的最大收益。初始化时：l[i][0]表示齐王的第i匹马与田忌最快的马比赛的结果。 程序如下： #include int n,a[100],b[100],l[100][100]; int main() { int i,j; readdata(); init(); for(i=n-2;i>=0;i--) for(j=1;j void readdata() { int i; scanf(\ for(i=0;i void init() { int i; // qsort(a,n); //略 for(i=0;i 26 else if(a[i]==b[0]) l[i][0]=0; else l[i][0]=-1; } } 实验五：贪心算法和随机算法 1.背包问题 有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 2.照亮的山景 在一片山的上空，高度为T处有N个处于不同位置的灯泡，如图。如果山的边界上某一点于某灯i的连线不经过山的其它点，我们称灯i可以照亮该点。开尽量少的灯，使得整个山景都被照亮。山被表示成有m个转折点的折线。 提示：照亮整个山景相当于照亮每一个转折点。 3.搬桌子问题 某教学大楼一层有n个教室，从左到右依次编号为1、2、?、n。现在要把一些课桌从某些教室搬到另外一些教室，每张桌子都是从编号较小的教室搬到编号较大的教室，每一趟，都是从左到右走，搬完一张课桌后，可以继续从当前位置或往右走搬另一张桌子。输入数据：先输入n、m，然后紧接着m行输入这m张要搬课桌的起始教室和目标教室。输出数据：最少需要跑几趟。 Sample Input 10 5 1 3 3 9 4 6 6 10 7 8 Sample Output 3 分析：贪心算法，把课桌按起点从小到大排序，每次都是搬离当前位置最近的课桌。 程序如下： #include 27 while(num 附录：逻辑推理问题 对于较难的逻辑推理问题，看上去难于解决，不知道该从哪里下手时，认真的读题从最简单最特殊的情况入手 1． 月薪30K的面试题 小明和小强都是张老师的学生，张老师的生日是m月n日，2人都知道张老师的生日是下列10组中的一天，张老师把m值告诉了小明，把n值告诉了小强，张老师问他们知道他的生日是那一天吗？ 3月4日 3月5日 3月8日 6月4日 6月7日 9月1日 9月5日 12月1日 12月2日 12月8日 小明说：如果我不知道的话，小强肯定也不知道 小强说：本来我也不知道，但是现在我知道了 小明说：哦，那我也知道了 提示：做西服有的需要几分钟，有的需要几百道工序。只要认真就能做好。 此题做对的人很少，不是因为题目太难，而是因为不够认真。 2． 微软面试题 一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。然而所有主人和他们的狗都不能够离开自己的房子，主人与主人之间也不能通过任何方式进行沟通，他们能做的只是通过窗户观察别人家的狗是否生病从而判断自己的狗病否。（就是说，每个主人只能看出其他 49家的狗是不是生病，单独看自己的狗是看不出来的）第一天没有枪声，第二天还是没有枪声，第三天传出一阵枪声，问有多少条狗被枪杀。 提示：上面的大字 3． 海盗分金块问题 海盗，大家听说过吧。这是一帮亡命之徒，在海上抢人钱财，夺人性 命，干的是刀头上舔血的营生。在我们的印象中，他们一般都瞎一只 眼，用条黑布或者讲究点的用个黑皮眼罩把坏眼遮上。他们还有在地 下埋宝的好习惯，而且总要画上一张藏宝图，以方便后人掘取。不过 大家是否知道，他们是世界上最民主的团体。参加海盗的都是桀骜不 驯的汉子，是不愿听人命令的，船上平时一切事都由投票解决。船长 的唯一特权，是有自己的一套餐具--可是在他不用时，其他海盗是 可以借来用的。船上的唯一惩罚，就是被丢到海里去喂鱼。 现在船上有若干个海盗，要分抢来的若干枚金币。自然，这样的问题 他们是由投票来解决的。投票的规则如下：先由最凶猛的海盗来提出 分配方案，然后大家一人一票表决，如果有50%或以上的海盗同意这个 方案，那么就以此方案分配，如果少于50%的海盗同意，那么这个提出 方案的海盗就将被丢到海里去喂鱼，然后由剩下的海盗中最凶猛的那 个海盗提出方案，依此类推。 我们先要对海盗们作一些假设。 28