#include <stdio.h>
int main()
{
int fib(int x)
{
if(x<2)
return 1;
else
return fib(x-1)+fib(x-2);
}
int n;
printf("Integer goes here, yo: ");
scanf("%i", n);
printf("\nThe Fibbonacci number of %i is %i\n", n, fib(n)); //I really believe that this line is faulty in the "...\n", n, fib(n))" declaration.
return 0;
}
That cannot be the original code either -- because nested functions are not supported in C.
If your compiler supports it, weird. I thought you said you used GCC, and to my knowledge, GCC doesn't support them.
In any case, you should move the fib(){} function body out from the enclosing main(){} function body. Function definitions cannot be nested in C.
Assuming that was really just another transcription error, the real crash cause is the missing & as FractalFusion pointed out.
That cannot be the original code either -- because nested functions are not supported in C.
If your compiler supports it, weird. I thought you said you used GCC, and to my knowledge, GCC doesn't support them.
Ah, so GCC supports them for C but not C++.
In any case, they're not standard C, and such, should be avoided unless you're writing a GCC-specific program for a good reason.
Not good enough. Considering that the function only is supposed to handle integer values, this works faster and gives the same results:
that looks short and sweet until you realize that φⁿ doesn't compute in constant time either.
couldn't this be used to calculate F(n) using only integer operations in O(log2(n))?
unsigned int fib(unsigned int n){
if (n < 2)
return n;
else
return fib(n - 1) + fib(n - 2);
}
I borrowed it for use in my own code.
You shouldn't, because that's the most inefficient possible way of calculating fibonacci numbers.
I realized that it might actually not be immediately clear why that's an extremely inefficient way of calculating fibonacci numbers. Explanation:
fib(0) and fib(1) obviously return immediately. The total amount of calls to the fib() function in both cases is obviously 1.
fib(2) performs 2 calls, fib(1) and fib(0). The total number of calls to fib() is 3 (the primary call to fib() plus the two recursive calls).
fib(3) performs the calls fib(2) and fib(1), that is 1+3+1 = 5 calls.
fib(4) performs the calls fib(3) and fib(2), that is 1+5+3 = 9 calls.
fib(5) = fib(4) and fib(3) = 1+9+5 = 15 calls.
etc...
The number of calls performed increases quite rapidly. For example
fib(30) performs a total of 2692537 calls to the fib() function.
fib(40) performs a total of 331160281 calls.
fib(45) performs a total of 3672623805 calls.
With a simple loop implementation fib(45) would just perform 45 iterations and that's it.
I think it might be a better programming exercise to simply calculate it in a loop... :)
With a simple loop implementation fib(45) would just perform 45 iterations and that's it.
A much more efficient way of calculating fibonacci numbers is to use a simple loop.
Everyone else doesn't seem to get the idea that I don't really know what the other functions in this thread do (I mean, yes, I know that they print Fibbonacci numbers, but not why they do) so I'm asking you about this instead. Do you mean a loop that calculates f(1), f(2), f(3) and so on up to f(n)?
I think it might be a better programming exercise to simply calculate it in a loop... :)
With a simple loop implementation fib(45) would just perform 45 iterations and that's it.
A much more efficient way of calculating fibonacci numbers is to use a simple loop.
Everyone else doesn't seem to get the idea that I don't really know what the other functions in this thread do (I mean, yes, I know that they print Fibbonacci numbers, but not why they do) so I'm asking you about this instead. Do you mean a loop that calculates f(1), f(2), f(3) and so on up to f(n)?
Warp means this:
unsigned int fib(unsigned int n){
unsigned int a=0, b=1, c=1, i;
if (n < 2)
return n;
else
for(i=3;i<=n;i++) {
a=b;
b=c;
c=a+b;
}
return c;
}
The other "functions" come from the mouth of algorithm complexity theorists.
If you're curious about the other algorithms that calculate F(n) with a single expression, you can find more details here. It involves the Golden Ratio, which is pretty cool.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Everyone else doesn't seem to get the idea that I don't really know what the other functions in this thread do (I mean, yes, I know that they print Fibbonacci numbers, but not why they do) so I'm asking you about this instead. Do you mean a loop that calculates f(1), f(2), f(3) and so on up to f(n)?
Think about the factorial function. There are two ways of implementing it: Recursively and iteratively. The recursive implementation would look something like this:
The iterative implementation would look something like this:
unsigned factorial(unsigned n)
{
unsigned result = 1;
for(unsigned i = 2; i <= n; ++i) result *= i;
return result;
}
In this case the iterative implementation is more efficient than the recursive one, but not by much. Both execute n steps (but the recursive version has more memory overhead, unless a really smart C compiler is able to perform tail recursion optimization).
The problem with the recursive fibonacci function is that it's exponentially heavier than an iterative implementation. The basic idea in both implementations is the same as with the factorial function above.
Think about the factorial function. There are two ways of implementing it: Recursively and iteratively. The recursive implementation would look something like this:
Actually, earlier I thought there was no discernible difference between recursion and iteration. Proved me wrong.
Derakon wrote:
If you're curious about the other algorithms that calculate F(n) with a single expression...
Thanks! I'll read it when I don't have to sleep. :)
FractalFusion wrote:
unsigned int fib(unsigned int n){
unsigned int a=0, b=1, c=1, i;
if (n < 2)
return n;
else
for(i=3;i<=n;i++) {
a=b;
b=c;
c=a+b;
}
return c;
}
It's not immediately clear what everything does (but something tells me it's hilariously simple and I'm a moron), so I'll try to make sense of it tomorrow when I can think straight. Thanks! :)
i need sleeeeep
Look at what the values of a, b, and c are:
a and be are two adjacent numbers in the Fibonacci sequence.
a + b, thus, is the next number in the Fibonacci sequence. Stick that into c.
Now we want to move everything over by one so we're ready to calculate the next number. So a becomes b, b becomes c, and c is ready to store the next number.
Now a and b are two adjacent numbers in the Fibonacci sequence...
Keep going until we've calculated N Fibonacci numbers.
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
Look at what the values of a, b, and c are:
a and be are two adjacent numbers in the Fibonacci sequence.
a + b, thus, is the next number in the Fibonacci sequence. Stick that into c.
Now we want to move everything over by one so we're ready to calculate the next number. So a becomes b, b becomes c, and c is ready to store the next number.
Now a and b are two adjacent numbers in the Fibonacci sequence...
Keep going until we've calculated N Fibonacci numbers.
Hi! I'm back, and I need more help with C!
At Christmas I recieved The C Programming Language, so I'm learning from that now, rather than internet tutorials.
I'm currently 'stuck' at the section regarding arrays; I really can't understand what they are.
Someone! Please tell me how they work, and what they're used for!
Can I ask you why you want to learn C, rather than, for example, C++, C# or Java? C is a rather low-level language with a huge amount of gotchas and ways to shoot yourself in the foot, and it offers very few tools which aid in programming (while those other languages offer tons of useful tools which make programming easier).
(Personally I'm not a huge fan of Java, but if I had to recommend either C or Java to a beginner programmer, I would definitely recommend the latter. I hate C more than I hate Java.)
As for your question, can you be a bit more specific about what is it that you don't understand about arrays? Also, are you talking about static arrays or dynamically allocated ones? (Do you know the difference?)
Knowing C is a bit like knowing assembly, in that it gives you a lot of insight into how computers "actually work" than higher-level languages do. Of course, C is abstracting things a lot already, but it does a heck of a lot less abstraction than Java does. I'm very glad I learned C and figured out how pointers, references, and garbage collection work. Now, did C really need to be my first language? Probably not, but in the long run, it didn't hurt. I'll grant that I was very confused a lot of the time starting out, though. :)
Pyrel - an open-source rewrite of the Angband roguelike game in Python.
An array is a continuous section of memory containing data of the same type. An array of 10 ints, which are often 4 bytes long, would be a section of memory 40 bytes long. C only cares about where in memory that section starts, so if you have a pointer to the first element of the array, that is all you need to know. This means that arrays and pointers are interchangeable, basically.
To create an array, you may write
int a[10] = {0,1,2,3,4,5,6,7,8,9};
When you do this, a section of memory (on the stack) will be filled with these numbers. In a hex editor, it might look like:
Here, the array starts at position 0x14 in memory, so the variable a will have this value in this case. To look up a value in the array, you do
int b = a[3];
for example. This means: Go to the address contained in a. Add 3 times the size of an integer to that address, and read an integer from it, storing it in b. Doing this, we find: a = 0x14. sizeof(int) = 4, so a+3*sizeof(int) = 0x14 + 0xC = 0x20, where we find the integer value 3, as expected. This makes it easy to see what would happen if we ask for something at a greater position than what was allocated for the array. We just get whatever lies in memory afterward. In this example, a[10] would read the bytes 5D 0A 3E 3E which corresponds to the integer 1044253277. C does not keep track of how long the array actually is.
Any pointer can be treated as an array. For example
int * c = a+6;
return c[3];
This will return the same thing as a[9]. c is a pointer to a place in memory 6*sizeof(int) later in memory than a, that is 0x2C, and we can treat this as an array starting at a later point in the original array a.
Another way of creating an array is to use malloc to reserve an area of memory on the heap:
int * d = malloc(1000*sizeof(int));
This can be used just like the previous arrays, except that you should free up the memory after you're done with it:
free(d);
(this will happen automatically when your program exits, though, so for a small program it is not a disaster if you forget).
And as for what they are useful for, isn't that pretty obvious? Let's say that you want to read in 10 numbers from standard input, and print them back their squares in reverse order. Without arrays, this would look like
