# Fibonacci Number??

#### EnginiusXIII

Joined Oct 2, 2007
21
During my last interview session, I was asked on Fibonacci Number. The question is how do I find the n-th number of Fibonacci using equation? For example I was given the 80th number, how do I determine it?

Great Mathematician, please show me the exact and complete solution to it. I'm desperate as the next interview is two day from now. Thank you in advance.

-=Re-edit=-
I just do some homeworks to it and finally I understand part of the solution. However, I'm still poor in the identities. By the way, I also need the solution in Programming C++. Kindly help me with the coding/language. Thank you!

#### agentofdarkness

Joined Oct 9, 2007
42
Programming this is pretty easy. Can you make arrays in C++? I once made a program to do the fibonacci sequence in MatLab. You define a matrix X. Then you do this code.
The recursive equation for a Fibonacci Sequence is F(n) = F(n-1) + F(n-2)

A = 1;first value of Fibonacci Sequence
B = 1;2nd value of Fibonacci Sequence
X = 1
X = 1
Insert for/while loop here
n = 3
q = n-1
w = n-2
X[n] = X[q] + X[w]
n = n + 1

The code here is not correct, I wrote the program a while back and don't remember the exact syntax. X[n] is the nth number in the matrix X. So if X = [0 1 2 3 4 5 6 7] then X = 1.

#### Dave

Joined Nov 17, 2003
6,970
Programming this is pretty easy. Can you make arrays in C++? I once made a program to do the fibonacci sequence in MatLab. You define a matrix X. Then you do this code.
The recursive equation for a Fibonacci Sequence is F(n) = F(n-1) + F(n-2)

A = 1;first value of Fibonacci Sequence
B = 1;2nd value of Fibonacci Sequence
X = 1
X = 1
Insert for/while loop here
n = 3
q = n-1
w = n-2
X[n] = X[q] + X[w]
n = n + 1

The code here is not correct, I wrote the program a while back and don't remember the exact syntax. X[n] is the nth number in the matrix X. So if X = [0 1 2 3 4 5 6 7] then X = 1.
Matlab implementations of the Fibonacci Sequence exist in abundance at the Matlab File Exchange: http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=5093&objectType=File

In fact this is a very good early programming exercise to learn how to program small, yet versitile, algorithms.

Dave

#### Papabravo

Joined Feb 24, 2006
13,972
During my last interview session, I was asked on Fibonacci Number. The question is how do I find the n-th number of Fibonacci using equation? For example I was given the 80th number, how do I determine it?

Great Mathematician, please show me the exact and complete solution to it. I'm desperate as the next interview is two day from now. Thank you in advance.

-=Re-edit=-
I just do some homeworks to it and finally I understand part of the solution. However, I'm still poor in the identities. By the way, I also need the solution in Programming C++. Kindly help me with the coding/language. Thank you!
Tell us more about these interviews. Why are you getting a second chance if you flubbed the first one? BTW I consider it a totally irrelevant question for an interview of any kind. This isn't some Aisian corporate thing is it? Ask irrelevant questions until there is only one brainbound participant standing, who can remember everything, but can't create anything.

#### hgmjr

Joined Jan 28, 2005
9,029
There is some interesting information on the topic of Fibonacci Numbers here in the mathworld website.

hgmjr

#### Dave

Joined Nov 17, 2003
6,970
Tell us more about these interviews. Why are you getting a second chance if you flubbed the first one? BTW I consider it a totally irrelevant question for an interview of any kind. This isn't some Aisian corporate thing is it? Ask irrelevant questions until there is only one brainbound participant standing, who can remember everything, but can't create anything.
Such questions are often asked, not to ascertain a definitive answer, but to look at how a potential employee may approach such a problem. It is the same as the famous Microsoft Questions, or the interview questions at both Cambridge and Oxford Universities - "Is the moon made of cheese?" for example!

Dave

#### EnginiusXIII

Joined Oct 2, 2007
21
Tell us more about these interviews. Why are you getting a second chance if you flubbed the first one? BTW I consider it a totally irrelevant question for an interview of any kind. This isn't some Aisian corporate thing is it? Ask irrelevant questions until there is only one brainbound participant standing, who can remember everything, but can't create anything.
Well, first of all, I didn't really flubbed the first interview. There are many questions being forwarded to me back then and I actually did pretty well too (maybe). By the way, this is a scholarship interview. Actually I totally agree with you on "who can remember everything". Haha, sometimes it is quite tough since the interviewer asked question based on the subjects I have learned years before years. But Dave got a point, and it is true because I did ask the interviewer back then about my status. He told me that he is marking me not base on the answers but the methods of solving the matter. Of course if you could get both the answers and solutions you will have the advantage.

