8 - May - 2011
Fun to code. The same applies to Inductors and Resistors. The series appears as 1, 3, 7, 15, 31, 63, 127, 255, ... which is one less than powers of 2. Ofcourse generating this series is quite easy. The emphasis is on the recursion tree, and dynamic programming.
I came across an interesting problem. Given N capacitors (or inductors, resistors) of same value say C (unit is Farad). How many difference capacitances can be derived from these N capacitors connected in series, parallel and series-parallel combination.
For example if N = 1, only one way it can be connected. If N = 2, they can be connected in two different ways of series and parallel. If N = 3, they can be connected in 7 different ways. That means we can derive 7 different capacitance values from given 3 capacitors of same value. These 7 combinations can be found pictorially on the Project Euler page.
Can we generalize it? Yes. Say the total possible capacitances are represented as S(n). If we observe, only the difference between S(n-1) and S(n-2) will participate using next capacitor. For example to calculate S(n) we need the difference DELTA = S(n-1) - S(n-2), and all combinations upto S(n-1). The new capacitor C(n) can be connected in series and parallel with every combination of DELTA..
With an example it will be clear. We know S(1) = 1, S(2) = 3 and S(3) = 7. To calculate S(4) we need DELTA = S(3) - S(2) = 4. We can connect the 4-th capacitor in series and parallel with these 4 combinations, overall it adds 4 * 2 = 8 more combination to the existing 7 combination upto S(3). So, clearly S(4) = 2 x DELTA + S(3) = 15. There is a recursive formula. It is evident from the recursion tree given below for S(5).
Solution can be generalized as
S(n) = 2 x (S(n-1) - S(n-2)) + S(n-1)
= 3 x S(n-1) - 2 x S(n-2)
Base case S(1) = 1, S(2) = 3 and S(3) = 7.
We can code above formula using recursion easily.
int totalPossibleCapacitances(int n)
{
static int S[] = {1, 3, 7};
if(n > 3)
// Non trival case
return 3*totalPossibleCapacitances(n-1) - 2*totalPossibleCapacitances(n-2)
else
// Trivial case
return S[n - 1];
}
Complexity: What will be the complexity? If we observe the recursion tree, the problems are overlapped. Similar to the Fibonacci series. The characteristic equation of generalized solution can be written as
x ^ 2 - 3*x + 2 = 0 whose roots are x1 = 1 and x2 = 2. The solution is in the form
S(n) = A(x1)^n + B(x2)^n where A and B are constants that depends on initial conditions. After substitution of S(2) and S(3) we get,
S(n) = 1.2 * (2)^n - 3 which is exponential.
So, the above function runs with exponential complexity. Can we do better? Yes, the well known technique "Dynamic Programming".
If we observe from S(4), every number is depending on past two numbers only. S(n) = 3*S(n-1) - 2*S(n-2), i.e. we need to store only the past two values to find next number. A three element array will be sufficient. Given below pseudo code,
int totalPossibleCapacitances(int n)
{
// For efficiency purpose
// static
int S[] = {1, 3, 7};
if(n > 3)
{
// Non trivial
int activeIndex = 0;
for(int i = 4; i <= n; i++)
{
S[activeIndex] = 3*S[ (activeIndex + 2) % 3 ] - 2*S[ (activeIndex + 1) % 3 ];
activeIndex++;
activeIndex %= 3;
}
if(activeIndex)
activeIndex--;
return S[activeIndex];
}
else
{
// Trivial
return (n > 0 ? S[n - 1] : -1);
}
}
Fun to code. The same applies to Inductors and Resistors. The series appears as 1, 3, 7, 15, 31, 63, 127, 255, ... which is one less than powers of 2. Ofcourse generating this series is quite easy. The emphasis is on the recursion tree, and dynamic programming.
