Разбор задачи "Резисторы"

(В этой задаче все равно — говорить про резисторы или про конденсаторы, т.к. формулы соединения аналогичны, только для резисторов для последовательного соединения формула та же, что для конденсаторов для параллельного, и наоборот. На задачу это не влияет. Я для удобства буду говорить про резисторы, а не про конденсаторы.)

"Резисторы" — это задача, скажем так, "общего вида" на перебор. А именно, если в других задачах на перебор вы обычно формируете какую-нибудь последовательность, последовательно к текущему решению добавляя что-то еще, то здесь так просто не получится.

Вы можете попробовать делать так: у вас есть некоторая текущая схема. Вы берете очередной еще не использованный резистор и присоединяете его к текущей схеме или последовательно или параллельно. Потом берете очередной еще не использованный резистор и т.д. Но с таким решением есть проблема: вы не сможете получить по-настоящему сложную схему. Например, рассмотрим следующую схему:

         +--D-E-+
 +-A--B--+      +--+
-+       +--F-G-+  +---
 |                 | 
 +-G--H--+--I--+---+
         |     |
         +-J-K-+ 

(буквы обозначают резисторы)

Вы ее получить не сможете, т.к. тут надо сначала собрать несколько отдельных схем, а потом уже их объединить в одну.

Вы можете попробовать собирать сразу две схемы, но все равно вы не сможете полностью покрыть все разнообразие решений.

Поэтому эту задачу можно решать по-другому. А именно, переформулируем ее так. У нас на столе лежат N резисторов. Мы можем взять два из них, убрать, а вместо них положить резистор, равный или последовательно соединенным этим двум резисторам, или параллельно соединенным. Т.е. любые два резистора мы можем заменить на результат их последовательного или параллельного соединения. После этого мы можем опять взять два любых резистора (в том числе и тот, который только получили из предыдущих двух) и заменить на один. И т.д. Ясно, что вот это как раз покрывает все разнообразие схем, т.к. никто нас не заставляет все время наращивать одну конкретную схему, мы можем сначала собрать несколько кусков, а потом их как надо объединить.

И это очень легко реализуется. Процедура find будет выбирать два резистора, заменять их на одно, и запускаться рекурсивно.

var r:array[...] of extended; // резисторы, которые сейчас лежат на столе
    n:integer; // количество резисторов
procedure find;
var i,j:integer;
    r1,r2:extended;
begin
for i:=1 to n do
    for j:=i+1 to n do begin
        r1:=r[i];
        r2:=r[j];
        // начинается магия, поймите ее!
        r[j]:=r[n];
        dec(n);
        r[i]:=r1+r2;
        find;
        r[i]:=r1*r2/(r1+r2);
        find;
        inc(n);
        r[n]:=r[j];
        r[i]:=r1;
        r[j]:=r2;
    end;
end;

Вот и все. Даже не надо проверки на выход из рекурсии, т.к. когда станет n=1, то циклы не выполнятся ни разу. Осталось только проверять все получающиеся резисторы на предмет того, не получается ли хорошее решение, это проще всего сделать циклом по всем имеющимся резисторам в начале процедуры find.

Что тут важно. Что тут решение строится не путем последовательных добавлений, а что вы честно исследуете все возможные пути. Можете думать об этом как о некоторой игре, в которой есть позиции (какие резисторы на столе) и возможные ходы из каждой позиции, и вы просто перебираете такие ходы.