一维数组的应用实例

6.1.5　一维数组的应用实例

例6.2　某超市进行促销活动，凡购买商品总金额达100元返现金10元，总金额达200元返20元，总金额达300元返30元，以此类推，上不封顶。试编程使收银机完成此功能。

分析：每一件商品的金额可以用一维数组a存放，为了符合日常生活习惯，编程时可以从a[1]开始存放商品金额。首先求出商品总金额，存放在a[0]中，然后求出返回的现金值，从而得到顾客应付的费用。

程序如下：

程序运行结果如下：

例6.3　采用线性查找法在数组中查找是否有数据x。若有，则显示它在数组中的位置；若没有，则显示没有找到该数。

分析：从第一个元素开始，依次将要查找的数与数组中元素比较，如果找到该数，则退出查找；若找遍整个数组都没有该数，则说明没有找到。

可以设一个标志find用来判断是否查找成功，0表示未成功，1表示成功，初值为0。

程序如下：

程序运行结果如下：

请输入要找的数：11↙

没有找到数11

重新查找一个数，即重新运行该程序，程序运行结果如下：

请输入要找的数：6↙

6是a[5]元素

例6.4　采用二分查找法在数组中查找是否有数据x。若有，则显示它在数组中的位置；若没有，则显示没有找到该数。

分析：二分查找法又称折半查找法，是在已排好序的一组数据中查找。具体做法：假定数据是按升序排列的，对于给定值x，从序列的中间位置开始比较，如果当前位置的值就是x，则查找成功；否则，若x小于当前位置值，则在序列的前半段数据中继续查找；若x大于当前位置值，则在序列的后半段数据中继续查找，直到找到为止。如果表示序列查找范围的上、下界数值颠倒时，查找不成功。

下面对一个具体的实例进行分析：

对于已排好序的数据序列（数组a），要求查找给定值x=3。

1　2　3　4　5　6　7　8　9　10

查找过程如下：

①用low、high作为查找范围的上、下界，用mid表示每次比较的数据对象的位置，它在由low和high标记的查找范围的中间，即mid=(low+high)/2。

②最初low=0，high=9，则mid=4，若用“[”和“]”代表查找范围，着重号指明要比较的数，即mid所在位置，则有下列表示：

[1　2　3　4　5．　6　7　8　9　10]

③此时a[mid]=5,x<a[mid],应在前半段中查找。重新设定查找范围如下：low=0，high=mid-1=3，则mid=2，并有下列表示：

[1　2．　3　4]　5　6　7　8　9　10

④此时a[mid]=2，x>a[mid]，应在后半段中查找，重新设定查找范围如下：low=mid+1=2，high=3，则mid=2，并有下列表示：

1　2　[3．　4]　5　6　7　8　9　10

⑤此时x=a[mid]=3，则查找成功。

程序如下：

程序运行结果如下：

请输入要找的数：25↙

没有找到数25

重新查找一个数，即重新运行该程序，程序运行结果如下：

请输入要找的数：8↙

8是a[7]元素

例6.5　从键盘上任意输入10个整数，要求按从小到大的顺序在屏幕上显示出来。

分析：排序的方法有很多，本题采用冒泡排序法。

冒泡排序法的基本思想：通过相邻两个数之间的比较和交换，使数值较小的数逐渐从底部移向顶部，数值较大的数逐渐从顶部移向底部，就像水底的气泡一样逐渐向上冒，故而得名。

由a[1]～a[n]组成的n个数据，进行冒泡排序的过程描述如下：

①首先将相邻的a[n]与a[n-1]进行比较，如果a[n]的值小于a[n-1]的值，则交换两者的位置，使较小的上浮，较大的下沉；接着比较a[n-1]与a[n-2]的值，同样使较小的上浮，较大的下沉。依次类推，直到比较完a[2]和a[1]后，a[1]中存放的是最小的数，称第一轮排序结束。

②然后在a[n]～a[2]区间内，重复上述过程，进行第二轮排序，使剩余元素中最小数据上浮到a[2]处；重复进行n-1趟后，整个排序过程结束。

下面通过一个具体的例子来说明冒泡排序的工作过程。有以下5个数，要求从小到大进行排序。过程如下，其中方括号里是已排好序的数：

完成一轮排序后，已排好序的数就增加一个，待排序的数就减少一个，从而使下一轮排序的比较次数减少一次，因此对n个数来说，各轮比较次数依次为：n-1，n-2，…，1。

对10个数进行从小到大排序，为了符合日常生活的习惯，可以定义数组长度为11，10个数分别存放在a[1]到a[10]中,不使用a[0]。

程序如下：

程序运行结果如下：

请输入10个数：

10 8 4 6 2 7 5 1 3 9↙

排序后的结果为：

1 2 3 4 5 6 7 8 9 10

注意：

变量j既是控制内循环的循环变量，又是控制待比较元素的下标。

例6.6　 用选择排序法，从键盘上任意输入10个整数从大到小进行排序，并在屏幕上显示出来。

选择排序法的基本思想：给n个数降序排序，将第一个数与其后面的数逐一进行比较，每次比较后，总是将大者放在第一个数的位置，经过n-1次比较后，n个数中的最大者放在了最前面；接着，将第二个数与其后面的n-2个数逐一进行比较，每次比较后，总是将大者放在第二个数的位置，经过n-2次比较后，n个数中的第二大的数放在了第二个位置……如此重复下去，当最后两个数比较完之后，整个排序过程结束。

例如： n=4，初始值为：26　　85　　17　　64

程序如下：

程序运行结果如下：

请输入10个数：

9 8 5 6 3 7 4 1 2 10↙

排序后的结果为：

10 9 8 7 6 5 4 3 2 1

例6.7　用筛选法求100以内的素数,并按每行5个的格式打印出来。

先分析如何用筛选法求出2～25之间的所有素数：

写出2～25之间的整数如下：

显然，这些数中最小的数2是素数，把除2以外凡是2的倍数的那些数筛去，余下的是：

从2的后面找出最小的数3是素数，把3以外凡是3的倍数的那些数筛去，余下的是：

再从3的后面找出最小的数5是素数……不断重复以上过程，最后余下的即为所求。

通过以上分析，现在我们可以定义一个数组a[100]作为筛子，把2～100的数放到筛子上（对应于下标2～100），将每一个数组元素初值都设为0(假定数组元素为0时表示是其下标值是素数，数组元素为1时表示是其下标值不是素数)：

①先找第一个素数2，将下标是2的倍数所对应的元素的值都改为1（表示筛去2的倍数），即a[4]，a[6]，a[8]，…，a[100]的值改为1。

②再找下一个值为0的数组元素，其下标是3，将下标是3的倍数所对应的元素的值都改为1，去掉3的倍数。

③重复步骤②，找下一个为0的数组元素，并去掉其倍数，直到没有下一个为0的元素为止。

注意：

被考察数i的倍数由反复加上i形成:

如2的倍数依次是：2+2，2+2+2，…

3的倍数依次是：3+3,3+3+3，…

程序如下：

程序运行结果如下：