一個簡單的公式

我有一個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

一個簡單的公式

回答

相關問題