C++是一种面向对象编程语言,其中数组是其中一种重要的数据结构。数组是一个数据对象集合,其中每个元素都具有相同的数据类型,并且可以根据其所在的位置(即索引)进行查询和引用。
有一个整数数组，数组元素由n个，用键盘输入，试着将数组的第一个元素移到数组末尾，其余的数组元素依次前移一个位置后顺序输出。
将一个数组中的元素逆序后输出。
有[0, 20]范围的整数N个，统计每个数的个数和不同整数的个数。
从数组中查找某个元素，如果找到，返回该元素在数组中的索引位置（数组下标），否则提示“无此元素”。
均方差一般指标准差。 标准差（Standard Deviation） ，数学术语，是方差（样本中各数据与样本平均数的差的平方和的平均数叫做样本方差）的算术平方根，用σ表示。标准差能反映一个数据集的离散程度。平均数相同的两组数据，标准差未必相同。
σ
=
Σ
i
=
1
n
(
x
i
?
μ
)
2
n
\sigma = \sqrt{\frac{\Sigma^{n}_{i=1}(x_i - \mu)^2}{n}}
σ=nΣi=1n?(xi??μ)2??
简单来说，标准差是一组数据和平均值分散程度的一种度量。一个较大的标准差，代表大部分数值和其平均值之间差异较大；一个较小的标准差，代表这些数值较接近平均值。
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int main() {
const int size = 100;//如果想加大数组，可以改变它
double a[size];
int index = 0;
double sum = 0;
double average, s=0, mu;
cout<<"请输入数据，输入任意字母确定结束输入："<<endl;
while(cin>>a[index++]) {
if(index > size-1) break;
}
cout<<"输入数据为："<<endl;
for(int i=0; i<index-1; i++)
cout << setw(8) << a[i];
cout<<endl;
for(int i=0; i<index-1; i++)
sum += a[i];
average = sum/(index-1); //求平均值
cout << "Average: " << average << endl;
for(int i=0; i<index-1; i++)
s += (a[i]-average)*(a[i]-average);
mu = sqrt(s/(index-1)); //求均方差
cout<<"均方差为：" << mu << endl;
return 0;
}
本题同上一题。
对任意给定的长度为n的已排好序的整型数组，求该数组元素的中位数。
中位数（Median）又称中值，统计学中的专有名词，是按大小顺序排列的一组数据中居于中间位置的数。如果被考察的这组数据的个数为偶数个，通常取最中间的两个数值的平均数作为中位数。
【算法分析】先对列表排序，如果列表的个数是奇数，则中间 那个数就是这组数据的中位数；如果列表的个数是偶数，则中间 那两个数的算术平均值就是这组数据的中位数。
#include <iostream>
//#include <cstdlib>
#include <algorithm>
using namespace std;
//求一个列表的中位数
int main() {
//int arr[] = {66, 93, 36, 48, 96, 83, 45, 60, 90, 53};
int arr[] = {136, 140, 129, 180, 124, 154, 146, 145, 158, 175, 165, 148};
int len = sizeof(arr) / sizeof(arr[0]);
cout<<"length: "<<len<<endl;
for(int i=0; i<len; i++)
cout<<arr[i]<<" ";
cout<<endl;
sort(arr, arr+len); //第一个参数是要排序的数组的起始地址, 第二个参数是结束的地址（最后一个数据的后一个数据的地址）
for(int i=0; i<len; i++)
cout<<arr[i]<<" ";
int m = len/2;
float median;
if(len % 2 == 0) {
median = (arr[m-1] +arr[m])/2.0;
} else {
median = arr[m];
}
cout<<"\nThe median number is: "<<median<<endl;
}
#include <iostream>
#include <iomanip>
using namespace std;
//输出斐波那契数列前40项
int main() {
int n=40;
int f[n];
//构造斐波那契数列
f[0] = 1;
f[1] = 1;
for(int i=2; i<n; i++){
f[i] = f[i-1] + f[i-2];
}
//输出斐波那契数列
for(int i=0; i<n; i++) {
cout << setw(12) << f[i];
if ((i+1) % 5 == 0) { //每行输出10项
cout << endl;
}
}
return 0;
}
运行程序，输出如下。
1 1 2 3 5
8 13 21 34 55
89 144 233 377 610
987 1597 2584 4181 6765
10946 17711 28657 46368 75025
121393 196418 317811 514229 832040
1346269 2178309 3524578 5702887 9227465
14930352 24157817 39088169 63245986 102334155
代码如下（示例）：
#include <iostream>
using namespace std;
// Classic binary search algorithm
// value: the value being searched
int binarySearch(int arr[], int size, int value) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > value) //value in the left part of the array
right = mid - 1;
else if (arr[mid] < value) //value in the right part of the array
left = mid + 1;
else if (arr[mid] == value)
return mid;
}
return -1; // the element is not exist in the array
}
int main(void) {
int arr[] = {2, 3, 4, 10, 10, 10, 10, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, n, x);
if (result == -1) {
printf("Element is not present in the array\n");
} else {
printf("Element is present at index %d\n", result);
}
return 0;
}
运行程序，输出如下。
Element is present at index 4
其实被查找元素10在列表中的第一次出现的索引位置为3，第二次出现的索引位置才是4。因为被查找列表元素是有序的，如果被查找元素在列表中如果有重复出现的话，那么这些相同的元素肯定是相邻的，这就出现了查找某个元素在列表中第一次出现或者最后一次出现的位置的情况。所以，二分查找可以进一步进行有针对性的调整。具体参见下面的代码。
#include <iostream>
using namespace std;
// Classic binary search algorithm
// value: the value being searched
int binarySearch(int arr[], int size, int value) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > value) //value in the left part of the array
right = mid - 1;
else if (arr[mid] < value) //value in the right part of the array
left = mid + 1;
else if (arr[mid] == value)
return mid;
}
return -1; // the element is not exist in the array
}
//寻找arr中值为value的左侧边界，也就是arr中有重复的值，寻找第一个等于value的位置
//Find the left boundary of value in arr, which means there are
//duplicate values in arr, and find the first position equal to the search value
int binarySearchLeft(int arr[], int size, int value) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > value) //value in the left part of the array
right = mid - 1;
else if (arr[mid] < value) //value in the right part of the array
left = mid + 1;
else if (arr[mid] == value) {
if (mid == 0 || arr[mid - 1] != value)
return mid;
else
right = mid - 1; //right boundary contracts to the left (right往左侧收缩)
}
}
return -1; // the element is not exist in the array
}
//寻找arr中值为value的右侧边界，也就是arr中有重复的值，寻找最后一个等于value的位置
//Find the right boundary of value in arr, which means there are
//duplicate values in arr, and find the last position equal to the search value
int binarySearchRight(int arr[], int size, int value) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > value)
right = mid - 1;
else if (arr[mid] < value)
left = mid + 1;
else if (arr[mid] == value) {
if (mid == size - 1 || arr[mid + 1] != value)
return mid;
else
left = mid + 1; //left boundary contracts to the right (left往右侧收缩)
}
}
return -1;
}
int main(void) {
int arr[] = {2, 3, 4, 10, 10, 10, 10, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
cout << binarySearchLeft(arr, n, x) << endl;
cout << binarySearchRight(arr, n, x) << endl;
return 0;
}
运行程序，输出如下
3
7
使用二分查找法查找一个列表中的元素是否存在于另一个列表中。
输入：
包括3行。
第一行2个数：n和q，第一个数n为被查找的列表的长度，第二个数q为查找元素的个数，
第二行是被查找的列表元素，
第三行是要查找的列表元素。
输出：
q行。每一行为被查找元素在被查找的列表中的位置。
#include <iostream>
using namespace std;
// Classic binary search algorithm
// value: the value being searched
int binarySearch(int arr[], int size, int value) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > value) //value in the left part of the array
right = mid - 1;
else if (arr[mid] < value) //value in the right part of the array
left = mid + 1;
else if (arr[mid] == value)
return mid;
}
return -1; // the element is not exist in the array
}
//寻找arr中值为value的左侧边界，也就是arr中有重复的值，寻找第一个等于value的位置
//Find the left boundary of value in arr, which means there are
//duplicate values in arr, and find the first position equal to the search value
int binarySearchLeft(int arr[], int size, int value) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > value) //value in the left part of the array
right = mid - 1;
else if (arr[mid] < value) //value in the right part of the array
left = mid + 1;
else if (arr[mid] == value) {
if (mid == 0 || arr[mid - 1] != value)
return mid;
else
right = mid - 1; //right boundary contracts to the left (right往左侧收缩)
}
}
return -1; // the element is not exist in the array
}
//寻找arr中值为value的右侧边界，也就是arr中有重复的值，寻找最后一个等于value的位置
//Find the right boundary of value in arr, which means there are
//duplicate values in arr, and find the last position equal to the search value
int binarySearchRight(int arr[], int size, int value) {
int left = 0, right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] > value)
right = mid - 1;
else if (arr[mid] < value)
left = mid + 1;
else if (arr[mid] == value) {
if (mid == size - 1 || arr[mid + 1] != value)
return mid;
else
left = mid + 1; //left boundary contracts to the right (left往右侧收缩)
}
}
return -1;
}
int main(void) {
int n, q;
cin >> n >> q;
int arr[n]; //The array being searched
int arr2[q]; //Elements to search for
for(int i=0; i<n; i++) cin >> arr[i];
for(int i=0; i<q; i++) cin >> arr2[i];
int count = sizeof(arr) / sizeof(arr[0]);
for(int i=0; i<q; i++) {
cout << binarySearchLeft(arr, count, arr2[i]) << ' ' << binarySearchRight(arr, count, arr2[i]) << endl;
}
return 0;
}
程序运行的一次输入输出如下。
7 5
1 2 3 4 5 6 7
2 7 4 3 9
1 1
6 6
3 3
2 2
-1 -1
C++数组中的数据，在内存中是连续存放的，每个元素占据相同大小的空间，就像排好队一样，理解这点非常重要。