acm,解题报告.docVIP

acm,解题报告 acm解题报告 HUNAN UNIVERSITY ACM解题报告 （选修课考核） 学生姓名 学生学号20110801315专业班级计算机科学与技术3班 第一题： 题目来源：HOJ 1007、GCD 最大公约数 Problem Description 求两个数最大公约数和最小公倍数 Input 每行两个整数N,M (0N,M10000) Output 每行两个数,分别为这两个数的最大公约数和最小公倍数. Sample Input 3 6 1 3 Sample Output 3 6 1 3 分析：求最大公约数可以用辗转相除法。 代码： #include cstdio int gcd(int x, int y){return y==0 ? x : gcd(y, x%y);} int main() { int a, b; while(scanf(%d%d, amp;a, amp;b)!=EOF) { int d= gcd(a, b); printf(%d %d\n, d, a/d*b); } } 第二题： 题目来源：POJ 1011 题目描述： Sticks Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Time Limit:5S Memory Limit:10000K INPUT：The input file contains blocks of 2 lines. The first line contains the number of sticks parts after cutting. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero. OUTPUT：The output file contains the smallest possible length of original sticks, one per line. 分析： 基本思路：从小到大，逐个尝试可能的长度。 设已知的n根短棍的长度分别是： l1,l2,?,ln 现在的问题就是：要判断这n根短棍是否可以组成m根长为length的长棍。 解决方案：逐个填充长棍，填完一根长棍，再填下一根。 这个想法是很简单的，我们可以看一下具体的实现： int ok=0;//全局变量，用来表示填充是否成功 void solve(int x) {//填充第x根长棍 if (x m) { ok = 1; printf(%d\n, length); return; } int i; for (i = 1;i = n;i++) if (!used[i]) break; used[i] = 1; search(x,stick[i],i);/*有若干个长棍都没有被填充过，如果现在将li填入其中一个作过尝试，就不用再填到别的长棍中作尝试了。*/ used[i] = 0; } void search(int num,int now,int next) { if (ok) return; if (now == length) { solve(num + 1); return; } for (int i = next + 1;i = n;i++) if (!used[i]) if(stick[i] + now = len) { used[i] = 1;search(num,now + stick[i],i);used[i] = 0; if (ok) return; //此步和我的第三个优化类似 if (stick[i] == length - now) return; } } 总结： 1.深度优先有哪些信誉好的足球投注网站的顺序（方式）对于效率有很大影响（此问题中对应于两种不同的思路） 2.优化剪枝对于深度优先有哪些信誉好的足球投注网站效率的提到也有极大的作用。 第三题： 题目来源:POJ 题目简介： 一个人要将消息传递给一个部门的所有的.这个人自己只传给他从这个部门中所选的一个人.然后消息从所选的人开始传播直到所有的人都知道此消息. 规则: 1.发送规则:一个人收到消息后便开始向所有