C语言常见算法

会计学1C语言常见算法(2)随机数函数random(intnum)用于产生[0,num)区间的一个整数。其包含在“stdlib.h”头文件中为了使每一次运行都产生一组新的随机数，可以使用randomize()函数是每次均产生不同的随机数。其包含在头文件“time.h”中(3)最大值与最小值我们需要将最大值（或最小值）保存在一个变量中（假设设变量名为max和min）,变量的初值我们一般设为数列中的第一个值。第1页/共41页例2：产生20个50到200之间的随机整数，并求出其中的素数、最大值和最小值。#include"stdlib.h"#include"time.h"main(){inta[20],b[20],max,min,k,i,j=0;

randomize();for(i=0;i<20;i++)a[i]=random(151)+50;产生20个[50,200]区间内的随机数第2页/共41页for(i=0;i<20;i++){for(k=2;k<a[i];k++)if(a[i]%k==0)break;

if(k==a[i]){b[j]=a[i];j++;}}for(i=0;i<j;i++)printf("%4d",b[i]);printf("\n");从a数组中找出其中的素数放在b数组中输出b数组中的各个元素

max=a[0];min=a[0];for(i=1;i<20;i++){if(a[i]>max)max=a[i];if(a[i]<min)min=a[i];}printf("max=%4d,min=%4d\n",max,min);}求出a数组中的最大值与最小值第3页/共41页二、求累加和的算法1循环条件次数控制（加多少项n,20,100)

用误差控制（直到某一项小于或大于一个数）使用终止标记2循环体求和求每一项：从前一项求出后一项、单独求每一项为下一项作准备3循环初值：设为0、设为第一项注意双重循环设初值的位置第4页/共41页4-16有一分数序列

的前20项之和main(){inti;floatf1=1,f2=1,f3,s=0;for(i=1;i<=20;i++){

f3=f1+f2;f1=f2;f2=f3;s=s+f2/f1;}printf("s=%f\n",s);}intf1,f2……s=s+1.0*f2/f1s=s+(float)f2/f1第5页/共41页三、迭代问题

这种方法是使用某个公式反复校正根的近似值，使之逐步精确化，最后得到满足精度要求的结果。第6页/共41页例：用牛顿迭代法求方程在1.5附近的根（精度为10-5）

2x3-4x2+3x-6=0

迭代公式为:x=x0-f/f1(f1为方程的导数公式)#include"math.h"main(){floatx,x0,f,f1;x0=1.5;f=((2*x0-4)*x0+3)*x0-6;f1=(6*x0-8)*x0+3;x=x0-f/f1;第7页/共41页while(fabs(x-x0)>=1e-5)

{

x0=x;f=((2*x0-4)*x0+3)*x0-6;f1=(6*x0-8)*x0+3;x=x0-f/f1;}

printf("%10.8f\n",x);}第8页/共41页四、数字分离

有些题中经常要求将一个数中的每一位数字或者其中的某些位数字输出，就需要使用到数字分离技术。如在求解同构数等问题时都需要使用到数字分离技术第9页/共41页例：给出一个不多于4位的正整数，要求：求出它是几位数，并且按逆序打印出各位数字main(){inti,j,k=0;scanf("%d",&i);while(i!=0)

{printf("%4d",i%10);i=i/10;k++;

}printf("\nk=%d\n",k);}第10页/共41页四、以特殊字符做为终止标志例：统计从键盘输入字符的个数，以'#'结束。#include"stdio.h"main(){charc;inti;c=getchar();for(i=0;c!='#';i++)c=getchar();printf("thenumberis:%d",i);}第11页/共41页五、排序问题常用的排序方法有四种：顺序交换法、选择法、冒泡法、插入法a.顺序排序法(n=10)指导思想：先设定a[0]中存放最小值，然后用a[0]分别与其后的每一个数a[j]（j=1..9）进行比较，在比较过程中如果发现有比a[0]小的数，就将a[0]与a[j]互换，一遍扫描之后，a[0]就是10个数中最小的数，重复此算法，只是每次比较时，进行比较的数的范围向后移一个位置。反复执行(n-1)次上述操作第12页/共41页例1：将数组a中的10个数按照由大到小的顺序排好(使用顺序交换法)#defineN10main(){inta[N],i,j,k,t;for(i=0;i<N;i++)scanf("%d",&a[i]);

