实验七数组（2）
【实验目的】：
1、掌握一维数组的定义、赋值和输入输出的方法；
2、掌握与数组有关的算法（例如排序算法）；
3、熟悉循环语句与数组处理语句结合的方法。
【实验时数】：2学时
【实验内容】：
一、新建文件夹
首先在各自对应的计算机wks盘上新建一个文件夹，文件夹的名字为“班级+学号的后两位+姓名”，如食品1081班、学号后两位是02的、姓名为“张三”的同学，则其对应的文件夹名字是：食品108102张三。
然后在刚才建好的文件夹里面再建立一个文件夹，文件夹为“第12次”。
以下实验内容的运行结果需保存在所建的“第12次”文件夹内，并按题目的要求完成。
希望同学们在做以下实验之前，先认真分析程序的运行结果，后再上机验证。
二、实验内容:
[程序一]：有15个数按由大到小顺序存放在一个数组中，输入一个数，要求用折半查找法找出该数是数组中第几个元素的值。
如果该数不在数组中，则打印出“无此数”。
将编写好的程序以文件名search.c保存在你刚才新建好的文件夹里。
【分析】：从表列中查一个数最简单的方法是从第1个数开始顺序查找，将要找的数与表列中的数一一比较，直到找到为止（如果表列中无此数，则应找到最后一个数，然后判定“找不到”）。
但这种“顺序查找法”效率低。
如果表列中有1000个数，且要找的数恰恰是第1000个数，则要进行1000次比较才能得到结果。
平均比较次数为500次。
折半查找法是效率较高的一种方法。
基本思路如下：
假如有已按由小到大排好序的9个数，a[1]～a[9]，其值分别为1、3、5、7、9、11、13、15、17。
若输入一个数3，想查3是否在此数列中，先找出表列中居中的数，即a[5]，将要找的数3与a[5]比较，a[5]的值是9，发现a[5]>3，显然3应当在a[1]到a[5]范围内，而不会在
a[6] 到a[9]范围内。
这样就可以缩小查找范围，甩掉a[6]到a[9]这一部分，即将查找范围缩小为一半。
再找a[1]到a[5]范围内的居中的数，即a[3]，将要找的数3与a[3]比较，a[3]的值是5，发现a[3]>3，显然3应当在a[1]到a[3]范围内。
这样又将查找范围缩小一半。
再将3与a[1]到a[3]范围内的居中的数a[2]比较，发现要找的数3等于a[2]，查找结束。
一共比较了3次。
如果表列中有n 个数，则最多比较的次数为int(log=n)+1。
建立有序数组a[N],flag=1,sign=1
显示a[N]
While(flag==1)
输入要查找的数据number
loca=0;top=0;bott=N-1
number 超出范围loca=-1
While(sign=1&&top<=bott)
mid=(bott+top)/2
number==a[mid)loca=mid
找到,显示结果
sign=0
bott=mid-1top=mid+1sign==1||loca==-1number 不在数组中
是否继续
T
F T F T F T
F T
F number<a[mid]flag=0
top,bott ：查找区间两端点的下标；loca ：查找成功与否的开关变量。
[程序二]：有一篇文章，共有3行文字，每行有80个字符。
要求统计出其中英文大写字母、小写字母、数字、空格以及其他字符的个数。
将编写好的程序以文件名count.c 保存在你刚才新建好的文件夹里。
for(i=0;i<3;i++)
输入文章第i 行
for(j=0;j<80&&text[i][j]!=’\0';j++)
‘A ’--’Z ’‘a ’--‘z ’‘0’--‘9’大写字母个数加1小写
字母个数加1数字
个数
加1
空格个数加1其他字符个数加1
输出大写字母、小写字母、数字、空格及其他字符的个数T F
T F
T F ‘ ’T F
[程序三]：打印出以下的杨辉三角形（要求打印出10行）。
将编写好的程序以文件名triangle.c 保存在你刚才新建好的文件夹里。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
………………
【分析】：杨辉三角形是(a+b)n展开后各项的系数。
例如：
(a+b)0展开后为1 系数为1
(a+b)1展开后为a+b 系数为1，1
(a+b)2展开后为a2+2ab+b2系数为1，2，1
(a+b)3展开后为a3+3a2b+3ab2+b3系数为1，3，3，1
(a+b)4展开后为a4+4a3b+6a2b2+4ab3+b4系数为1，4，6，4，1
以上就是杨辉三角形的前5行，杨辉三角形各行的系数有以下的规律：
（1）各行第一个数都是1；
（2）各行最后一个数都是1；
（3）从第3行起，除上面指出的第一个数和最后一个数外，其余各数是上一行同列和前一列两个数之后。
例如第4行第2个数“3”是第3行第2
个数和第3行第1个数之后。
可以这样表示：a[i][j]=a[i-1][j]+a[i-1][j-1]，
其中i为行数，j为列数。
使数组第一列和对角线元素为1
其他各元素为a[i-1][j-1]+a[i-1][j]（用双重for循环）
输出二维数组的内容
[程序四]：编写一个程序：将用户从键盘上输入的一个不大于256的十进制正整数（应对输入的整数进行合法性的检查）转换成对应的八位二进制数输出。
将编写好的程序以文件名为DtoB.c保存在你刚才新建好的文件夹里。
【要求】：定义一个长度为8的一维数组来存放相应的二进制数，并且初始化初值为0。
将键盘输入的数n不断的除2（n%2）将余数保存在这个定义的数组里。
[程序五]：青年歌手参加歌曲大奖赛，有10个评委对她进行打分，试编程求这位选手的平均得分（去掉一个最高分和一个最低分）。
将编写好的程序以文件名为sort.c保存在你刚才新建好的文件夹里。