arrays - 旋转数组和循环次数混淆

Question

问题是写一个函数 rotate(ar[], d, n) 将大小为 n 的 arr[] 旋转 d 个元素。解决方案(杂耍法)在这里http://www.geeksforgeeks.org/array-rotation/ .令我困惑的是为什么循环数是n和d的gcd。有谁知道例子证明吗？

Answer 1

why the number of cycles is gcd of n and d

这样循环数就可以完美地平分两者!如果“c”是涉及的循环数，则 n 应该可以被 c 完全整除，即 n = xc，类似地，d = yc。

现在，在算法中，x 是数组中的集合数，y 是执行的步骤(或迭代)数。在给定的示例中检查并确认这一点。

选择 GCD 的主要目的是让 x 和 y 是整数而不是一些浮点值。