for(i=0;i<N-1;i++)for(j=i+1;j<N;j++)if(a[j]<a[i]){t=a[j];a[j]=a[i];a[i]=t;}for(i=0;i<N;i++)printf("%5d",a[i]);}第13页/共41页b.选择排序法

指导思想：不急于交换，先找出a[0]到a[9]中的最小数所在的位置k，一遍扫描完之后，在把a[0]与a[k]进行交换，重复次算法9次。例2：将数组a中的10个数按照由大到小的顺序排好(使用选择法)第14页/共41页#defineN10main(){inta[N],i,j,k,t;for(i=0;i<N;i++)scanf("%d",&a[i]);

for(i=0;i<N-1;i++){k=i;for(j=i+1;j<N;j++)if(a[j]<a[k])k=j;t=a[i];a[i]=a[k];a[k]=t;}for(i=0;i<N;i++)printf("%5d",a[i]);}第15页/共41页c.冒泡法指导思想：是将相邻的两个数进行比较，若前一个数比后一个数大，在交换两元素的内容，否则不交换。从而把最大的数放在最后位置。第16页/共41页#defineN10main(){inta[N],i,j,k,t;for(i=0;i<N;i++)scanf("%d",&a[i]);

for(i=0;i<N-1;i++)for(j=0;j<N-i-1;j++)if(a[j+1]<a[j]){t=a[j];a[j]=a[j+1];a[j+1]=t;}for(i=0;i<N;i++)printf("%5d",a[i]);}第17页/共41页例：有N个数已按由小到大的顺序排好，要求输入一个数，把它插入到原有序列中，而且仍然保持有序。输入数据时，使其数据排列仍然有序解题思想：先找到待插入的位置，然后将从该位置起到数组的最后位置的所有元素均向后移一个位置。第18页/共41页

main(){inta[100],i,j,n,x;scanf("%d",&n);/*确定数组元素中的个数*/for(i=0;i<n;i++)scanf("%d",&a[i]);/*给数组的每个元素赋初值*/scanf("%d",&x);/*输入待插入的数据*/for(i=0;i<n;i++)if(a[i]>x)break;/*找到待插入的位置i*/for(j=n-1;j>=i;j--)a[j+1]=a[j];/*从a[i]到a[n-1]之间的数组军后移一位*/a[i]=x;/*把数据x放到a[i]位置处*/for(i=0;i<=n;i++)printf("%5d",a[i]);printf("\n");}第19页/共41页 main() {intx[50],y,n,i; scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&x[i]);printf("%5d",x[i]);}printf("\n"); for(i=0;i<=(n-1)/2;i++) {y=x[i]; x[i]=x[n-1-i]; x[n-1-i]=y;} for(i=0;i<n;i++) printf("%5d",x[i]); printf("\n"); }方法1：例6．将n(n<=50)个整数按逆序重放在数组中。第20页/共41页 main() {intx[100],n,m,i,j; scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",&x[i]); for(j=1;j<=n;j++){m=x[0]; for(i=0;i<n-j;i++)x[i]=x[i+1]; x[n-j]=m; } for(i=0;i<n;i++) printf("%5d",x[i]); printf("\n"); }方法2第21页/共41页注意：求解水仙花数、完数、同构数、最大公约数和最小公倍数以及费波拉切数列等内容水仙花数：是一个三位数，其各位数字的立方和等于该数本身。如：153=13+53+33完数：一个数等于它的所有因子（不包括它本身）之和。如：6=1+2+3同构数：一个数等于它的平方数的右端。如5的平方是25最大公约数：使用辗转相除法进行求解第22页/共41页图形1：（法一）main(){inti,j;for(i=1;i<=5;i++){for(j=1;j<=5;j++)printf(“*”);printf(“\n”);}}*************************六、简单图形打印第23页/共41页图形1：（法二）main(){inti;for(i=1;i<=5;i++)printf(“*****\n”);}*************************第24页/共41页图形2：（法一）main(){inti,j;for(i=1;i<=5;i++){for(j=1;j<i;j++)printf(““);for(j=1;j<=5;j++)printf(“*”);printf(“\n”);}}*************************第25页/共41页图形2：（法二）main(){inti,j;for(i=1;i<=5;i++){for(j=1;j<i;j++)printf(““);printf(“*****\n”);}}*************************第26页/共41页图形3：main(){inti,j;for(i=1;i<=5;i++){for(j=1;j<=5-i:j++)printf(““);for(j=1;j<=5;j++)printf(“*”);printf(“\n”);}}*************************第27页/共41页图形4：main(){inti,j;for(i=1;i<=5;i++){for(j=1;j<=i;j++)printf(“*”);printf(“\n”);}}***************第28页/共41页图形5：main(){inti,j;for(i=1;i<=5;i++){for(j=1;j<=5-i;j++)printf(““);for(j=1;j<=i;j++)printf(“*”);printf(“\n”);}}***************第29页/共41页*************************图形6：main(){inti,j,k;for(i=1;i<=4;i++){for(j=1;j<=4-i;j++)printf("");for(k=1;k<=2*i-1;k++)printf("*");printf("\n");}

for(i=1;i<=3;i++){for(j=1;j<=i;j++)printf("");for(k=1;k<=7-2*i;k++)printf("*");printf("\n");}}第30页/共41页七、字符数组

