Question

关于算法分析与设计的题目,请各位高高手帮帮忙.小女子感激不尽

19、 [找出伪币]给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。利用一台仪器比较两组硬币重量的仪器, 可以知道两组硬币的重量是否相同。设计一个算法，求出解决此问题的具有最少比较次数和比较方法。
20、 考虑上题的伪币问题。假设把条件“伪币比真币轻”改为“伪币与真币的重量不同”，同样假定袋中有n 个硬币。给出相应算法。该算法可输出信息“不存在伪币”或找出伪币，算法应递归地将大的问题划分成两个较小的问题。
21、 给出一个n 顶点网络（有向或无向），要求找出一个包含所有n 个顶点的具有最小耗费的环路。任何一个包含网络中所有n 个顶点的环路被称作一个旅行（t o u r）。在旅行商问题中，设计一个算法，找到一条最小耗费的旅行。
22、 键盘输入一个仅由小写字母组成的字符串，输出以该串中任取M 个字母的所有排列及排列总数。输入数据均不需判错。
23、 （组合问题）找出从自然数1，2，…，n中任取r个不同数的所有排列。
24、 写一个算法，求出一个二叉树的深度与最大宽度。
25、 写一个在一百万个数字中求十个最大的数的算法
26、 写出先根遍历的非递归算法。
28、 （旅行家的预算问题）一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市，给定两个城市间的距离d1，汽车油箱的容量是c，每升汽油能行驶的距离d2，出发时每升汽油的价格是p，沿途加油站数为n（可为0），油站i离出发点的距离是di，每升汽油的价格是pi。设计一个算法，给出旅行家的预算问题的最少花费的加油方案。计算结果四舍五入保留小数点后两位，若无法到达目的地输出“No answer" 。
29、 （删数问题） 键盘输入一个高精度的正整数N，去掉其中任意S个数字后剩下的数字按左右次序组成一个新的正整数。对给定的N和S，寻找一种删数规则使得剩下得数字组成的新数最小。
30、 考察机器调度问题。假定仅有一台机器可用，选择最大数量的任务在这台机器上执行。解决这种任务选择问题的贪婪算法可按步骤选择任务，每步选择一个任务，其贪婪准则如下：从剩下的任务中选择具有最小的完成时间且不会与现有任务重叠的任务。实现该算法，其复杂性应为O(nlogn)。（提示：采用一个完成时间的最小堆）
31、 编写一个求从图G中顶点s到顶点i的一条最短路径。算法的复杂性是多少？

Answer 1

恩，这些题挺好的，留个名字等着天上掉馅饼。

Answer 2

数据结构没学好吧。