用迭代法求两个数的最大公约数和最小公倍数.doc

吉林化工学院 化工与材料工程学院用迭代法求两个数的最大公约数和最小公倍数化工09110605 摘要：迭代法是一种循环控制语句和循环结构程序的设计方法。在计算机解决问题的时候，总希望从复杂的问题中找到规律，并归结为简单问题的重复，发挥其擅长重复运算的特点，让它重复执行一组语句，直到满足给定条件为止。因此， c语言提供了重复操作的语句，由这些语句构成的程序称为循环结构。本文就是采用迭代法，利用c语言中提供的重复语句，求得两个数的最大公约数和最小公倍数。关键词：循环语句；循环结构；迭代法；最大公约数和最小公倍数Iterative Method with the greatest common divisor and least common multiple of two numbersChemical 09110605 WANG MengAbstract: The iterative method is a loop control statement and loop structure design process. When the computer to solve the problem, hoping to find from the law of complex issues and boil down to a simple repetition of questions, to play the good characteristics of repeat operation, let it repeat a set of statements until the date that satisfies the given conditions. Therefore, c language repeat the statement provided by these statements constitute the program is called loop structure. This is the iterative method, using c language provided by the repeated statement, obtained the greatest common divisor and least common multiple of two numbers.Key words: loop; loop structure; iteration; greatest common divisor and least common multiple31、前言：算法设计是程序设计的关键，也是程序设计的难点。选择算法的标准首先是算法的正确性、可靠性和易理解性；其次就是算法所需要的存储空间要小、运算速度要快等。迭代法也称为辗转法，是一种不断用变量的原值推导出新值的方法。用迭代法有三个要点：一是确定迭代变量，在可以用迭代法解决问题中，必须存在一个或多个直接或间接地不断由原值递推出的新值的变量，这个变量就是迭代变量；二是建立迭代关系，即如何从变量的前一个值推出下一个值；三是迭代结束条件，即需要迭代的次数无法确定，直到满足某种条件结束。所以通常采用条件控制，用while语句或dowhile语句实现。解决这种求得两数最大公约数和最小公倍数的问题，还可以用调用函数的方法，即编写两个函数，分别求两个整数的最大公约数和最小公倍数。然后用主函数进行调用这两个函数，在这种方法中主函数总是包括如下内容： （1）输入数据（如果需要）。 （2）调用函数完成要求的功能。 （3）输出结果。 本文是用迭代法解决该问题的。2、原理： 求两个数x、y的最大公约数和最小公倍数。 最小公倍数=x*y/最大公约数；所以关键就是求得最大公约数。本文采用“辗 转相除法”求最大公约数。 辗转相除法就是重复做：求a除以b的余数p；a等于原来的b；b等于p，直到p等于0时，a就是最大公约数。其中迭代变量是a和b；迭代关系是a=b，b=p；迭代结束条件是p等于0。2、1 NS图： main()变量初始化输入&x，&ya=x;b=y; do p=a%b;a=b;b=p;while(p!=0) 1 0 输出结果2、2 程序代码： void main() int x,y,a,b,p; printf(x,y=);scanf(%d,%d,&x,&y); a=x;b=y; do p=a%b; a=b; b=p; while(p!=0); printf(%d,%dn,a,x*y/a); 程序测试 ： x，y=18，12(回车) 6，363、算法设计： 输入x、y，并分别送到a、b中求最大公约数（保留x，y求最小公倍数）。 重复执行： p=a%b； a=b； b=p；，直到p=0，a即为最大公约数。 最小公倍数=x*y/a。4、结论： 迭代法是求得两个数最大公约数和最小公倍数的常用程序设计方法，它的程序编译较为简单，完成要求效率较高。建议遇到求解相关问题时，优先考虑该种方法。其次是运用函数互相调用的方法（前言中提及到的），用该种方法时最好是编程人手多，每个人分别编辑实现功能不同的函数模块，最后将各函数吻合到一起归为一个程序，从而解决问题。如果单人独自完成该程序的调试，那么会容易出现错误