По мотивам двойного хеширования;)

← →
default © (2006-10-20 14:09) [0]

4 1 5 2 6 3 7
a,b,c,d,e,f,g

пример
массив из 7 элементов
стартовый элемент - b
шаг - 2

идёт циклический проход по элементам массива начиная от стартового элемента с заданным шагом до тех пор пока не встретится элемент который уже обходили

вопрос
каковы должны быть длина массива и шаг чтобы мы обошли все элементы массива до первого повторения и вообще возможно ли такое

← →
MBo © (2006-10-20 14:29) [1]

???
разные простые числа.
тогда (NStep * StepSize) mod Len = 0 только при NStep = Len, т.е., начав с первого элемента, попадаем на него только через Len шагов.
Если массив развернуть в ряд
abcabcabc(abc), то видно, что начав с любого номера, мы попадем на него тоже через Len шагов, из чего следует, что все элементы будут посещены, и единожды

← →
Думкин © (2006-10-20 14:33) [2]

Взаимно просты они должны быть?

← →
MBo © (2006-10-20 14:35) [3]

оффтоп по поводу твоей недавней ветки:
нашел в своих закромах "tips" ветку со старого форума algolist c сообщением
На мой взгляд, решение статической кольцевой очереди на основе массива с указателем начала и длины очереди - более рационально. Буфер очереди используется полностью, указатель авляется целым индексом массива
;)

Думкин © (20.10.06 14:33) [2]
верно, но это нужно ещё доказать
но лучше Вам не надо пока этого делать, а то ветка быстро станет не актуальной
MBo © (20.10.06 14:35) [3]
интересно:)

MBo © (20.10.06 14:35) [3]
с одной стороны хорошо, что эта идея возникла не у одного меня с другой плохо ибо я в итоге не оригинален:)

p.s. хотя MBo практически всё рассказал, но не всё:)

этот вопрос возник при рассмотрении двойного хеширования
там когда зондирование идёт было сказано, что если длина хеш-таблицы есть простое число, то все элементы таблицы будут обходиться
у Кнута сказано про взаимную простоту, но без пояснений

По мотивам двойного хеширования;) Найти похожие ветки