如何在C++中实现求右旋转数组最小元素位置乘积的功能？

问题定义 #

• 元素位置乘积：对于包含N个整数的一维数组A，其值为所有元素与对应位置（从1开始）的乘积之和，公式为 $\Sigma A[k] * k$。例如数组[5,3,2,6,4,1]的元素位置乘积为 $51+32+23+64+45+16=67$。
• 数组右旋转p个位置：将数组前p个元素移到末尾。例如数组[5,3,2,6,4,1]右旋转2个位置后得到[2,6,4,1,5,3]。

需求 #

编写C++函数min_elem_pos_prod，接收数组A和N作为参数，找到使得元素位置乘积最小的右旋转p次（$0≤p<N$）后的数组，打印该数组并返回对应的乘积。示例中N=6，A=[5,3,2,6,4,1]，调用函数后需输出乘积64和数组6 4 1 5 3 2。

现有代码片段 #

单次右旋转函数 #

#include <iostream>

void rotateRight(int arr[], int size) {
    int end = size - 1 ;
    int temp = arr[end];
    for (int j = end; j > 0; j--) {
        arr[j] = arr[j - 1];
    }
    arr[0] = temp;
}

（注：原代码中多余的循环外层已移除，该函数仅负责单次右旋转1位）

元素位置乘积计算函数 #

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. 遍历所有可能的旋转次数p（0到N-1），对每个旋转后的数组计算元素位置乘积。
2. 全程记录最小的乘积值，以及对应的数组状态。
3. 由于rotateRight是原地修改数组，需保存原数组副本避免影响后续计算；每次找到更优解时，复制当前数组状态作为最佳结果。

完整实现代码 #

#include <iostream>
#include <cstring> // 用于memcpy函数

void rotateRight(int arr[], int size) {
    int end = size - 1 ;
    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;
}

int min_elem_pos_prod(int A[], int N) {
    // 保存原数组副本，用于后续恢复
    int originalArr[N];
    memcpy(originalArr, A, sizeof(int)*N);
    
    // 初始化最小乘积和最佳数组为原数组状态
    int minProduct = elementWiseProduct(A, N);
    int bestArr[N];
    memcpy(bestArr, A, sizeof(int)*N);
    
    // 遍历p=1到N-1的旋转情况（p=0对应原数组）
    for (int p = 1; p < N; p++) {
        rotateRight(A, N);
        int currentProduct = elementWiseProduct(A, N);
        
        // 更新最小乘积和对应数组
        if (currentProduct < minProduct) {
            minProduct = currentProduct;
            memcpy(bestArr, A, sizeof(int)*N);
        }
    }
    
    // 打印结果
    std::cout << "最小乘积：" << minProduct << std::endl;
    std::cout << "对应的数组：";
    for (int i = 0; i < N; i++) {
        std::cout << bestArr[i] << " ";
    }
    std::cout << std::endl;
    
    // 恢复原数组（可选，根据需求决定是否保留原数组初始状态）
    memcpy(A, originalArr, sizeof(int)*N);
    
    return minProduct;
}

// 测试示例
int main() {
    int arr[] = {5,3,2,6,4,1};
    int N = sizeof(arr)/sizeof(arr[0]);
    min_elem_pos_prod(arr, N);
    return 0;
}

代码说明 #

• 使用memcpy复制数组，确保原数组不被破坏，同时精准保存最佳状态的数组。
• 遍历所有旋转次数，每次旋转后计算乘积并对比更新最小值。
• 测试示例运行后会输出：

  最小乘积：64
  对应的数组：6 4 1 5 3 2 
  

  完全符合需求要求。

内容的提问来源于stack exchange，提问作者Homer Jay Simpson