edited by
20,904 views
62 votes
62 votes

Consider the following C function.

int fun(int n) {
    int x=1, k;
    if (n==1) return x;
    for (k=1; k<n; ++k)
        x = x + fun(k) * fun (n-k);
    return x;
}

The return value of $fun(5)$ is ______.

edited by

12 Answers

1 votes
1 votes

Answer is 51.

If you know the no of ways to split a number then you can easily solve the question:

5 can be split into (1,4), (2,3) (3,2)  (4,1)

therefore Fun(5) = 1+fun(1)*fun(4) + fun(4)*fun(1)+fun(3)*fun(2) + fun(2)*fun(3)

                           =  x+ 2*{fun(1)*fun(4) + fun(2)*fun(3)}

Similiarly

fun(2) = 1+ fun(1)*fun(1) = 2 ,since 2 can be split in 1,1

fun(3) = 1+ 2*{fun(1)*fun(2)} =5 ,since 3 can be split in 1,2 and 2,1

fun(4)= 1+ 2*{fun(1)*fun(3)}+fun(2)*fun(2) = 15 ,since 4 can be split in 2,2   1,3  and 3,1

fun(5)=  1+ 2*{fun(1)*fun(4) + fun(2)*fun(3)} = 1+ 2*(15+10) = 51

0 votes
0 votes
Answer is 51

Explanation:

By mathematical induction,solve this from smaller value to bigger value

fun(1) → fun(2) → fun(3) → fun(4) → fun(5)

For n=1,it check if(1=1).The condition is true so it return 1;

For n=2,The if condition fails then it execute for loop for k<2 times

              For k=1,

              x=1+fun(1)*fun(2-1); => 1+fun(1)*fun(1) => 1+1*1 => 2

              it returns x=2 so fun(2)=2

For n=3,The if condition fails then it execute for loop for k=1,2

              For k=1,

              x=1+fun(1)*fun(3-1); => 1+fun(1)*fun(2) => 1+1*2 => 3

              For k=2,

              x=3+fun(2)*fun(3-2); => 3+fun(2)*fun(1) => 3+2*1 => 5

              It return x =5 => fun(3)=5

For n=4,The if condition fails then it execute for loop for k=1,2,3

              For k=1,

              x=1+fun(1)*fun(4-1); => 1+fun(1)*fun(3) => 1+1*5 => 6

              For k=2,

              x=6+fun(2)*fun(4-2); => 6+fun(2)*fun(2) => 6+2*2 => 10

              For k=3,

              x=10+fun(3)*fun(4-3); => 10+fun(3)*fun(1) => 10+5*1 => 15

              It return x =15 => fun(4)=15

For n=5,The if condition fails then it execute for loop for k=1,2,3,4

              For k=1,

              x=1+fun(1)*fun(5-1); => 1+fun(1)*fun(4) => 1+1*15 => 16

              For k=2,

              x=16+fun(2)*fun(5-2); => 16+fun(2)*fun(3) => 16+2*5 => 26

              For k=3,

              x=26+fun(3)*fun(5-3); => 26+fun(3)*fun(2) => 26+5*2 => 36

              For k=4,

              x=36+fun(4)*fun(5-4); => 36+fun(4)*fun(1) => 36+15*1 => 51

              It return x =51 => fun(5)=51.
Answer:

Related questions

38 votes
38 votes
5 answers
2
36 votes
36 votes
6 answers
3
go_editor asked Feb 13, 2015
15,514 views
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.