Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 17.04.2010, 19:36
Danon

 
Сообщений: n/a

Резисторы
Даны N резисторов с известными сопротивлениям. Требуется определить, можно ли с помощью этих резисторов построить последовательно-параллельную схему сопротивлением R.
1<=N<=7

Есть какие-нибудь идеи как это сделать?
  #2  
Старый 17.04.2010, 19:45
гость

 
Сообщений: n/a

полный перебор
  #3  
Старый 17.04.2010, 20:01
гость

 
Сообщений: n/a

Я понимаю, но как это сделать быстро.
Алгоритм такой.
У меня есть процедура get_res. Она рекурсивная, и определяет какие сопротивления можно получить, если использовать различные резистры. Для разных комбинаций резистров - разные наборы сопротивлений получаются.
Но перебирает эта процедура не все сопротивления, т.к перебор там устроен следующим образом:
Если i-й резистор не использовался, то она сначала пытается его к текуще схеме подключить последовательно, а потом паралелельно, запуская при этом себя рекурсивно. В качестве параметров передаются текущее сопротивление и кол-во резисторов.
Теперь чтобы найти ВСЕ сопротивления которые можно получить из исходных резисторов мне надо разбивать резисторы на два подмножества и пытаться подключать их последовательн и параллельно....
Но мне не нравится то, что всеэто слишком долго работает...

Может я не так перебираю?
  #4  
Старый 17.04.2010, 20:22
гость

 
Сообщений: n/a

Чё там долго работает? Их всего около 80 тысяч конфигураций, если не ошибаюсь (http://www.research.att.com/~njas/sequences/A006351). Это мало. Мгновенно должно работать.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра