一个简单的公式

我有一个for循环这给一个给定的整数序列，固定参数N和d：一个简单的公式

int i = 0, j = 0; 
    for (int k=0; k<N; k++) {    
     sequence[k] = i; 
     if ((i += D) >= N) i = ++j; 
    }

我想找到一个简单的公式其再现该序列中，仅在N个视和D（和索引k），如（不起作用）。我努力尝试，但我无法找到总是适用于N和D的任何值的东西！

谢谢！

来源

2010-10-23 WhitAngl

它看起来像它会产生整数0到N-1的置换。你为什么要把它转换成公式？公式和全功能之间可能会有一些妥协。 – 2010-10-23 11:08:41

我用这个排列表有一个大的预计算表，但我的应用程序开始过于内存要求，我试图删除所有表 – WhitAngl 2010-10-23 18:28:42

下面是公式。目前它需要一个条件语句，但如果你想要纯粹的功能表单，你可以通过返回0或1的函数来表达它。

我写它作为Perl函数，以减轻测试（I测试所有N < = 20和d 0与N之间）

sub div { my ($x, $y) = @_; return ($x-$x%$y)/$y }; # whole division 

my $small_subsequence_length = div($N, $D); 
my $big_subsequence_length = $small_subsequence_length + 1; 
my $num_big_subseqiences = $N % $D; 
my $num_total_big_subsequence_numbers = $big_subsequence_length * $num_big_subseqiences; 
my $num_total_small_subsequence_numbers = $N - $num_total_small_subsequence_numbers; 
my $num_small_subseqiences = div($num_total_small_subsequence_numbers, $small_subsequence_length); 

sub sequence { 
    my $k = $_[0]; 
    my ($subsequence_num, subsequence_offset); 

    if ($k > $num_total_big_subsequence_numbers) { 
     my $k2 = $k - $num_total_big_subsequence_numbers; 
     $subsequence_num = div($k2, $small_subsequence_length) + $num_big_subseqiences; 
     $subsequence_offset = ($k2 % $small_subsequence_length) * $D; 
    } else { 
     $subsequence_num = div($k, $big_subsequence_length); 
     $subsequence_offset = ($k % $big_subsequence_length) * $D; 
    } 
    return $subsequence_offset + $subsequence_num; 
}

来源

2010-10-23 10:49:49 DVK

谢谢，我正在尝试！ :) – WhitAngl 2010-10-23 18:36:17

...而且效果很棒:)再次感谢！ – WhitAngl 2010-10-23 18:43:46

我认为有以下应该做的：

 
sequence[0] = 0; 

For k!=0, 
sequence[k] = (sequence[k-1]+D)%N; 
sequence[k] = ((temp=(sequence[k-1]+D))/N)? ++sequence[0]: temp%N;

这里，温度是一个临时变量，推出以避免在RHS表达冗余。

我知道这很复杂，但我确定这是正确的。完成所有值设置后，您可以将序列[0]重置为0，然后您就可以继续。 PS：我试图得到一个封闭的表格。

来源

2010-10-23 09:56:37

编号考虑D = 3，N = 4。序列是0， 3,1,4-。你的序列是0,3,2,1。 – 2010-10-23 09:59:43

是的，我发现它错了一些其他的价值。我会看看我能否得到正确的解决方案。 – 2010-10-23 10:01:51

我已编辑帖子。 – 2010-10-23 10:59:47

转换DVK的函数的C代码，并除去分支：

int sequence(int N, int D, int k) { 
    int subsequence_length = N/D + 1; 
    int num_big_subseqiences = N % D; 
    int num_total_big_subsequence_numbers = subsequence_length * num_big_subseqiences; 

    int small = (k > num_total_big_subsequence_numbers) & 1; 

    k -= num_total_big_subsequence_numbers * small; 
    subsequence_length -= small; 
    subsequence_num = (k/subsequence_length) + num_big_subseqiences * small; 
    subsequence_offset = (k % subsequence_length) * D; 

    return subsequence_offset + subsequence_num; 
}

来源

2010-10-23 12:30:41

非常感谢:)（以及每个花时间思考这个问题的人!!：p） – WhitAngl 2010-10-25 06:55:31

一个简单的公式

回答

相关问题