c程序设计的常用算法

《c程序设计的常用算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、C程序设计的常用算法一、计数、求和、求阶乘等简单算法此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。例1:求阶乘。下列程序用于求n的阶乘，在累乘之前,一定要将用于存放乘积的变量的值初始化为1；注意阶乘的数字比较大，所以函数类型最好使用长整型。longfunc(intn){inti;longt=1;for(i=2;i<=n;i++)t*=i;returnt;}例2:整数拆分问题。（1）确定3位数（2）不确定数字位数，利用数组存储数字利用变量存储数字数组定义足够大intsplit(intn,inta[

2、10]）{inti;for(i=0;n!=0;i++){a[i]=n%10;n=n/10;}returni;/*返回数字个数*/}#defineN3a,b,c依次保存个十百位a=n%10;b=n/10%10;c=n/100%10;viodsplit(intn,inta[]）{inti;for(i=N-1;n!=0;i--){a[i]=n%10;n=n/10;}}例3:求整数的因子之和。注意：因子包括1和自身。longfactor(intn){inti;longsum=0;for(i=1;i<=n;i++)if(n%i==0)sum+=i;returnsum;}例4

3、:求回文数的函数（例如：456的回文数是654。）inthws(inta){intc=0;while(a>0){c=c*10+a%10;a/=10}return(c);}11二、求两个整数的最大公约数、最小公倍数分析：求最大公约数的算法为辗转相除法。(最小公倍数=两个整数之积/最大公约数)求最大公约数的算法步骤：(1)对于已知两数m，n，使得m>n；(2)m除以n得余数r；(3)若r=0，则n为求得的最大公约数，算法结束；否则执行(4)；(4)m←n，n←r，再重复执行(2)。例如:求m=14,n=6的最大公约数.mnr14%6=26%2=0三、判断素数（或求一定

4、范围之内的所有素数）只能被1和本身整除的正整数称为素数。基本思想：在判断数m是否为素数时，首先把m作为被除数，将2~sqrt(m)的所有数字依次作为除数，去除m，只要有一个数能将m整除，则m不是素数；否则，如果都除不尽，则m就是素数。四、求最值算法思想：以求最小值为例定义变量min用于存放当前所有找到的最小数，a为已知数组。算法步骤如下：1）在min中存放第1个数，比较从数组中的第二个元素开始。2）数组a中每个元素依次与min中的数组相比，小者放入min中。3）比较完数组的最后一个元素，算法结束。Min中数为所求。程序如下：五、排序问题1．选择法排序（升序）基本思

5、想：1）对有n个数的序列（存放在数组a[n]中），从中选出最小的数，与第1个数交换位置；2）除第1个数外，其余n-1个数中选最小的数，与第2个数交换位置；3）依次类推，选择了n-1次后，这个数列已按升序排列。2．冒泡法排序（升序）基本思想：(将相邻两个数比较，小的调到前头)1）有n个数（存放在数组a(n)中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数已“沉底”，放在最后一个位置，小数上升“浮起”；2）第二趟对余下的n-1个数（最大的数已“沉底”）按上法比较，经n-2次两两相邻比较后得次大的数；3）依次类推，n个数共进行n-1趟比较

6、，在第j趟中要进行n-j次两两比较。程序段如下3．合并法排序（将两个有序数组A、B合并成另一个有序的数组C，升序）基本思想：1）先在A、B数组中各取第一个元素进行比较，将小的元素放入C数组；2）取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完；113）将另一个数组剩余元素抄入C数组，合并排序完成。六、查找问题1．①顺序查找法（在一列数中查找某数x）基本思想：一列数放在数组a[0]~a[n-1]中，待查找的数放在x中，把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标，p初值为0，使x与

7、a[p]比较，如果x不等于a[p]，则使p=p+1，不断重复这个过程；一旦x等于a[p]则退出循环；另外，如果p大于数组长度，循环也应该停止。2．折半查找法（只能对有序数列进行查找）基本思想：设n个有序数（从小到大）存放在数组a[0]~a[n-1]中，要查找的数为x。用变量bot、top、mid分别表示查找数据范围的底部（数组下界）、顶部（数组的上界）和中间，mid=(top+bot)/2，折半查找的算法如下：（1）x=a(mid)，则已找到退出循环，否则进行下面的判断；（2）x

8、>a(mi