在这一部分里要注意字符串的正确的输入、输出格式。一般我们使用'\0'做为循环终止的条件，如想用长度做为终止条件，则该长度应为字符串的实际长度，而不应用定义字符数组时声明的长度

注意：字符串的排序、连接问题（5-13、5-16）第31页/共41页练习1、在一个字符串中删除一个指定的字符。1、找到要删除字符的位置，将其后面的字符依次往前移一个位置。2、利用产生一个新数组的方法，对原串中的不等于指定的字符的字符放到新数组中。第32页/共41页#include"stdio.h"main(){charstr[80],c;inti,j;gets(str);c=getchar();j=0；for(i=0;str[i]!='\0';i++)if(str[i]!=c){str[j]=str[i];j++;}str[j]='\0';puts(str);}#include"stdio.h"main(){charstr[80],c;inti,j,k;gets(str);c=getchar();for(i=strlen(str)-1;i>=0;i--)if(str[i]==c){for(k=i;str[k]!='\0';k++)str[k]=str[k+1];str[k]='\0';}puts(str);}第33页/共41页练习2、编写程序，比较两个字符串的大小。(不能使用strcmp()函数)比较规则：逐个字符进行比较，直到有两个字符不等或有一个字符串结束为止。第34页/共41页main(){chars1[80],s2[80];inti,k;gets(s1);gets(s2);i=0;while(s1[i]!='\0'&&s2[i]!='\0')

if(s1[i]!=s2[i])break;elsei++;

k=s1[i]-s2[i];if(k>0)printf("s1>s2\n");elseif(k<0)printf("s1<s2\n");elseprintf("s1=s2\n");}第35页/共41页

main(){chars1[80],s2[80];inti,k;gets(s1);gets(s2);i=0;while(s1[i]==s2[i]&&s1[i]!='\0'&&s2[i]!='\0')i++;k=s1[i]-s2[i];if(k>0)printf("s1>s2\n");elseif(k<0)printf("s1<s2\n");elseprintf("s1=s2\n");}第36页/共41页练习3、判断一字符串是否为另一个字符串的子串，若是则返回第一出现的起始位置，否则则返回0main(){staticchars1[20]="IloveChina!";staticchars2[20]="love";inti,j,k,m=0;for(i=0;s1[i]!='\0';i++)

if(s1[i]==s2[0])

{for(j=1,k=i+1;s2[j]!='\0';j++,k++)if(s1[k]!=s2[j])break;if(s2[j]=='\0'){m=i;break;}

}printf("stationis%d\n",m);}第37页/共41页八、对矩阵的操作注意：矩阵的主对角线、副对角线的概念如何实现矩阵转置、求解矩阵中指定的元素之和等问题（如求解右上三角、左下三角的元素之和）打印杨辉三角形（用一维和二维分别实现）第38页/共41页习题7.6:输出杨辉三角形（10行）。vo