C语言常用算法.

C语言常用算法共100页第2页一、数值计算1、累加2、累乘（阶乘）3、交换4、最大/最小值5、数位拆解6、数组移动7、级数计算8、素数判断二、数据查找1、顺序查找2、穷举查找三、排序算法1、冒泡排序2、选择排序3、插入排序4、归并排序C语言常用算法共100页第3页1、累加累加算法的要领是形如“s=s+A”的累加式，此式必须出现在循环中才能被反复执行，从而实现累加功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为0。一、数值计算C语言常用算法共100页第4页例g-1、求1+2+3+……+100的和。main(){inti,s;s=0;i=1;while(i=100){s=s+i;i=i+1;}printf(“s=%d\n,s);}【解析】程序中红字部分为累加式的典型形式，赋值号左右都出现的变量称为累加器，其中“i=i+1”为特殊的累加式，每次累加的值为1，这样的累加器又称为计数器。main(){inti,s;s=0;i=1;for(i=1;i=100;i++)s=s+i;printf(“s=%d\n,s);}C语言常用算法共100页第5页2、累乘、阶乘累乘算法的要领是形如“s=s*A”的累乘式，此式必须出现在循环中才能被反复执行，从而实现累乘功能。“A”通常是有规律变化的表达式，s在进入循环前必须获得合适的初值，通常为1。C语言常用算法共100页第6页例g-2、求10！【分析】10！=1×2×3×……×10main(){inti;longs;s=1;i=1;while(i=10){s=s*i;i=i+1;}printf(1*2*3*...*10=%ld\n,s);}C语言常用算法共100页第7页3、交换两量交换借助第三者。如同交换两个瓶子里的墨水，必须借助第三个空瓶子。例g-3、任意读入两个整数，将二者的值交换后输出。main(){inta,b,t;scanf(%d%d,&a,&b);printf(%d,%d\n,a,b);t=a;a=b;b=t;printf(%d,%d\n,a,b);}【解析】程序中加粗部分为算法的核心，其中t为中间变量，起到“空瓶子”的作用。注意：三句赋值语句赋值号左右的各量之间的关系！C语言常用算法共100页第8页【应用】例g-4、任意读入三个整数，然后按从小到大的顺序输出。例C12_102main(){inta,b,c,t;scanf(%d%d%d,&a,&b,&c);if(ab){t=a;a=b;b=t;}if(ac){t=a;a=c;c=t;}if(bc){t=b;b=c;c=t;}printf(%d,%d,%d\n,a,b,c);}C语言常用算法共100页第9页4、求最大值/最小值【例g-5】用数组a存放随机产生的20个整数，然后输出其最大值和最小值。#defineN20main(){inta[N],i,max,min;for(i=0;iN;i++)a[i]=rand();max=a[0];min=a[0];for(i=1;iN;i++){if(a[i]max)max=a[i];if(a[i]min)min=a[i];}printf(max=%d,min=%d\n,max,min);}C语言常用算法共100页第10页【例g-6】修改上例，输出最大/最小值的数组元素的下标。#defineN20main(){inta[N],i,max,min;for(i=0;iN;i++)a[i]=rand();max=0;min=0;for(i=1;iN;i++){if(a[i]a[max])max=i;if(a[i]a[min])min=i;}printf(max=a[%d]=%d,min=a[%d]=%d\n,max,a[max],min,a[min]);}C语言常用算法共100页第11页5、数位拆解原理：整除运算、模运算如：48/10=4596/100=51234/1000=148%10=8596%100=96596%10=6五位整数N的数位拆解：个位：N%10十位：N/10%10百分位：N/100%10千分位：N/1000%10万位：N/10000%10或N/10000如，拆解65824的数位：个位：65824%10=4十位：65824/10%10=2百分位：65824/100%10=8千分位：65824/1000%10=5万位：65824/10000%10=6C语言常用算法共100页第12页【例g-7】输出一个任意整数的各个位数。#defineN10main(){inta[N],i=0;longx;scanf(%ld,&x);while(x0L){a[i]=x%10;x/=10;i++;}for(i--;i=0;i--)printf(%d,a[i]);}C语言常用算法共100页第13页【例g-8】用随机函数产生100个[0，99]范围内的随机整数，统计个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数并打印出来。【分析】用数组a[100]存放产生的确100个随机整数，数组x[10]来存放个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数。即个位是1的个数存放在x[1]中，个位是2的个数存放在x[2]中，……个位是0的个数存放在x[10]。C语言常用算法共100页第14页voidmain(){inta[101],x[11],i,p;for(i=0;i=11;i++)x[i]=0;for(i=1;i=100;i++){/*产生0~100之间的随机数*/a[i]=rand()%100;printf(%4d,a[i]);if(i%10==0)printf(n);}for(i=1;i=100;i++){/*获取个位数为数组x的下标*/p=a[i]%10;if(p==0)p=10;x[p]=x[p]+1;}for(i=1;i=10;i++){p=i;if(i==10)p=0;printf(%d,%d\n,p,x[i]);}printf(\n);}C语言常用算法共100页第15页例，判断水仙花数。C语言常用算法共100页第16页6、数组移动算法核心：前移：a[i-1]=a[i]后移：a[i+1]=a[i]【例g-9】#defineN10main(){inta[N],i=0;/*随机赋值*/for(i=0;iN;i++)a[i]=rand();for(i=0;iN;i++)printf(%d,a[i]);printf(\n);/*数组前移*/for(i=1;iN;i++)a[i-1]=a[i];for(i=0;iN;i++)printf(%d,a[i]);printf(\n);/*数组后移*/for(i=N-1;i0;i--)a[i]=a[i-1];for(i=0;iN;i++)printf(%d,a[i]);printf(\n);}C语言常用算法共100页第17页7、级数（数列）计算级数计算的关键是“描述出通项”，而通项的描述法有两种：一为直接法、二为间接法又称递推法。直接法的要领是：利用项次直接写出通项式；递推法的要领是：利用前一个（或多个）通项写出后一个通项。可以用直接法描述通项的级数计算例子有：（1）1+2+3+4+5+……（2）1+1/2+1/3+1/4+1/5+……等等。可以用间接法描述通项的级数计算例子有：（1）1+1/2+2/3+3/5+5/8+8/13+……（2）1+1/2!+1/3!+1/4!+1/5!+……等等。C语言常用算法共100页第18页main(){floats;inti;s=0.0;for(i=1;i=100;i++)s=s+1.0/i;printf(1+1/2+1/3+...+1/100=%f\n,s);}（1）直接法求通项例g-10、求1+1/2+1/3+1/4+1/5+……+1/100的和。【解析】程序中红字部分就是利用项次i的倒数直接描述出每一项，并进行累加。【注意】因为i是整数，故分子必须写成1.0的形式！C语言常用算法共100页第19页例g-11、计算下列式子前20项的和：1+1/2+2/3+3/5+5/8+8/13+……。【分析】此题后项的分子是前项的分母，后项的分母是前项分子分母之和。（2）间接法求通项（即递推法）main(){floats,fz,fm,t,fz1;inti;s=1;fz=1;fm=2;t=fz/fm;for(i=2;i=20;i++){s=s+t;fz1=fz;fz=fm;fm=fz1+fm;t=fz/fm;}printf(1+1/2+2/3+...=%f\n,s);}C语言常用算法共100页第20页只能被1或本身整除的数称为素数。基本思想：把m作为被除数，将2~sqrt(m)作为除数，如果都除不尽，m就是素数，否则就不是。8、判断素数voidmain(){intm,i,k;printf(pleaseinputanumber:n);scanf(%d,&m);k=sqrt(m);for(i=2;ik;i++)if(m%i==0)break;if(i=k)printf(该数是素数);elseprintf(该数不是素数);}【例g-12】C语言常用算法共100页第21页intprime(intm){inti,k;k=sqrt(m);for(i=2;ik;i++)if(m%i==0)return0;return1;}将其写成一函数,若为素数返回1，不是则返回0。main(){inti,k;scanf(“%d”,&n);if(prime(n)==1)printf(“是素数。”);elseprintf(“非素数。”);}C语言常用算法共100页第22页1、顺序查找（即线性查找）思路：将待查找的量与数组中的每一个元素进行比较，若有一个元素与之相等则找到；若没有一个元素与之相等则找不到。二、数据查找C语言常用算法共100页第23页#defineN10main(){inta[N],i,x;for(i=0;iN;i++)scanf(%d,&a[i]);scanf(%d,&x);for(i=0;iN;i++)if(a[i]==x)break;if(iN)printf(Found!\n);elseprintf(Notfound!\n);}【例g-13】任意读入10个数存放到数组a中，然后读入待查找数值，存放到x中，判断a中有无与x等值的数。C语言常用算法共100页第24页也称为“枚举法”，即将可能出现的每一种情况一一测试，判断是否满足条件，一般采用循环来实现。这是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。2、穷举C语言常用算法共100页第25页main(){intx,g,s,b;for(x=100;x=999;x++){g=x;s=x/10;b=x/100;if(b*b*b+s*s*s+g*g*g==x)printf(%d\n,x);}}【例g-14】用穷举法输出所有的水仙花数（即这样的三位正整数：其每位数位上的数字的立方和与该数相等。比如：13+53+33=153。C语言常用算法共100页第26页main(){inti,j,k;printf(5元1元5角n);for(i=1;i=20;i++)for(j=1;j=100-i;j++){k=100-i-j;if(5*i+1*j+0.5*k==100)printf(%3d%3d%3dn,i,j,k);}}例g-15：将一张面值为100元的人民币等值换成100张5元、1元和0.5元的零钞，要求每种零钞不少于1张，问有哪几种组合？C语言常用算法共100页第27页1、冒泡排序（起泡排序）三、排序算法基本思想：假设要对含有n个数的序列进行升序排列，冒泡排序算法步骤是：1）有n个数（存放在数组a(n)中），第一趟将每相邻两个数比较，小的调到前头，经n-1次两两相邻比较后，最大的数已“沉底”，放在