C++程序 数组的平均数计算(迭代和递归)
给定一个数组,任务是找到该数组的平均值。平均值是数组元素之和除以元素数。
示例:
输入: arr[] = {1, 2, 3, 4, 5}
输出: 3
元素之和为1 + 2 + 3 + 4 + 5 = 15,
元素总数为5。
所以平均值是15/5 = 3
输入: arr[] = {5, 3, 6, 7, 5, 3}
输出: 4.83333
元素之和是5 + 3 + 6 + 7 + 5 + 3 = 29
元素总数为6。
所以平均值是29/6 = 4.83333。
迭代方法:
迭代程序很简单。我们需要求和并将其除以元素的总数。
// C++ program to calculate average
// of array elements
#include <iostream>
using namespace std;
// Function that return average
// of an array.
double average(int a[], int n)
{
// Find sum of array element
int sum = 0;
for (int i=0; i<n; i++)
sum += a[i];
return (double)sum/n;
}
// Driver code
int main()
{
int arr[] = {10, 2, 3, 4,
5, 6, 7, 8, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout << average(arr, n) << endl;
return 0;
}
输出
6
时间复杂度: O(n),上述代码的时间复杂度为O(n),因为它循环遍历所有数组元素来计算总和。
空间复杂度: O(1),空间复杂度为O(1),因为未使用额外的空间。
递归方法:
首先,将元素的索引作为一个额外参数传递,然后递归计算和。计算出和后,将其除以n。
// C ++程序计算平均值
//的数组元素
# include <iostream>
using namespace std;
//递归地计算
double avgRec(int a[],
int i, int n)
{
//最后一个元素
if (i == n-1)
return a[i];
//当索引为0,将之前计算的和除以n。
if (i == 0)
return ((a[i] + avgRec(a, i+1,
n))/n);
//计算和
return (a[i] + avgRec(a, i+1, n));
}
// 返回数组平均值的函数
double average(int a[], int n)
{
return avgRec(a, 0, n);
}
// 主函数
int main()
{
int arr[] = {10, 2, 3, 4,
5, 6, 7, 8, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout << average(arr, n) << endl;
return 0;
}
输出
6
时间复杂度: O(n)
辅助空间: O(n)