• 计算机导论第十一周课后作业

  ---

  第十一周课后作业

  • 6-1 查找最大值并返回其下标
  • • 1.题目
    • 2.思路
    • 3.代码
  • 6-17 实验7_9_简单排序
  • • 1.题目
    • 2.思路
    • 3.代码
  • 6-18 实验7_10_发子弹
  • • 1.题目
    • 2.思路
    • 3.代码
  • 6-19 实验7_12_插入排序
  • • 1.题目
    • 2.思路
    • 3.代码
  • 6-20 实验7_11_循环移位
  • • 1.题目
    • 2.思路
    • 3.代码
  • 6-21 实验7_13_选择排序
  • • 1.题目
    • 2.思路
    • 3.代码
  • 6-22 实验7_14_二分查找
  • • 1.题目
    • 2.思路
    • 3.代码

  6-1 查找最大值并返回其下标

  1.题目

  本题利用函数查找数组中的最大值。
  
  函数接口定义：
  int findMax(int arr[], int n);
  该函数中arr用于接收数组，n为所接收的数组的长度，函数返回值为数组中最大值的下标。
  1
  2
  3
  4
  5

  2.思路

  设置初始max值，之后遍历数组，遇到更大的数则不断更新最大值即可。由于要求返回的是最大值下标，可以用下标表示最大值。

  3.代码

  int findMax(int arr[], int n){
      int max_index=0;//初始设置最大值为第一个元素
      for(int i=1;i

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

  6-17 实验7_9_简单排序

  1.题目

  设计函数 void bubbleSort(int a[],int n);，实现对整型数组的排序。
  
  输入第一行为一个整数n(0

  
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

  2.思路

  比较相邻的元素。如果第一个比第二个大，就交换他们两个。

  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

  针对所有的元素重复以上的步骤，除了最后一个。

  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

  3.代码

  void bubbleSort(int a[],int n){
      for(int i=0;ia[j]){//比较相邻两个元素
                  int temp=a[j];
                  a[j]=a[j-1];
                  a[j-1]=temp;
              }
          }
      }
  }
  void outputData(int data[],int elementCount){
      for(int i=0;i

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

6-18 实验7_10_发子弹

1.题目

在某次实弹射击训练中，班长让战士们围成一圈发子弹。首先，班长给每个人发若干发子弹，然后按如下方法将每个战士手中的子弹进行调整：所有的战士检查自己手中的子弹数，如果子弹数为奇数，则向班长再要一颗。然后每个战士再同时将自己手中的子弹分一半给下一个战士（最后一个战士将手中的子弹分一半给第1个战士)。这种调整会一直进行下去，直到所有战士手中的子弹数相等为止。现请你写一个函数模拟这个调整的过程。

函数接口定义：
void distribute(int * bullets , int size , int number ) ;
其中 bullets 、 size 和 number 都是用户传入的参数。 bullets 为指向一个int 型数组的指针，该数组中依次存储着每个战士手中的子弹数，每次调整后该数组仍然依次存储着每个战士手中的子弹数 ; size 是战士的总数； number为调整的次数。函数没有返回值。
1
2
3
4
5

2.思路

m控制的是调整次数，因此不需要调整到子弹数相同，而是由m的值控制调整的次数。这是第一层循环。
第二层循环需要遍历数组，对于每个元素，为奇数则加一，模拟“要一颗子弹”的过程，而“同时”传递子弹则可以设计一个数组add，用来存储每个士兵交给下一个士兵的子弹数，同时更改自己的子弹数目。

子弹数	10	2	8	22	16	4	10	6	14	20
拿掉一半子弹（该士兵子弹数/2）	5	1	4	11	8	2	5	3	7	10
获得的子弹（上一个士兵子弹数/2）	10	5	1	4	11	8	2	5	3	7

当然，这种方式易于理解但是并不是最优的，实际上只定义一个add变量，初始值为最后一个士兵给第一个士兵的子弹数，之后随着遍历更改add变量即可，可以自己试验一下这种优化思路。

3.代码

void distribute(int * bullets , int size , int number ){
    int add[size];//定义子弹转移的数量
    for(int m=0;m

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

6-19 实验7_12_插入排序

1.题目

设计函数 void InsertSort(int a[],int n); 该函数使用插入排序算法，将数组a的前n个元素按照升序的方式排序。

插入排序算法描述如下：

初始序列：49 38 65 97 76 13 27 49

将元素(38) 插入合适位置： [38 49] 65 97 76 13 27 49

将元素(65) 插入合适位置： [38 49 65] 97 76 13 27 49

将元素(97) 插入合适位置： [38 49 65 97] 76 13 27 49

将元素(76) 插入合适位置： [38 49 65 76 97] 13 27 49

将元素(13) 插入合适位置： [13 38 49 65 76 97] 27 49

将元素(27) 插入合适位置： [13 27 38 49 65 76 97] 49

将元素(49) 插入合适位置： [13 27 38 49 49 65 76 97]

输入与输出要求：
首先输入一个整数n（1<=n<=1000），代表待排序元素的个数。然后输入n个整数，每个整数不会超过int型的存储范围。

输出为n-1行，依次为1到n-1趟排序后数组内各个元素。每行输出的顺序为a[0]至a[n-1]，数与数之间用空格分开，注意第n个数后没有空格而是换行符。

函数接口定义：
函数原型如下：
void InsertSort(int a[],int n);
其中 a 和 n 都是用户传入的参数。 a 为待排序数组； n 需排序的元素的个数。函数没有返回值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2.思路

插入排序的基本思路：前x个元素是已经排序好的数组，对于第x+1个元素，需要在前x个元素中查找它应该处于的位置，插入之后前x+1个元素是排好序的数组，直到x=n；
注意插入的时候还需要考虑后续数组的移动

3.代码

void InsertSort(int a[],int n){
    int sort_len=1;//已经排序的数组的长度,初始假设元素0是长度为1的排序数组
    for(sort_len=1;sort_lena[sort_len]){//第一次出现降序，则是待插入的位置。
                break_index=i;
            }
        }
        int insert_element=a[sort_len];//对待插入元素进行备份，防止后面被覆盖
        for(int j=sort_len;j>break_index;j--){//数组后半段元素移动,从后往前覆盖
            a[j]=a[j-1];
        }
        a[break_index]=insert_element;//元素插入
        //每次需要输出当前数组元素
        for(int i=0;i

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

6-20 实验7_11_循环移位

1.题目

设计函数void shift(int *array , int num , int size ) ;，实现将整型数组内元素循环向左移若干位置。循环向左移位含义如下：

比如，原始数组a[0],a[1]...a[9]内元素依次为：1 2 3 4 5 6 7 8 9 10，循环向左移1位后，则a[0],a[1]...a[9]内元素依次为：2 3 4 5 6 7 8 9 10 1，循环向左移2位后，则a[0],a[1]...a[9]内元素依次为：3 4 5 6 7 8 9 10 1 2。依次类推。

补充说明：本题测试用例中并没有num >= size的情况，大家也可以想一想，如果有这种情况，算法应该如何实现，与没有时是否一样。

函数接口定义：
void shift(int *array , int num , int size ) ;
其中 array 、 num和 size 都是用户传入的参数。 array 为指向原始数组的指针； num 为向左移的位数；size 为数组的大小。函数没有返回值。
1
2
3
4
5
6
7
8
9

2.思路

• 循环移位最简单的思路，开辟temp[num]数组，记录array前num位数组，然后将array中的元素向左移动，之后再用temp数组填补array数组因为移动而产生的空缺。
• 循环移位有一种简洁的思路——三次数组反转：以num为分界点，将数组分为两部分a和b，数组a和b分别反转，之后将数组整体再次反转。

数组反转的过程存在一定的操作重复性，可定义一个reverse函数简化代码。

• 三次反转解决移位问题是一个经典的算法思路。
• 如果num>size,可取num%size的结果作为分割数组的界限值。

3.代码

void reverse(int *array,int start,int end){
//数组反转思路：和回文字符串判断类似，首尾元素交换，向中间会合
    while(start
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6-21 实验7_13_选择排序

1.题目

设计函数 void SelectSort(int a[],int n); 使用选择排序算法对数组a的前n个元素按照升序的方式排序。

选择排序算法描述如下：
从a[0]到a[n-1]这段元素中找最小元素a[min]，a[0]和a[min]交换；接着，从a[1]到a[n -1]这段元素中找最小元素a[min]，a[1]和a[min]交换；依次类推，直到从a[n－2]到a[n -1]这段元素中找最小元素a[min]，a[n－2]和a[min]交换。

输入：首先输入一个整数n(1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

函数接口定义：

//选择排序（升序） 
//参数说明：数组，数组中已有元素个数 
void selectSort(int data[],int elementCount) ;

//函数功能：找数组中的最小值元素，并返回其下标 
//参数说明：数组名，查找起始位置下标，查找终止位置下标
int findMin(int data[], int startLoc, int endLoc) ; 

//输出数组中所有元素 
//参数说明：数组，数组中已有元素个数 
void outputData(int data[],int elementCount) ;
1
2
3
4
5
6
7
8
9
10
11

2.思路

选择排序和插入排序类似，前x个元素已经排序，每次交换第x+1个元素和后续元素中的最小值。

3.代码

void selectSort(int data[],int elementCount){//升序
    int min_index;
    for(int sort_len=0;sort_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

6-22 实验7_14_二分查找

1.题目

设计函数 int BinarySearch(int a[],int n,int key);

利用二分查找算法，在升序排列的数组a的前n个元素中查找值为key的数组元素的下标。如果数组a中存在整数key，则返回下标；否则返回－1。假设数组a中的元素互不相同。

输入与输出要求：

首先输入两个整数n，m，分别代表数组a中元素的个数与需要查找的整数的个数，n（0
1
2
3
4
5
6
7
8
9

函数接口定义：

int BinarySearch(int a[],int n,int key) ;
1

其中 a 、 n和 key 都是用户传入的参数。 a被查找的数组； n 是数组长度； key 是要查找的元素。如果找到，则返回该元素在数组中的下标，否则返回-1。

2.思路

二分查找首先需要数组有序，然后每次都比较中间元素a[mid]和key的大小关系：

• a[mid]==key,查找结束；
• a[mid] > key,说明key只可能存在于前半段数组中，继续查找；
• a[mid] < key,说明key只可能存在于后半段数组中，继续查找

直到查找到key（成功）或者数组大小小于等于0（失败）

3.代码

int BinarySearch(int a[],int n,int key){
    int start=0,end=n-1;//数组的首尾，之后会不断变化
    int mid;//中间下标
    int index=-1;//用来表示查找是否成功
    while(start<=end&&index==-1){//继续查找
        mid=(end+start)/2;
        if(a[mid]==key){//查找成功
            index=mid;
        }
        if(a[mid]>key){//继续查找前半段a[start,mid-1]
            end=mid-1;
        }
        if(a[mid]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20