C语言常见算法学习教案

1、会计学1C语言常见语言常见(chn jin)算法算法第一页，共41页。(2) 随机数随机数 函数函数random(int num)用于产生用于产生0,num)区区间的一个整数。间的一个整数。其包含在其包含在“stdlib.h”头文件中头文件中 为了为了(wi le)使每一次运行都产生一组新的使每一次运行都产生一组新的随机数，可以使用随机数，可以使用randomize()函数是每次均产函数是每次均产生不同的随机数。其包含在头文件生不同的随机数。其包含在头文件“time.h”中中(3) 最大值与最小值最大值与最小值 我们需要将最大值（或最小值）保存在一个变量中我们需要将最大值（或最小值）保存在一个

2、变量中（假设设变量名为（假设设变量名为max和和min）,变量的初值我们一般变量的初值我们一般(ybn)设为数列中的第一个值。设为数列中的第一个值。第二页，共41页。例例2：产生：产生(chnshng)20个个50到到200之间的随机之间的随机整数，并求出其中的素数、最大值和最小值。整数，并求出其中的素数、最大值和最小值。#include stdlib.h#include time.hmain() int a20,b20,max,min,k,i,j=0; randomize(); for(i=0;i20;i+) ai=random(151)+50;产生产生(chnshng)20个个50,200

3、区间内的随机数区间内的随机数第三页，共41页。 for(i=0;i20;i+) for(k=2;kai;k+) if(ai%k=0) break; if(k=ai) bj=ai; j+; for(i=0;ij;i+) printf(%4d,bi); printf(n);从从a数组中找出其中数组中找出其中(qzhng)的素数放在的素数放在b数组中数组中输出输出(shch)b数数组中的各个元组中的各个元素素 max=a0; min=a0; for(i=1;imax) max=ai; if(ai=1e-5) x0=x; f=(2*x0-4)*x0+3)*x0-6; f1=(6*x0-8)*x0+3;

4、 x=x0-f/f1; printf(%10.8f n,x); 第九页，共41页。四、数字四、数字(shz)分离分离 有些题中经常(jngchng)要求将一个数中的每一位数字或者其中的某些位数字输出，就需要使用到数字分离技术。 如在求解同构数等问题时都需要使用到数字分离技术第十页，共41页。例：给出一个不多于例：给出一个不多于(du y)4位的正整数，要位的正整数，要求：求出它是几位数，并且按逆序打印出各位求：求出它是几位数，并且按逆序打印出各位数字数字 main() int i,j,k=0; scanf(%d,&i); while(i!=0) printf(%4d,i%10); i=

5、i/10; k+; printf(nk=%dn,k);第十一页，共41页。四、以特殊字符做为终止四、以特殊字符做为终止(zhngzh)标志标志例：统计从键盘输入字符例：统计从键盘输入字符(z f)的个数，以的个数，以#结结束。束。#include stdio.hmain() char c; int i; c=getchar(); for(i=0; c!=#; i+) c=getchar(); printf(the number is:%d,i);第十二页，共41页。五、排序五、排序(pi x)问题问题常用的排序方法有四种：常用的排序方法有四种：顺序顺序(shnx)交换法、选择法、冒泡法、插入法

6、交换法、选择法、冒泡法、插入法a.顺序排序法顺序排序法(n=10)指导思想：先设定指导思想：先设定a0中存放最小值，然后用中存放最小值，然后用a0分别与其后的每一个数分别与其后的每一个数aj（j=1.9）进行）进行(jnxng)比较，在比较过程中如果发现有比比较，在比较过程中如果发现有比a0小的数，小的数，就将就将a0与与aj互换，一遍扫描之后，互换，一遍扫描之后，a0就是就是10个数中最小的数，重复此算法，只是每次比较时个数中最小的数，重复此算法，只是每次比较时，进行，进行(jnxng)比较的数的范围向后移一个位置比较的数的范围向后移一个位置。反复执行。反复执行(n-1)次上述操作次上述操作

