在递归公式中寻找位置函数

Question

首先，请注意，我的英语在这里并不是最好的。如果有人有兴趣帮助我解决这个问题，并希望我更详细的东西，不要激动地问更多的细节。

一个特定的解决方案，在任何标记给定的语言是非常赞赏的。即使用公式来解决更多的问题也是这个问题的目标。

谢谢

让定义序列规则SR，一个固定的整数序列：

高级= (a，b，c，d，.)

示例

SR = (1, 2, 3, 5)

让我们定义移位序列规则SS由SR得到的序列如下：

SS = (a-0，，，，.-d)

示例

(1-0, 2-1, 3-2, 5-3) = (1, 1, 1, 2)

移位序列规则SS应根据以下递归公式计算到输出序列OS：

OS(n) = 0，n=0

OS(n) = OS(n-1) + SS(i)，n>0

其中我是n在当前子群SS中的位置。

示例

OS(n) = (1, 2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 15..)

在哪里n=(1,2,3,4,5,6,7,8,9,10,11,12,..)。

OS(0) = 0
OS(1)  = OS(0)  + SS(1) = 0 + 1  = 1
OS(2)  = OS(1)  + SS(2) = 1 + 1  = 2
OS(3)  = OS(2)  + SS(3) = 2 + 1  = 3
OS(4)  = OS(3)  + SS(4) = 3 + 2  = 5
OS(5)  = OS(4)  + SS(1) = 5 + 1  = 6
OS(6)  = OS(5)  + SS(2) = 6 + 1  = 7
OS(7)  = OS(6)  + SS(3) = 7 + 1  = 8
OS(8)  = OS(7)  + SS(4) = 8 + 2  = 10
OS(9)  = OS(8)  + SS(1) = 10 + 1 = 11
OS(10) = OS(9)  + SS(2) = 11 + 1 = 12
OS(11) = OS(10) + SS(3) = 12 + 1 = 13
OS(12) = OS(11) + SS(4) = 13 + 2 = 15

实际上我缺少的是(无法得到)是n在相关的移位组中的当前位置，只给出n，这样：

pos(n)=i -> S(pos(n)) = S(i)

所以我终于可以写了

OS(0) =0

OS(n) = OS(n-1) + SS(pos(n))

到目前为止，我得到的是移动组当前指数的公式。我怀疑它可以帮助我确定想要的位置公式pos(n)，但不知道如何确定：(

组索引可以表示为：

G(N)=上限(n/D(SS))

其中D( SS )是SS的维数，即序列规则中元素的个数。

示例

例如，$n$序列的范围从1到12。第4维的移动组(1,1,1,2)的数目使1->1映射到OS(n)是3 = 12/4。

n=9的分组索引可以计算为：

 G(9) = ceiling(n/D(SR)) = ceiling(9/4) = 3

最终答案

%操作符的使用是我所缺少的。最后的递归公式是：

OS(n) = 0，n=0

OS(n) = OS(n-1) + SS((n + D(SR)-1) % D(SR) + 1)，n>0

或者使用纯数学公式(以及上面对组索引的定义)：

OS(n) = 0，n=0

OS(n) = OS(n-1) + SS((n + D(SR)-1 - (D(SR) * G(n)) + 1)，n>0

谢谢@GARETH

Answer 1

这个问题很难理解，但我认为您正在寻找操作。

序列SS有4个元素，因此pos(n)为n模4。

这个操作可以用许多编程语言(包括C#和Ruby)由%操作符计算，在Haskell中由mod函数计算。

如果需要模数在1到4之间，而不是0到3之间，请使用以下表达式：

(n + 3) % 4 + 1