第15课 数组举例

---

前言

本课介绍的主要内容如下。

1. 兔子繁殖的问题
2. 排序的问题
3. 求最值的问题
4. 铺地毯的问题

---

一、Fibonacci sequence

斐波那契数列数值为：1, 1, 2, 3, 5, 8, 13, 21, 34, …在数学上，这一数列以如下递推的方法定义：F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-2)（n≥2，n∈N），即
$$f(n)=?\begin{array}{ll}0& n=0\\ 1& n=1\\ f(n?1)+f(n?2)& n>1\end{array}$$

二、数据排序

1. STL中的sort()函数与reverse()函数的使用

使用sort()函数对数组全部元素排序。

#include <iostream>
#include <algorithm>
using namespace std;

void print(int a[], int len) {
	for(int i=0; i<len; i++)
		cout << a[i] << ' ';
	cout << endl;
}

int main() {
	int a[] = {6, 2, 4, 9, 5};
	int len = sizeof(a)/sizeof(a[0]);
	sort(a, a+len);
	print(a, len);
	reverse(a, a+len);
	print(a, len);
    return 0;
}

运行程序，输出为

2 4 5 6 9
9 6 5 4 2

sort()函数还可以对数组的部分元素进行排序。

#include <iostream>
#include <algorithm>
using namespace std;

void print(int a[], int len) {
	for(int i=0; i<len; i++)
		cout << a[i] << ' ';
	cout << endl;
}

int main() {
	int a[] = {6, 2, 4, 9, 5};
	int len = sizeof(a)/sizeof(a[0]);
	sort(a+2, a+len);
	print(a, len);
	reverse(a+2, a+len);
	print(a, len);
    return 0;
}

运行程序，输出为

6 2 4 5 9
6 2 9 5 4

sort()函数对数组部分元素排序的语法格式如下。
sort(数组名+起始元素下标, 数组名+终止元素下标+1)

reverse()函数对数组部分元素进行翻转的语法格式如下。
reverse(数组名+起始元素下标, 数组名+终止元素下标+1)

2. STL中的max_element()函数与min_element()函数

1. 用max_element()函数与min_element()函数求数组最大、最小元素值
   示例代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

void print(int a[], int len) {
	for(int i=0; i<len; i++)
		cout << a[i] << ' ';
	cout << endl;
}

int main() {
	int a[] = {6, 2, 4, 9, 5};
	int len = sizeof(a)/sizeof(a[0]);
	cout << *max_element(a, a+len) << endl;//9
	cout << *min_element(a, a+len) << endl;//2
    return 0;
}

2. 用max_element()函数与min_element()函数求数组最大、最小元素下标

max_element()函数求全部数组元素中最大元素下标的语法格式如下。
max_element(数组名, 数组名+最后元素下标+1) - 数组名

min_element()函数求全部数组元素中最小元素下标的语法格式如下。
min_element(数组名, 数组名+最后元素下标+1) - 数组名

#include <iostream>
#include <algorithm>
using namespace std;

void print(int a[], int len) {
	for(int i=0; i<len; i++)
		cout << a[i] << ' ';
	cout << endl;
}

int main() {
	int a[] = {6, 2, 4, 9, 5};
	int len = sizeof(a)/sizeof(a[0]);
	cout << *max_element(a, a+len) << endl;//9
	cout << *min_element(a, a+len) << endl;//2
	
	cout << max_element(a, a+len)-a << endl;//3
	cout << min_element(a, a+len)-a << endl;//1
	
    return 0;
}

max_element()函数与min_element()函数同样可以只对数组的一段元素进行操作。

---

课后练习

1. 顺序查找法

2. 插入排序算法

插入排序法（Insert Sort ）是将数组中的元素逐一与已排序好的数据进行比较，先将前两个元素排序好，再将第三个元素插入适当的位置，也就是说这三个元素仍然是已排序好的，接着将第四个元素加入，重复此步骤，直到排序完成为止。可以看作是在一串有序的记录R1, R2, …, Ri 中插入新记录 R，使得 i +1个记录仍然为排序状态。
插入排序算法步骤如下。

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素（新元素），在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置；
   重复步骤 2~5。

#include <iostream>
#include <iomanip>
using namespace std;