7、第十三页，共41页。例例1：将数组：将数组a中的中的10个数按照个数按照(nzho)由大由大到小的顺序排好到小的顺序排好(使用顺序交换法使用顺序交换法)#define N 10main( ) int aN,i,j,k,t; for(i=0;iN;i+) scanf(%d,&ai); for (i=0;iN-1;i+) for (j=i+1;jN;j+) if (ajai) t=aj; aj=ai; ai=t; for(i=0;iN;i+) printf(%5d,ai);第十四页，共41页。b.选择排序选择排序(pi x)法法 指导思想：不急于交换，先找出指导思想：不急于交换，先找出a0

8、到到a9中中的最小数所在的位置的最小数所在的位置k，一遍扫描完之后，在把，一遍扫描完之后，在把a0与与ak进行交换，重复次算法进行交换，重复次算法9次。次。例例2：将数组：将数组a中的中的10个数按照个数按照(nzho)由大到小由大到小的顺序排好的顺序排好(使用选择法使用选择法)第十五页，共41页。#define N 10main( ) int aN,i,j,k,t; for(i=0;iN;i+) scanf(%d,&ai); for (i=0;iN-1;i+) k=i; for(j=i+1;jN;j+) if(ajak) k=j; t=ai; ai=ak; ak=t; for(i=0

9、;iN;i+) printf(%5d,ai);第十六页，共41页。c.冒泡法冒泡法指导思想：是将相邻指导思想：是将相邻(xin ln)的两个数进行比的两个数进行比较，若前一个数比后一个数大，在交换两元素较，若前一个数比后一个数大，在交换两元素的内容，否则不交换。从而把最大的数放在最的内容，否则不交换。从而把最大的数放在最后位置。后位置。第十七页，共41页。#define N 10main( ) int aN,i,j,k,t; for(i=0;iN;i+) scanf(%d,&ai); for (i=0;iN-1;i+) for(j=0;jN-i-1;j+) if(aj+1aj) t=a

10、j; aj=aj+1; aj+1=t; for(i=0;iN;i+) printf(%5d,ai);第十八页，共41页。例：有例：有N个数已按由小到大的顺序排好，个数已按由小到大的顺序排好，要求要求(yoqi)输入一个数，把它插入到原输入一个数，把它插入到原有序列中，而且仍然保持有序。有序列中，而且仍然保持有序。输入输入(shr)数据时，使其数据排列仍然有数据时，使其数据排列仍然有序序解题解题(ji t)思想：思想： 先找到待插入的位置，然后将从先找到待插入的位置，然后将从该位置起到数组的最后位置的所有元该位置起到数组的最后位置的所有元素均向后移一个位置。素均向后移一个位置。第十九页，共41页

11、。 main() int a100,i,j,n,x; scanf(%d,&n); /* 确定数组元素中的个数 */ for (i=0;in;i+) scanf(%d,&ai); /* 给数组的每个元素赋初值 */ scanf(%d,&x); /* 输入待插入的数据(shj) */ for (i=0;ix) break; /* 找到待插入的位置i */ for (j=n-1;j=i;j-) aj+1=aj; /* 从ai到an-1之间的数组军后移一位*/ ai=x; /*把数据(shj)x放到ai位置处*/ for (i=0;i=n;i+) printf(%5d,ai);

12、 printf(n); 第二十页，共41页。main( ) int x50,y,n,i; scanf(%d,&n); for(i=0;in;i+) scanf(%d,&xi); printf(%5d,xi); printf(n); for(i=0;i=(n-1)/2;i+) y=xi; xi=xn-1-i; xn-1-i=y; for(i=0;in;i+) printf(%5d,xi); printf(n); 方法方法(fngf)1： 例例6将将n(n=50)个整数个整数(zhngsh)按逆序重放在按逆序重放在数组中。数组中。第二十一页，共41页。main( ) int x10

13、0,n,m,i,j; scanf(%d,&n); for(i=0;in;i+) scanf(%d,&xi); for(j=1;j=n;j+) m=x0; for(i=0;in-j;i+) xi=xi+1; xn-j=m; for(i=0;in;i+) printf(%5d,xi); printf(n); 方法方法(fngf)2第二十二页，共41页。注意：求解水仙花数、完数、同构数、最大公约数注意：求解水仙花数、完数、同构数、最大公约数和最小公倍数以及费波拉切数列等内容和最小公倍数以及费波拉切数列等内容水仙花数：是一个三位数，其各位数字的立方和等水仙花数：是一个三位数，其各位数字

