Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
И еще немного о линейках Голомба. 24.10.02 22:36 Число просмотров: 1068
Автор: Grom [ HZ Ural ] <Gusynin Oleg> Статус: Member
|
Мне стало интересно, ведь если замкнуть последний элемент линейки с первым, то мы получим нечто, что я для себя называю круговой линейкой Голомба (ну или замкнутой), при условии, что все расстояния разные. (например для 4 делений, получившаясяя линейка - 1-2-4). Кто-нибудь исследовал такие линейки, и если да. то где этоможно посмотреть?
А пока предлагаю некоторые свойства круговых линеек Голомба, которые я сам определил (это значит, что некоторые из них могут быть ошибочными :):
• Количество различных расстояний равно (n-1)*(n-2)+1, где n - количестко делений (Из этого следует, что минимальная возможная круговая линейка с n делениями имеет длину (n-1)*(n-2)+1)
• Оптимальные линейки. 2: 1, 3: 1-2, 4: 1-2-4, 5: 1-2-6-4, 6: 1-3-10-2-5, 7: 1-2-5-4-6-13 (или 1-2-7-4-12-5). Длина каждой из приведенных линеек равна (n-1)*(n-2)+1, при данном количестве делений, следовательно они оптимальны.
• Размыкание любого звена круговой линейки приводит ее к обычной линейки Голомба. Таким образом, из круговой линейки с n делениями можно получить n обычных линеек.
Теория: Линейка является круговой линейкой Голомба, если всевозможные разомкнутые линейки, полученные из данной, являются линейками Голомба.
Могу также поделиться исходниками на паскале по поиску и определению таких линеек.
|
- И еще немного о линейках Голомба. - Grom [ HZ Ural ] 24.10.02 22:36 [1068]
|
|
|