void InsertSort(int arr[], int n){
    int i,j,key;
    for(i = 1; i < n; i++){
        key = arr[i];
        j = i - 1;
        while(j >= 0 && arr[j] > key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

void InverseInsertSort(int arr[], int n) {
    int i,j,key;
    for(i = n - 2; i >= 0; i--) {
        key = arr[i];
        j = i + 1;
        while(j < n &&  key < arr[j]) {
            arr[j-1] = arr[j];
            j++;
        }
        arr[j-1] = key;
    }
}

int main() {
	int beauties[] = { 154, 166, 257, 174, 162, 159, 160, 161, 171 };
	// 获取数组的长度
	int len = sizeof(beauties) / sizeof(beauties[0]);
	InsertSort(beauties, len);
	for (int i = 0; i < len; i++) {
		cout <<setw(7) << beauties[i];
	}
	cout << endl;
    return 0;
}

插入排序适用于列表中大部分元素已经有序的情况，也适用于往已排序数据表中添加新记录后再进行排序的情况。
由于插入排序会造成数据的大量搬移，因此建议在链表上使用。

3. 对两个有序数列进行两路归并排序、

#include<iostream>
#include<iomanip>
using namespace std;

int main() {
	int a[4] = {5, 9, 15, 19};
	int b[5] = {12, 24, 26, 37, 48};
	int len_a = sizeof(a)/sizeof(a[0]);
	int len_b = sizeof(b)/sizeof(b[0]);
	int c[len_a+len_b];
	int i=0, j=0, k=0;
	while(i<len_a && j<len_b) {
		if(a[i]>b[j]) {
			c[k++] = b[j++];
		} else {
			c[k++] = a[i++];
		}
	}
	while(i<len_a) {
		c[k++] = a[i++];
	}
	while(j<len_b) {
		c[k++] = b[j++];
	}

	for(int index=0; index<k; index++) {
		cout << setw(5) << c[index];
	}
	cout << endl;
	return 0;
}

运行程序，输出如下。

    5    9   12   15   19   24   26   37   48

4. 数组计算

编写一个程序，建立具有n个元素的数组，然后按顺序每5个元素计算一个平均值并存入另一个数组，最后将两个数组输出。

#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;

int main() {
	int a[] = {80, 70, 85, 95, 65, 90, 85, 90, 85, 70, 80, 100, 70, 75, 95};
	int len_a = sizeof(a)/sizeof(a[0]);
	int len_b = ceil(len_a/5.0);
	float b[len_b];
	int j, sum;
	for(int i=0; i<len_b; i++) {
		sum=0;
		for(int j=0; j<5; j++) {
			sum += a[5*i+j];
		}
		b[i] = sum/5.0;
	}
	for(int i=0; i<len_a; i++) {
		cout << setw(5) << a[i];
	}
	cout << endl;
	for(int i=0; i<len_b; i++) {
		cout << setw(5) << b[i];
	}
	return 0;
}

运行程序，输出如下。

   80   70   85   95   65   90   85   90   85   70   80  100   70   75   95
   79   84   84

5. 塔形方阵

以n为中心的塔形方阵是一种特殊的方阵，n只在它的中心出现一次，四周位置上的数字从中心逐渐减少直到1，所以塔形方阵的行数和列数都是2n-1。
请编写一个程序，输入一个自然数n（1<=n<=9），构建以n为中心的塔形方阵。

#include<iostream>
#include<iomanip>
using namespace std;

int main() {
	int n,i,j,k;
	cin >> n;
	int a[n][n];
	for(k=0; k<(n+1)/2; k++) 
		for(i=k; i<n-k; i++)
			for(j=k; j<n-k; j++)
				a[i][j] = k+1;
	for(i=0; i<n; i++) {
		for(j=0; j<n; j++) {
			cout << setw(2) << a[i][j];
		}	
		cout << endl;
	}
		
				
	return 0;
}

运行程序，输出如下。

9
 1 1 1 1 1 1 1 1 1
 1 2 2 2 2 2 2 2 1
 1 2 3 3 3 3 3 2 1
 1 2 3 4 4 4 3 2 1
 1 2 3 4 5 4 3 2 1
 1 2 3 4 4 4 3 2 1
 1 2 3 3 3 3 3 2 1
 1 2 2 2 2 2 2 2 1
 1 1 1 1 1 1 1 1 1