14、的立方和等于该数本身。如：于该数本身。如：153=13+53+33完数：一个数等于它的所有因子（不包括它本身）完数：一个数等于它的所有因子（不包括它本身）之和。如：之和。如：6=1+2+3同构数：一个数等于它的平方数的右端。如同构数：一个数等于它的平方数的右端。如5的平方的平方是是25最大公约数：使用最大公约数：使用(shyng)辗转相除法进行求解辗转相除法进行求解第二十三页，共41页。图形图形(txng) 1： （法一）（法一）main() int i,j; for (i=1;i=5;i+) for (j=1;j=5;j+) printf (“ *”); printf(“n”); * * *

15、 * * * * * * * * * * * * * * * * * * * * * *六、简单六、简单(jindn)图形打印图形打印第二十四页，共41页。图形图形(txng) 1：（法二）：（法二）main() int i; for (i=1;i=5;i+) printf (“ * * * * *n”); * * * * * * * * * * * * * * * * * * * * * * * * *第二十五页，共41页。图形图形(txng) 2：（法一）：（法一）main() int i,j; for (i=1;i=5;i+) for ( j=1;ji;j+) printf ( “ “)

16、; for ( j=1;j=5;j+) printf (“ *”); printf(“n”); * * * * * * * * * * * * * * * * * * * * * * * * *第二十六页，共41页。图形图形(txng) 2：（法二）：（法二）main() int i,j; for (i=1;i=5;i+) for ( j=1;ji;j+) printf ( “ “); printf (“ * * * * *n”); * * * * * * * * * * * * * * * * * * * * * * * * *第二十七页，共41页。图形图形(txng) 3：main() i

17、nt i,j; for (i=1;i=5;i+) for (j=1;j=5-i:j+) printf ( “ “); for (j=1;j=5;j+) printf (“ *”); printf(“n”); * * * * * * * * * * * * * * * * * * * * * * * * *第二十八页，共41页。图形图形(txng) 4 ：main() int i,j; for (i=1;i=5;i+) for (j=1;j=i;j+) printf (“ *”); printf(“n”); * * * * * * * * * * * * 第二十九页，共41页。图形图形(txng

18、) 5：main() int i,j; for (i=1;i=5;i+) for (j=1;j=5-i;j+) printf (“ “); for (j=1;j=i;j+) printf (“*”); printf(“n”); * * * * * * * * * * *第三十页，共41页。 * * * * * * * * * * * * * * * * * * * * * * * * *图形图形(txng)6：main() int i,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(*);

19、 printf(n); for(i=1;i=3;i+) for(j=1;j=i;j+) printf( ); for(k=1;k=0;i-) if(stri=c) for(k=i;strk!=0;k+) strk=strk+1; strk=0; puts(str); 第三十四页，共41页。练习练习2 2、编写程序，比较、编写程序，比较(b(bjio)jio)两个字两个字符串的大小。符串的大小。( (不能使用不能使用strcmp()strcmp()函数函数) )z比较规则：逐个比较规则：逐个(zhg)字符进行比较字符进行比较，直到有两个字符不等或有一个字符串结，直到有两个字符不等或有一个字符串结

20、束为止。束为止。第三十五页，共41页。main()char s180,s280; int i,k; gets(s1); gets(s2); i=0; while(s1i!=0&s2i!=0) if(s1i!=s2i) break; else i+; k=s1i-s2i; if(k0) printf(s1s2n); else if(k0) printf(s10) printf(s1s2n); else if(k0) printf(s1s2n); else printf(s1=s2n); 第三十七页，共41页。练习练习3、判断一字符串是否为另一个字符串的子串、判断一字符串是否为另一个字符串的子串，若是则返回第一，若是则返回第一(dy)出现的起始位置，否则则出现的起始位置，否则则返回返回0main() static char s120=I love China!; static char s220=love; int i,j,k,m=0;