实验9资料-20181

实验9的目的是让学生熟悉基本的算法实现，包括随机数生成、冒泡排序、折半查找以及数组的操作。下面是这些知识点的详细说明： 1. **随机数生成与输出**： 使用`rand()`函数可以生成0到`RAND_MAX`之间的随机整数。在描述中，为了在10到100之间生成10个随机数，我们首先通过`srand(time(NULL))`对随机数生成器进行初始化，然后使用`rand() % (100 - 10 + 1) + 10`计算10到100之间的随机整数。 2. **冒泡排序**： 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。对于降序排序，我们需要在比较时改变条件，使得较大的元素向后移动。在N-S流程图中，外层循环`for(i=0; i<n-1; i++)`控制遍历次数，内层循环`for(j=0; j<n-i-1; j++)`负责每次遍历中的交换操作，判断条件改为`a[j]>a[j+1]`，使得较大的元素逐渐"冒"到数列的末尾。 3. **折半查找**： 折半查找（也叫二分查找）适用于已排序的数组。在N-S流程图中，我们需要根据目标值`x`与中间元素`a[mid]`的比较结果来调整查找范围。如果`x`等于`a[mid]`，则找到目标并结束查找；如果`x`大于`a[mid]`，则在`mid+1`到`bot`之间继续查找；如果`x`小于`a[mid]`，则在`top`到`mid-1`之间查找。注意，数组如果是降序排列，比较条件需要相应调整。 4. **选择法排序**： 选择法排序是找到数组中最小（或最大）的元素，然后将其放到正确的位置。改进的选择法算法减少了不必要的比较，当找到最小值时，不再检查后面的元素，这提高了效率。 5. **斐波那契数列与数组操作**： 斐波那契数列前两项为1，后续每一项是前两项之和。在给定的实验中，数组`a`初始包含斐波那契数列的前10项。接下来的任务包括： - 插入元素：要保持有序，从数组末尾开始遍历，直到找到合适的位置`p`插入新元素，然后将所有大于新元素的元素后移一位。 - 删除重复元素：遍历数组，比较相邻元素，如果相同，则将后者删除，只保留一个。 - 计算平均值：累加所有元素，除以元素个数。 - 删除低于平均值的元素：计算平均值，遍历数组，删除所有低于平均值的元素。 以上就是实验9中的关键知识点，包括随机数生成、冒泡排序、折半查找以及数组操作等。这些基础知识在编程和算法设计中非常常见，对理解计算机科学的基础原理至关重要。