当前位置: 面试刷题>> 轮转函数 (经典算法题500道)


题目描述补充

题目:轮转函数(Rotation Function)

给定一个长度为 n 的数组 A,我们需要定义一个轮转函数 F,该函数接受一个索引 k0 <= k < n)作为参数,并计算数组 A 在向右轮转 k 个位置后,新数组中所有元素的索引和。即,对于每个元素 A[i],在轮转后它的新索引为 (i+k) % n,我们需要计算所有新索引与原数组值乘积的和。

具体地,轮转函数 F(k) 定义为:

$$ F(k) = \sum_{i=0}^{n-1} A[i] \times ((i+k) \mod n) $$

其中,% 表示取模运算。

示例

给定数组 A = [1, 2, 3, 4, 5],计算 F(0), F(1), F(2) 的值。

  • F(0) = 1*0 + 2*1 + 3*2 + 4*3 + 5*4 = 0 + 2 + 6 + 12 + 20 = 40
  • F(1) = 1*1 + 2*2 + 3*3 + 4*0 + 5*1 = 1 + 4 + 9 + 0 + 5 = 19
  • F(2) = 1*2 + 2*3 + 3*4 + 4*1 + 5*2 = 2 + 6 + 12 + 4 + 10 = 34

示例代码

PHP 示例

function F(array $A, $k) {
    $n = count($A);
    $sum = 0;
    for ($i = 0; $i < $n; $i++) {
        $newIndex = ($i + $k) % $n;
        $sum += $A[$i] * $newIndex;
    }
    return $sum;
}

// 示例使用
$A = [1, 2, 3, 4, 5];
echo F($A, 0) . "\n"; // 输出 40
echo F($A, 1) . "\n"; // 输出 19
echo F($A, 2) . "\n"; // 输出 34

Python 示例

def F(A, k):
    n = len(A)
    return sum(A[i] * ((i + k) % n) for i in range(n))

# 示例使用
A = [1, 2, 3, 4, 5]
print(F(A, 0))  # 输出 40
print(F(A, 1))  # 输出 19
print(F(A, 2))  # 输出 34

JavaScript 示例

function F(A, k) {
    const n = A.length;
    let sum = 0;
    for (let i = 0; i < n; i++) {
        const newIndex = (i + k) % n;
        sum += A[i] * newIndex;
    }
    return sum;
}

// 示例使用
const A = [1, 2, 3, 4, 5];
console.log(F(A, 0)); // 输出 40
console.log(F(A, 1)); // 输出 19
console.log(F(A, 2)); // 输出 34

码小课 网站中有更多关于算法和数据结构的内容分享给大家学习,欢迎访问以获取更多知识和练习。

推荐面试题