0
$\begingroup$

Using python need to code a recursive function with one input and no global integers that calculates the number of options to get $x$ using $a*1+b*2+c*3$.

Say $x=3$, there are four options: $\lbrace (1,1,1),(1,2),(2,1),(3)\rbrace$.

$\endgroup$
  • $\begingroup$ Do you probably mean the number of ways of using $\{1, 2, 3\}$ (along with their permutations) so that their sum is a given input $x$? Your equations coupled with your example makes no sense to me. $\endgroup$ – Paresh Dec 18 '12 at 17:02
  • $\begingroup$ The number of ways using the elements in the group ${1,2,3}$ so the sum will be the input (x): say x=3: $1)1+1+1 = 3$ $2)1+2=3$ $3)2+1=3$ $4)3 = 3$ so the output is 4. Sorry about the layout of my comment. I don't know how to add the spaces $\endgroup$ – yuvalz Dec 18 '12 at 18:00
  • 3
    $\begingroup$ I am going -1 questions which are so poorly phrased that it we have to guess what they mean. Please put in more effort when you ask a question. $\endgroup$ – Andrej Bauer Dec 18 '12 at 18:42
  • $\begingroup$ I'm sorry. I'm new to this. $\endgroup$ – yuvalz Dec 18 '12 at 19:08
  • $\begingroup$ But you're not new to speaking and writing. I don't mean to be mean, but do please take some care in how you write your questions. Starting sentences with capital letters helps, for example. Consider the fact that hundreds of people will read what you write. $\endgroup$ – Andrej Bauer Dec 18 '12 at 19:16
4
$\begingroup$

Recursion is a pretty bad choice here, but here is the recursion you could use: $$ f(n) = \begin{cases} 0, & n < 0, \\ 1, & n = 0, \\ f(n-1) + f(n-2) + f(n-3), & n > 0.\end{cases} $$ For example, $$ \begin{align*} f(-2) &= 0, \\ f(-1) &= 0, \\ f(0) &= 1, \\ f(1) &= f(0) + f(-1) + f(-2) = 1, \\ f(2) &= f(1) + f(0) + f(-1) = 2, \\ f(3) &= f(2) + f(1) + f(0) = 4. \end{align*} $$ The dynamic programming approach implied by this example is a much better idea; it can be implemented in constant space and linear time, whereas the recursion will take linear space and exponential time. You could also use matrix powering to compute $f$: $$ f(n) = \begin{bmatrix} 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}^n \begin{bmatrix} 1 \\ 1 \\ 2 \end{bmatrix}. $$ The generating function is $$ \sum_{n=0}^\infty f(n) x^n = \frac{1}{1-x-x^2-x^3}. $$ Finally, you can also find an explicit solution: $$ \begin{align*} f(n) &= \mathrm{round}(Cx^n), \\ C &= \frac{1}{3} + \frac{\sqrt[3]{847+33\sqrt{33}}}{66} + \frac{4}{3\sqrt[3]{847+33\sqrt{33}}}, \\ x &= \frac{1 + \sqrt[3]{19-3\sqrt{33}} + \sqrt[3]{19+3\sqrt{33}}}{3}. \end{align*} $$ This explicit solution isn't very helpful since you need a lot of precision, but it does give you the correct asymptotics; note $C \approx 0.6184199223$ and $x \approx 1.839286756$.

$\endgroup$
  • 2
    $\begingroup$ Speaking of an overkill :-) $\endgroup$ – Andrej Bauer Dec 18 '12 at 18:43
1
$\begingroup$
def f(n):
    """Compute the numbers of ways in which non-negative n can be expressed
    as a sum of 0s, 1s, and 2s."""
    (u, v, w) = (0, 0, 1)
    while n > 0:
        (u, v, w) = (v, w, u + v + w)
        n = n - 1
    return w
$\endgroup$
  • $\begingroup$ That's not recursive, though. $\endgroup$ – Yuval Filmus Dec 18 '12 at 19:27
  • $\begingroup$ @YuvalFilmus it can be turned to a recursive function using a helper for f(n), such as: fh(n, u,v,w) { if (n == 0) return w; else return fh(n-1, v,w, w+v+u) } .. would run in n steps as in loop. $\endgroup$ – AJed Dec 18 '12 at 22:53
0
$\begingroup$
def f(n):
    if n < 0:
        return 0
    elif n == 0:
        return 1
    else:
        return f(n-1) + f(n-2) + f(n-3)
$\endgroup$
  • $\begingroup$ i m sorry, but this function has exponential time complexity. you already mentioned that it is not good in your previous answer. $\endgroup$ – AJed Dec 19 '12 at 1:32
  • $\begingroup$ You might have misread the question: it asks for a recursive function, not for an efficient function. An optimizing compiler might memoize $f$ and then the running time is linear (of course, in that case the execution is no longer recursive). $\endgroup$ – Yuval Filmus Dec 19 '12 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.