查找循环数组中任意两个索引之间的中间索引

Question

我有一个数组和三个索引：

var arr = ['a', 'b', 'c', 'd'];
var f = 0; // first element
var l = arr.length - 1; // last element
var c = 0; // current element

我正在尝试编写一个函数，使索引 c 在数组中循环。要求是它永远不会达到索引 l。所以，每当c达到某个值时，f和l也需要增加。

我认为作为 c 极限的合理值是 f 和 l 之间的中间点。我写的函数是这样的：

var mod = function(x, m) {
    var r = x%m;
    return r<0 ? r+m : r;
}

while (true) {
    console.log('f', f, 'l', l, 'c', c);
    if (c == l) {
       console.log('error');
    }

    c = mod(c + 1, arr.length);

   if (c > mod(l - f, arr.length) / 2) {
      f = mod(f + 1, arr.length);
      l = mod(l + 1, arr.length);
   }
}

这显然行不通。 modulo 运算符是否有一个很好的简单公式来获得我想要的结果，或者方法完全错误？

这里有一个 fiddle 可以试试：https://jsfiddle.net/wku37h9e/2/

编辑：解释这样做的目的会有点长。假设数组中存储了我必须不断移动的外部元素的位置。当 c 接近 l 时，我推进所有索引。图形上是这样的：

1. [f|c] [   ] [   ] [ l ]
2. [ f ] [ c ] [   ] [ l ]
3. [ l ] [ f ] [ c ] [   ] // here I start moving things around
4. [   ] [ l ] [ f ] [ c ]
5. [ c ] [   ] [ l ] [ f ]
6. [ f ] [ c ] [   ] [ l ]

等等。数组中的元素越多，索引之间的距离就越远。

我还使用了不同于正常版本的 mod 来考虑负数。

我希望现在更清楚一些

Answer 1

我不确定我是否理解 - 当我定义所有工作的 mod 函数时：

function test() {
    var i=0;
    var arr = ['a', 'b', 'c', 'd'];
    var f = 0; // first element
    var l = arr.length - 1; // last element
    var c = 0; // current element
    while (true && i < 1000) {
        ++i;
        console.log('f', f, 'l', l, 'c', c);
        if (c == l) {
           console.log('error');
           break;
        }

        c = mod(c + 1, arr.length);

        if (c > mod(l - f, arr.length) / 2) {
           f = mod(f + 1, arr.length);
           l = mod(l + 1, arr.length);
        }
    }
}
function mod(a,b) { return a % b;}

似乎通过可能的值循环 c，并且 c 与 l 的（不断重新计算的）值永远不相同......但我不明白你的算术重新尝试申请 f 和 l

Answer 2

我只计算l，数组长度的一半加上c。 f 是下一个索引。所有数字都是正数。

                            c   f   l
1. [ c ] [   ] [ l ] [ f ]  0   3   2  l = length / 2 + c, f = l + 1  both mod length
2. [ f ] [ c ] [   ] [ l ]  1   0   3
3. [ l ] [ f ] [ c ] [   ]  2   1   0
4. [   ] [ l ] [ f ] [ c ]  3   2   1
5. [ c ] [   ] [ l ] [ f ]  0   3   2
6. [ f ] [ c ] [   ] [ l ]  1   0   3

var arr = ['a', 'b', 'c', 'd'],
        c, f, l;

for (c = 0; c < arr.length; c++) {
    l = (arr.length / 2 + c) % arr.length;
    f = (l + 1) % arr.length;
    document.write('c:' + c + ' f: ' + f + ' l: ' + l + '<br>');
}

Answer 3

A reasonable value to work as a limit for c I thought would be the middle point between f and l

在 mod len

中求两个值 low 和 high 之间的平均值

function midPoint(low, high, len) {
    var mid;
    low %= len;
    high %= len;
    while (low < 0) low += len; // these two lines are the
    while (high < low) high += len; // most important for direction
    mid = (low + high) / 2; // mean average
    mid %= len; // convert back to our mod
    return mid;
}

也有

// works as expected beyond range of mod
midPoint( 1, -1, 9); // middle of 1..8 (mod 9) = 4.5
midPoint(-7,  5, 9); // middle of 2..5 (mod 9) = 3.5
midPoint(-6, 12, 9); // middle of 3..3 (mod 9) = 3
// and
midPoint( 2,  5, 9); // middle of 2..5 (mod 9) = 3.5
midPoint( 5,  2, 9); // middle of 5..2 (mod 9) = 8 (we went the other way around)

在整个计算完成之前，您实际上不必强制执行 mod，所以如果您真的想要，可以执行以下操作，但您 会在循环中失去方向

function midPoint(A, B, len) {
    var mid;
    mid = (A + B) / 2; // mean average
    mid %= len; // convert back to our mod
    while (mid < 0) mid += len; // always positive
    return mid;
}

但是请注意这里

midPoint(-6, 3, 9); // middle of 3..3 (mod 9) = 7.5
midPoint( 3, 3 + 0 * 9, 9); // middle of 3..3 (mod 9) = 3
midPoint( 3, 3 + 1 * 9, 9); // middle of 3..3 (mod 9) = 7.5
midPoint( 3, 3 + 2 * 9, 9); // middle of 3..3 (mod 9) = 3

即3..3 (mod 9) 的中点既是 3 又是 7.5，这是 true，但是我们绕哪边现在走了取决于 k（其中 B - A = k * len + a）

查找循环数组中任意两个索引之间的中间索引

Finding the middle index between any two indexes in a circular array

javascript

arrays

modulo