提问人：Homer Jay Simpson 提问时间：11/7/2023 最后编辑：Jarod42Homer Jay Simpson 更新时间：11/9/2023 访问量：70
如何在 c++ 中计算右旋转数组的最小元素乘积？[关闭]
How can I calculate the minimum element-wise product of a right rotated array in c++? [closed]
问：
考虑一个 N 个整数的一维数组 A。A 的元素位积等于 Σ A [ k ] * k ，即它是当 将数组的每个元素乘以其位置。例如，阵列的元素位置乘积 ̈
A = [5， 3， 2， 6， 4， 1] 是： 5 * 1 + 3 * 2 +2 * 3 + 6 * 4 + 4 * 5 + 1 * 6 = 67。
将数组 A 旋转 p 位置（其中 0 ≤ p < N）通过获取其第一个 p 元素并将它们放在末尾来转换 A。例如，将 A = [5， 3， 2， 6， 4， 1] 旋转 2 位得到 [2， 6， 4， 1， 5， 3]。
我想用 c++ 编写一个函数，该函数接受 A 和 N 作为参数，并使用最小元素位置乘积计算数组 A 的 p=1 的右旋转。该函数应在此旋转后打印数组 A 的元素并返回相应的乘积。
示例 1：（N = 6） A = [5， 3， 2， 6， 4， 1]
min_elem_pos_prod（A， N）
输出：
产品 ：64 阵列：6 4 1 5 3 2
| 迭 代 | ||||||
|---|---|---|---|---|---|---|
| p=0 ：67 | 5 | 3 | 2 | 6 | 4 | 1 |
| p=1 ：76 | 3 | 2 | 6 | 4 | 1 | 5 |
| p=2 ：73 | 2 | 6 | 4 | 1 | 5 | 3 |
| p=3 ：64 | 6 | 4 | 1 | 5 | 3 | 2 |
| p=4 ：79 | 4 | 1 | 5 | 3 | 2 | 6 |
| p=5 ：82 | 1 | 5 | 3 | 2 | 6 | 4 |
我有右旋转数组的函数：
#include <iostream>
void rotateRight(int arr[], int size) {
int p = 1 ;
int end = size - 1 ;
for (int i = 0; i < p; i++) {
int temp = arr[end];
for (int j = end; j > 0; j--) {
arr[j] = arr[j - 1];
}
arr[0] = temp;
}
}
和元素明智的产品：
int elementWiseProduct(int arr[], int N) {
int sum = 0;
for (int i = 0,j=1; i < N; ++i,j++) {
sum += arr[i]*j;
}
return sum;
}
我的问题是我怎样才能将这两个或其他函数结合起来来输出所需的结果？
答：
1赞
Olivier Samson
11/7/2023
#1
好的，所以 N-1 是你在得到原始数组之前可以做的最大旋转量，所以让我们简单地这样做（并修改你的 rotateRight（） 方法以接受 p 作为参数）：
// Calculate product without any rotation
int product = elementWiseProduct(A, N);
int numberOfRotations = 0;
// Calculate product for all possible rotations
// Replace values initialized above if product is smaller
for (int i = 1; i <= N - 1; i++) {
// Rotate once as your current implementation does
rotateRight(A, N, 1);
// Get the element-wise product of this rotation
int newProduct = elementWiseProduct(A, N);
if (newProduct < product) {
product = newProduct;
numberOfRotations = i;
}
}
// Rotate array to get to the correct rotation
// Rotation needed is one more since we need to cycle
// back to original array with one rotation
rotateRight(A, N, numberOfRotations + 1);
// Print array and minimum product
...
评论
5 * 1 + 3 * 2 +2 * 3 + 6 * 4 + 4 * 5 + 1 * 6std::size_t bestP = 0; int bestScore = elementWiseProduct(A, N); for (int p = 1; p != N; ++p) { rotateRight(A, N); if (auto score = elementWiseProduct(A, N); score < bestScore) { bestScore = score; bestP= p; }}?elementWiseProduct顺便说一句，是错误的：product += (i+1) * a[i];if