串旋转杂耍算法 [英] Juggling algorithm of string rotation

问题描述

有几种方法来处理柱旋转。
关于柱旋转深，有三个线性算法。（点击的这里检查）

There are several ways to deal with string rotation.
"Programming Pearls" talks about string rotation in deep, with three linear algorithms.(click here to check it)

第一个是所谓的杂耍算法，这是我花了很多时间去研究它，但我仍然无法理解的作用大公因式扮演它。任何人都可以详细解释一下？

The first one is called "Juggling algorithm", which I spent a lot time to study it, but I still can't understand the role that Great Common Divisor plays in it. Can anybody explain it in detail ?

推荐答案

您通过移动，步长为 D 旋转的元素。这个过程返回一定数量的举动后，这样你需要申请 M 长周期 L = N / M 的总和。

You rotate the elements by moving them in steps of d. This process loops back after a certain number of moves, so that you need to apply m cycles of length l=n/m in total.

→是解决方程的第一个值 LD = 0（MOD N），使<$ C $ç> M 是precisely GCD（N，D）。

l is the first value that solves the equation l.d = 0 (mod n), so that m is precisely gcd(n, d).

Example 1: for n=12, d=3, 3 cycles of length 4:
 0  3  6  9
 1  4  7 10
 2  5  8 11

Example 2: for n=12, d=10, 2 cycles of length 6:
 0 10 8 6 4 2
 1 11 9 7 5 3

这篇关于串旋转杂耍算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！