第15课 数组举例

2024-01-02 17:59:28


前言

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

  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 ) = { ? 0 n = 0 ? 1 n = 1 ? f ( n ? 1 ) + f ( n ? 2 ) n > 1 f(n)= \begin{cases} \ 0 & n=0\\ \ 1 & n=1\\ \ f(n-1)+f(n-2) & n>1 \end{cases} f(n)=? ? ???0?1?f(n?1)+f(n?2)?n=0n=1n>1?

二、数据排序

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;
}

  1. 用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

文章来源:https://blog.csdn.net/red2brick/article/details/135324354
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。