Lastly, thanks guys, now I get the idea of solving it using MatLab.

#### EnginiusXIII

Joined Oct 2, 2007
21
Dave, to be honest with you, I will totally flub if a question like this was given to me.

"Is the moon made of cheese?" Man, I can't handle those question since my IQ is pretty low. What will you answer if you were asked like that?

#### Dave

Joined Nov 17, 2003
6,970
Dave, to be honest with you, I will totally flub if a question like this was given to me.

"Is the moon made of cheese?" Man, I can't handle those question since my IQ is pretty low. What will you answer if you were asked like that?
Its the thought process that is important. The question "Is the moon made of cheese?" is clearly nonsensical - of course it is not, but saying that the moon isn't made of cheese because it isn't is not the answer they are looking for. Ask yourself why cannot the moon be made of cheese? Think what it would entail to make a structure the size of the moon out of cheese, numbers of cows etc. It sounds truly stupid, but it's the thought process - why does a completely stupid question with only one feasible answer, have that answer?

Dave

Joined May 1, 2007
19
hello enginius

the fibonnaci function f can easily be computed by machine using the recursive definition. i've forgotten what little c++ i ever knew, so here is it in python:

f = lambda n: n>=2 and f(n-1)+f(n-2) or n

computing f(n) manually for large n is a job that calls for a closed form of the function. one way to derive a closed form is to express in matrix notation the recurrence that defines the sequence of vectors whose n-th term v(n) is [f(n),f(n+1)]. if this equation is v(n+1)=m.v(n) then v(n)=m^n.v(0) for all n and the required equation is obtained by diagonalizing m. all of this is in the wikipedia article.

hope that helps

peace
stm

#### Papabravo

Joined Feb 24, 2006
13,972
A scholarship interview. That explains a great deal. I never had to do one of those and I don't think I missed much. It seems vaguely reminiscent of the GMAT (Graduate Management Admissions Test) where they presented an argument and ask the testee to classify the argument and identify any flaws. They don't teach that stuff in Engineering School so needless to say I kinda tanked that part.

#### EnginiusXIII

Joined Oct 2, 2007
21
Yeah, I kind of get what you are trying to say, Dave. Thanks for the hints.

Hi Stm,
Thanks for the help. Yeah, I'm referring to Wiki too...

#### granwizzard

Joined Nov 21, 2007
1
You can try this and your processor don't blow way if you wan´t the first 100 terms.
#include <stdio.h>
#include <stdlib.h>

int fibo (int k)
{
int i=0,n, f=1;
if (k==0 ||k==1)
return k;

for (n=1; n< k; ++n)
{
f= i + f;
i = f - i;
}
return f;
}

int prompt()
{
int k;
printf ("Insert a integer: ");
scanf ("%d",&k);
return k;
}

int main(int argc, char *argv[])
{
system("chcp 1252");
int k = prompt();
printf("\nThe Sequence is: \n\n");
int i;
for(i=0;i<k ; i++)
{
printf("%d\n", fibo(i));
if ( k < fibo(i+1) )
break;
}

system("PAUSE");
return 0;
}

Give me some feedback.

Kind regards.

#### fishface

Joined Jan 16, 2008
1
Sorry to revive a relatively old post, but I was recently asked how to calculate the nth degree of the fibonacci sequence -without- using recursion in an interview.
I told them I'd put the fib calculation in a loop but apparently they wanted something else. Totally confused me.

I've had all sorts of questions in interviews before, including "how many piano tuners are there in manhatten". That (piano) question I found much easier than the sort of "you have to get over a bridge but the bridge is weak and can only support 2 people at a time, You only have one torch, and one of your party has a limp, what's the fastest time you can get across the bridge without it collapsing" questions (that's made up, don't stress out trying to solve it), because the latter are so abstracted from reality and the interviewers seem only interested in the predetermined answer they know. The former type of questions (pianos, moon being made of cheese) are nice and open-ended and so it's obvious that you just need to work through the logic rather than find out a specific answer.