算法归纳 （ 1 ）关键字比较次数：无论文件初始状态如何，在第 i 趟排序 中选出最小关键字的记录，需做 n-i 次比较，因此，总的比较次数 为： n(n-1)/2=0(n 2 )； （ 2 ）记录的移动次数：当初始文件为正序时，移动次数为 0 ； 初态为反序时，每趟排序均要执行交换操作，总的移动次数取最 大值 3(n-1) 。 直接选择排序的平均时间复杂度为 O(n2 ) 。
} //output for(i=1;i<=100;i++) if(a[i]==0) printf("%4d",i); getch(); }
【提示】素数是指，除了1和本身，没有其它因子的自然数。最小 素数为2.判断一个数是否为素数通常对所有可能的因子进行判 断。我们只须判断整数num，是否能被2~sqrt(num)范围内的整数 整除，如果能，则不是，否则为素数。
***思考***如何生成不同的10个数？ 9、约瑟夫问题 设有N个人围成一圈。从第1个人开始报数，数到M的人出圈；再 由下一个人开始从1开始报数，数到M的人出圈；…..，如此继 续，直到所有人都出圈为止，设N个人的编号分别为1,2,…,N,打印 输出出列次序。（11_8.c） 输入:M、N由键盘输入； 输入样例： 人数N：10 报数M：5 输出样例 5，10， 6 ，12 ，9， 8， 1 ，4 ，7 ，3
3、 读入10个数，输出偶数项，并打印它们的和，输出奇数项， 并打印它们的平均值。（11_2.c）
4、 读入10个数，打印其中的最大数和最小数及其位置号。 （11_3.c）
5、 有N盏灯，放在一排，从1到N依次顺序编号。有N个人也从1到
N依次编号。
第1个人（1号）将灯全部关闭；第2个人
（2号）将凡是2的倍数的灯打开；第3个人（3号）将凡是3的
2、 程序填空求：100以内的素数。（11_1.c） #include <stdio.h> #include <math.h> main() { int a[101],i,k,m; for(i=2;i<=100;i++) a[i]=1 ; for(i=2;i<=100;i++) if(a[i]==1) {m=sqrt(i); for(k=2;k<=m;k++) if(i%k==0) a[i]=0;
【操作提示】 第1步：随机生成10个100以内的随机数，赋值数组元素a[i]（循 环，注意有序性，假设为从小到大） 第2步：输入整数x 第3步：利用循环遍历数组元素a[0]~a[9]，如果x>a[i]，则退出循 环，且记住i的位置值，将x插入到a[i]前； 第4步：利用循环将数组元素a[i]~a[9]向后平移至a[i+1]~a[10]; 第5步：将x赋值给a[i]; 第6步：输出数组元素；
【算法分析】 初始化，N个人的初始状态，均未出列表示：数组元素 a[0]~a[99]为1； K为出列人数，当为n时，表示全部出列，则游戏结束。 （While循环） 开始报数位置标志i=1； 在1~n个人中（while循环）， ---如果此人未出列（a[i]==1），则累计报数器s（s++）； ---当S能被M整除时，出列人数k++，并且将a[i]置为0，表
7、 随机生成10个100以内的整数，使用“选择排序法”升序（从小 到大）排列输出。（11_1.6）
【选择排序法描述】 第1步：在1~n个数中，找到最小数，和第1个数交换；前1个数排 好序； 第2步：在2~n个数中，找到最小数，和第2个数交换；前2个数排 好序； ……. 第k步：在k~n个数中，找到最小数，和第k个数交换；前k个数排 好序； ….. 第n-1步：在n-1~n个数中，找到最小数，和第n-1个数交换；排序 结束。 **思考**
的灯将是亮着的），总结规律，简化处理；
完全平方数的因子个数为奇数？偶数？
6、 输入10个100以内的整数，按升序存放在数组a中，再任意输 入一个数x,将x插入到有序数组a中，保证数组a仍然有序。
（11_5.c） 随机数的生成 # include <time.h> srand((int)time(0)); /*随机种子*/ for(i=0;i<10;i++) a[i]=rand()%100;
一维数组第2讲：应用举例
1、 读程，写出程序运行后的正确运行结果. main() {
int n[2]={0},i,j,k=2; //赋值 for(i=0;i<k;i++)
for(j=0;j<k;j++) {n[j]=n[i]+1; printf("%d,%d\n",j,n[j]); } //输出 printf("\n**************\n"); for(i=0;i<k;i++) printf("n[%d]=%d\n",i,n[i]); getch(); } 运行结果：
示已出列；并输出i的位置； ---继续下一个人的判断；
11（11_10.c）
12、求满足等式x2=?????????（9个），每个问号互不相同，且 遍历1~9；（11_11.c） 13、
（11_12.c） 14、
（11_13.c）
8、 随机生成10个100以内的整数，使用“冒泡排序法”降序（从大 到小）排列输出。（11_7.c）
【冒泡排序法描述】 第1步：从前往后，相邻2个数比较，较小数后移，反复n-1次，最 后1个数最小； 第2步：从前往后，相邻2个数比较，较小数后移，反复n-2次，最 后2个数Ok； ……. 第k步：从前往后，相邻2个数比较，较小的数后移，反复n-3次， 最后k个数OK； ….. 第n-1步：从前往后，相邻2个数比较，较小的数后移，执行1次， OK；
倍数的灯做相反处理（该灯如是打开的，则将它关闭；如是关
闭的，则将它打开）。以后的人都和3号一样，将凡是自己编
号倍数的灯做相反处理。试计算当第N个人操作后，哪几盏灯
是亮的。（11_4.c）
【操作提示】
灯的亮或灭如何表示？如何模拟每个人对灯的相反处理？
灯的亮与灭与灯被拉的次数的关系（因子数为偶数的序号对应
【算法设计】 数组a[n]存放待排的n个数。外层k循环1~n-1步，对应每一步，利 用j循环,控制比较次数，n-k，比较a[j]和a[j+1]，若a[j]<a[j+1]，则交
换这两个元素。
【程序大致流程】 1） 随机生成数组元素； 2） 输出排序前的数字序列； 3） 冒泡排序实现排序过程； 4） 输出排序后的结果；
几层循环？外层、内层循环的控制变量？ 比较过程中的关键变量设置？（比较元素的表示？最值表 示？位置记录？） 【算法设计】
数组a[n]存放待排的n个数。循环控制变量k控制1~n-1步，对应每 一步，利用j,控制在a[k]~a[n-1]中寻找最小数，并记录其下标pos， 找到后，和a[k]交换。
【程序大致流程】 1） 随机生成数组元素； 2） 输出排序前的数字序列； 3） 选择排序实现排序过程； 4） 输出排序后的结果；
