个人网站建设思路,深圳有哪些做网站公司,洛可可,福州网站seo推广优化文章目录 前言一、数组的概念二、一维数组的定义三、一维数组的初始化四、一维数组的使用及举例1. 元素顺次前移的问题2. 数组元素逆序调整问题3. 统计输入的各个数据的个数 五、课后练习1. 从数组中查找某个元素2. 求一个数组中元素的平均值和均方差3. 编程统计某班某次考试的… 文章目录 前言一、数组的概念二、一维数组的定义三、一维数组的初始化四、一维数组的使用及举例1. 元素顺次前移的问题2. 数组元素逆序调整问题3. 统计输入的各个数据的个数 五、课后练习1. 从数组中查找某个元素2. 求一个数组中元素的平均值和均方差3. 编程统计某班某次考试的平均成绩和均方差4. 求一个列表的中位数5. 使用数组输出Fibonacci数列的前40项6. 二分查找——在一个有序列表中查找某个元素7. 改进的二分查找——在一个有序列表中查找某个元素 总结 前言
C是一种面向对象编程语言,其中数组是其中一种重要的数据结构。数组是一个数据对象集合,其中每个元素都具有相同的数据类型,并且可以根据其所在的位置(即索引)进行查询和引用。 一、数组的概念
二、一维数组的定义
三、一维数组的初始化
四、一维数组的使用及举例
1. 元素顺次前移的问题
有一个整数数组数组元素由n个用键盘输入试着将数组的第一个元素移到数组末尾其余的数组元素依次前移一个位置后顺序输出。
2. 数组元素逆序调整问题
将一个数组中的元素逆序后输出。
3. 统计输入的各个数据的个数
有[0, 20]范围的整数N个统计每个数的个数和不同整数的个数。
五、课后练习
1. 从数组中查找某个元素
从数组中查找某个元素如果找到返回该元素在数组中的索引位置数组下标否则提示“无此元素”。
2. 求一个数组中元素的平均值和均方差
均方差一般指标准差。 标准差Standard Deviation 数学术语是方差样本中各数据与样本平均数的差的平方和的平均数叫做样本方差的算术平方根用σ表示。标准差能反映一个数据集的离散程度。平均数相同的两组数据标准差未必相同。 σ Σ i 1 n ( x i − μ ) 2 n \sigma \sqrt{\frac{\Sigma^{n}_{i1}(x_i - \mu)^2}{n}} σnΣi1n(xi−μ)2 简单来说标准差是一组数据和平均值分散程度的一种度量。一个较大的标准差代表大部分数值和其平均值之间差异较大一个较小的标准差代表这些数值较接近平均值。
#includeiostream
#includeiomanip
#includecmath
using namespace std;
int main() {const int size 100;//如果想加大数组可以改变它double a[size];int index 0;double sum 0;double average, s0, mu;cout请输入数据输入任意字母确定结束输入endl;while(cina[index]) {if(index size-1) break;}cout输入数据为endl;for(int i0; iindex-1; i)cout setw(8) a[i];coutendl;for(int i0; iindex-1; i)sum a[i];average sum/(index-1); //求平均值cout Average: average endl;for(int i0; iindex-1; i)s (a[i]-average)*(a[i]-average);mu sqrt(s/(index-1)); //求均方差cout均方差为 mu endl;return 0;
}3. 编程统计某班某次考试的平均成绩和均方差
本题同上一题。
4. 求一个列表的中位数
对任意给定的长度为n的已排好序的整型数组求该数组元素的中位数。 中位数Median又称中值统计学中的专有名词是按大小顺序排列的一组数据中居于中间位置的数。如果被考察的这组数据的个数为偶数个通常取最中间的两个数值的平均数作为中位数。 【算法分析】先对列表排序如果列表的个数是奇数则中间 那个数就是这组数据的中位数如果列表的个数是偶数则中间 那两个数的算术平均值就是这组数据的中位数。
#include iostream
//#include cstdlib
#include algorithmusing 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]);coutlength: lenendl;for(int i0; ilen; i)coutarr[i] ;coutendl;sort(arr, arrlen); //第一个参数是要排序的数组的起始地址, 第二个参数是结束的地址最后一个数据的后一个数据的地址for(int i0; ilen; i)coutarr[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: medianendl;
}
5. 使用数组输出Fibonacci数列的前40项
#include iostream
#include iomanip
using namespace std;
//输出斐波那契数列前40项
int main() {int n40;int f[n];//构造斐波那契数列 f[0] 1;f[1] 1;for(int i2; in; i){f[i] f[i-1] f[i-2];}//输出斐波那契数列 for(int i0; in; i) {cout setw(12) f[i];if ((i1) % 5 0) { //每行输出10项cout endl;}}return 0;
}运行程序输出如下。 1 1 2 3 58 13 21 34 5589 144 233 377 610987 1597 2584 4181 676510946 17711 28657 46368 75025121393 196418 317811 514229 8320401346269 2178309 3524578 5702887 922746514930352 24157817 39088169 63245986 1023341556. 二分查找——在一个有序列表中查找某个元素
代码如下示例
#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 arrayright mid - 1;else if (arr[mid] value) //value in the right part of the arrayleft 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 arrayright mid - 1;else if (arr[mid] value) //value in the right part of the arrayleft 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 arrayright mid - 1;else if (arr[mid] value) //value in the right part of the arrayleft mid 1;else if (arr[mid] value) {if (mid 0 || arr[mid - 1] ! value)return mid;elseright 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;elseleft 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
77. 改进的二分查找——在一个有序列表中查找某个元素
使用二分查找法查找一个列表中的元素是否存在于另一个列表中。 输入 包括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 arrayright mid - 1;else if (arr[mid] value) //value in the right part of the arrayleft 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 arrayright mid - 1;else if (arr[mid] value) //value in the right part of the arrayleft mid 1;else if (arr[mid] value) {if (mid 0 || arr[mid - 1] ! value)return mid;elseright 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;elseleft 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 searchedint arr2[q]; //Elements to search forfor(int i0; in; i) cin arr[i];for(int i0; iq; i) cin arr2[i];int count sizeof(arr) / sizeof(arr[0]);for(int i0; iq; 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数组中的数据在内存中是连续存放的每个元素占据相同大小的空间就像排好队一样理解这点非常重要。
