)给定 n 个整数 a1, a2, … , an ,求它们两两相乘再相加的和,即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an.
时间: 2023-07-30 13:10:38 浏览: 61
这个问题可以通过暴力枚举的方法解决,即对于每一个数,都与它后面的数进行相乘并相加。具体实现可以使用双重循环来枚举,时间复杂度为 O(n^2)。
以下是用 Python 实现的代码:
```python
def sum_of_products(nums):
n = len(nums)
res = 0
for i in range(n):
for j in range(i+1, n):
res += nums[i] * nums[j]
return res
```
还有一种更加高效的做法,可以将上式拆开,得到:
S = (a1 + a2 + … + an-1 + an)^2 - (a1^2 + a2^2 + … + an-1^2 + an^2)
这样我们只需要先计算出所有数的平方和,和它们的和,再套用上述公式即可。这种方法的时间复杂度为 O(n)。
以下是用 Python 实现的代码:
```python
def sum_of_products(nums):
n = len(nums)
sum_nums = sum(nums)
sum_squares = sum([x*x for x in nums])
res = sum_nums * sum_nums - sum_squares
return res // 2
```
相关问题
蓝桥杯真题 求和 给定 n 个整数 a1· a2, · · · , an,求它们两两相乘再相加的和python
以下是求解蓝桥杯真题的Python代码:
```python
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
for j in range(i+1, n):
ans += a[i] * a[j]
print(ans)
```
3)给定 n 个整数 a1, a2, … , an ,求它们两两相乘再相加的和,即 S = a1 · a2 + a1 · a3 + · · · + a1 · an + a2 · a3 + · · · + an-2 · an-1 + an-2 · an + an-1 · an. 样例输入
这里是使用 C 语言编写的给定 n 个整数求两两相乘再相加的和的代码:
```c
#include <stdio.h>
int main()
{
int n, a[100], i, j, sum = 0;
printf("请输入整数个数n:");
scanf("%d", &n);
printf("请输入%d个整数:", n);
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (i = 0; i < n - 1; i++) {
for (j = i + 1; j < n; j++) {
sum += a[i] * a[j]; // a[i]和a[j]相乘,累加到sum中
}
}
printf("两两相乘再相加的和为:%d\n", sum);
return 0;
}
```
以上代码中,我们先输入整数个数n和n个整数a1, a2, … , an,然后使用两层循环遍历每个数对,将其两两相乘再相加的结果累加到sum中。最后输出sum的值作为答案。
例如,如果输入n为4,整数为1、2、3、4,那么两两相乘再相加的和为:1x2 + 1x3 + 1x4 + 2x3 + 2x4 + 3x4 = 20。