простая формула - PullRequest
Новая
       10

простая формула

1 голос
/ 23 октября 2010

У меня есть цикл 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), например sequence[k] = D*(k%D)+ k/D (которая не работает). Я очень старался, но я просто не могу найти то, что всегда работает для любых значений N и D!

Спасибо!

Ответы [ 3 ]

1 голос
/ 23 октября 2010

Вот формула. На данный момент требуется условный оператор, но вы всегда можете выразить его через функцию, возвращающую 0 или 1, если вам нужна чистая функциональная форма.

Я написал это как функцию Perl, чтобы упростить тестирование (я тестировал все N <= 20 и D от 0 до N) </p> 

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;
}
1 голос
/ 23 октября 2010

Преобразовал функцию 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;
}
0 голосов
/ 23 октября 2010

Я думаю, что должно подойти следующее: 

sequence[0] = 0;

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

Здесь temp - временная переменная, введенная во избежание избыточности в выражении на RHS.

Я знаю, что это сложно, ноЯ уверен, что это правильно.После того, как все значения установлены, вы можете сбросить последовательность [0] на 0, и все.

PS: Я пытаюсь получить закрытую форму.

...