theJam.ru

Логические задачиОчень трудная задача

11 ноября 2009 | Добавил: atlakatl

В 90-ые столкнулся с проблемой. Решил её не оптимально. А как найти приемлемое решение, так и не знаю.
Итак, имеется протяжённое сопротивление. В некоторых его частях выведены N клемм. Нужно расположить их на сопротивлении так, чтобы при последовательном присоединении к каждой паре получался наиболее равномерное распределение по сопротивлению. Не понятно? – конечно, лучше не получается. Понятнее будет на примерах:

Пример 1:
Длина сопротивления 3. Первая клемма на 0, вторая на 1, третья на 3. Соединяя каждую пару, получаем: кл1-кл2=1, кл2-кл3=2, кл1-кл3=3
Пример 2:
Длина сопротивления 6. Первая клемма на 0, вторая на 1, третья на 4, четвёртая на 6. кл1-кл2=1, кл3-кл4=2, кл2-кл3=3, кл1-кл3=4, кл2-кл4=5, кл1-кл4=6
Абсолютно равномерное распределение! При 5 клеммах должны получаться числа от 1 до 10 и т.д. Но не получается!
Потому зададимся каким-нибудь критерием. Например, чтобы максимальное отклонение от натурального ряда было минимально. Или был бы минимален квадрат отклонения. Что удобнее. Какой должна быть процедура поиска? Кроме случайного перебора ничего не вырисовывается.

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку
Метки

Комментариев: 6

  1. SoVictor пишет:

    Задача знаменита и не нова, обычно она даётся так:
    Сделать минимальное количество засечек на линейке длиной N, чтобы этой линейкой можно было измерить любое расстояние от 1 до N
    Сущесвтуют вариации этой задачи... должен сказать, что для произвольного N её не встречал :)

  2. atlakatl пишет:

    Задача в формулировке SoVictor-а решается для конкретных N довольно просто. Так для измерения целых длин от 1 до 10 требуется линейка длиной 10 с насечками на 1, 5, 6, 8, - один из минимальных вариантов. В этом варианте есть и дублирующиеся пары. Так, 2=10-8=8-6 и т.д.

    Уточняю мою формулировку. Если на сопротивлении имеется N клемм, то возможно измерить K=N*(N-1)/2 значений. Например, при 5 клеммах возможно измерить 10 значений. Нужно найти такое расположение клемм, чтобы разности всевозможных пар обеспечивали минимальное отклонение от целого ряда чисел от 1 до K. Формулировку минимальности не конкретизирую: она может зависеть от метода решения.

    В случае численного решения имеем классическую многоэкстремальную задачу, где число минимумов пропорционально (K-1)! – в смысле факториал. Без дополнительных соображений для больших K найти глобальный минимум перебором невозможно за приемлемое время.

  3. Kot пишет:

    а можно так соеденять?
    __П__П_П__ т.е. вторую с третьей,четветую с 7й, т.е. что бы сопротивление было 1-2 + 3-4 + 7-Н??

  4. atlakatl пишет:

    что бы сопротивление было 1-2 + 3-4 + 7-Н
    Действительно, так можно получить дополнительные варианты значений сопротивления. Но меня интересуют соображения по нахождению именно простейших пар, создаваемых подключением по двум клеммам.

  5. atlakatl пишет:

    Александр:
    Линейка Голомба похожа на эту задачу, но всё-таки другая.

    Так мы все здесь математики, только непрофессиональные. )

Комментировать!

Друзья, обращаю ваше внимание, что все бессмысленные и пустые сообщения будут удаляться, ровно как и комментарии с заведомо не существующми e-mail адресами. Спасибо!


Случайное:
ОБЗОР ИГРЫ ASSASIN’S CREED ROGUE
Assassin’s Creed Rogue, последняя на сегодняшний день «полноценная», если так можно сказать, часть и
Полезные советы перед началом прохождения The Witcher 3
Относительно недавно состоялся выход, наверное, одной из самых ожидаемых игр как в жанре RPG, так
История возникновения компьютерных игр
Многие пользователи интересуются феноменом огромной популярности индии - игр, несмотря на то, что мн
Обзор Игры FAR CRY 3
Far Cry 3 – это игра, которая у многих ассоциируется всего лишь с одним словом – «безумие». Мы играе
Какие бывают на данный момент типы компьютерных игр?
Классификация компьютерных игр – это достаточно спорный вопрос, поскольку на данный момент предостав


 
2005-2011 theДжем.ru - сайт для тех, кто умеет читать и думать. ↑ вверх
полезно знать