nth fibonacci with dynamic programming in c – dead clever, innit
intro
Oi, you lot! New to C and fancy summat a bit brainy? We’re gonna sling together a lil program to nab the nth Fibonacci number—ya know, that mad sequence where each number’s the sum of the two before it, like 0, 1, 1, 2, 3, 5, and so on—using dynamic programming to keep it quick. It’s dead smart but proper simple—like when I was tryna count my pint tabs piling up (lost it after five, too smashed). Great for getting yer head round arrays and loops in C without a right faff. Let’s have a butcher’s!
code bit
Here’s the code—nowt posh, just a quick job I chucked together. Shoved it in a box so it don’t look like a total shambles on yer blog. take a gander:
long long fibDP(int n) { // big numbers, innit
if(n<=0) { // no daft stuff
return 0; // 0th is 0
}
if(n==1) { // first is 1
return 1;
}
long long dp[n+1]; // stash em all
dp[0]=0; // start here
dp[1]=1;
for(int i=2;i<=n;i++) { // build it up
dp[i]=dp[i-1]+dp[i-2]; // add last two
}
return dp[n]; // chuck back nth
}
int main() { // nearly did void, ha!
int n; // which one ya want
printf("gimme n for nth Fibonacci: ");
scanf("%d",&n);
if(n<0) { // no negatives, ya muppet
printf("oi, gimme n 0 or up!\n");
}
else {
long long result=fibDP(n); // crunch it
printf("Fibonacci number %d is %lld\n",n,result); // forgot ; once, ugh!
}
return 0;
}
what ya get
Here’s what it chucks out when ya run it. I tested it with a couple n’s—worked bang on, mate! (Uses `long long` coz Fibonacci gets big quick!)
Fibonacci number 0 is 0
gimme n for nth Fibonacci: 5
Fibonacci number 5 is 5
gimme n for nth Fibonacci: 10
Fibonacci number 10 is 55
how it works, kinda
Right, let’s have a natter bout this like we’re slumped at the boozer with a pint—or a bag of pork scratchings, coz I’m Hank Marvin again. I’ll spill it like my tatty old notes from when I was faffing with C. It’s a doddle once ya clock it, swear down!
1. that `#include
This is me nicking my toolkit. `
2. `int main()` funtion
Gotta have a “main” to kick off—it’s like the door to my local. `int` means I’m lobbing a number out at the end (that `0` says “sorted, guv!”), and them curly `{}` lads keep it all snug. Nearly wrote `void main()`—old me was a right numpty!
3. boxes: `int n;`
This is my lil bucket—`n` holds which Fibonacci number ya want. `int` coz we’re picking a spot, innit!
4. chatting at ya: `printf` and `scanf`
So yeah, `printf("gimme n for nth Fibonacci: ")` is me barking, “Oi, n, sharpish!” Then `scanf("%d",&n)` grabs it and shoves it in `n`. `%d` for integers, `&` like a post-it saying “bung it here, ya twit!”
5. `fibDP` funtion
Here’s the guts! `fibDP(int n)` does the dynamic programming magic. `if(n<=0)` gives 0 for 0 or less—keeps it sensible. `if(n==1)` gives 1—first Fib’s 1. Else, `long long dp[n+1]` makes an array to stash all Fibs up to n—`long long` coz they grow massive! `dp[0]=0` and `dp[1]=1` set the start, then `for(i=2;i<=n;i++)` loops, `dp[i]=dp[i-1]+dp[i-2]` adds the last two. Returns `dp[n]`—like piling up pint tabs but smarter!
6. check the daft ones: `if(n<0)`
If ya chuck in a negative—`if(n<0)`—it yells “oi, 0 or up!”—coz negatives don’t make sense for Fibs!
7. chucking it out: `printf` and `fibDP`
`long long result=fibDP(n)` crunches it, then `printf("Fibonacci number %d is %lld\n",n,result)` shows it—`%d` for n, `%lld` for big numbers, `\n` keeps it tidy. Forgot a `;` once—CODE JUST DIED, and I was proper fuming!
8. `return 0` to scarper
That `return 0;` is me legging it, like, “Ta-ta, we’re done!” It’s a C thing—means it all went smooth as a greased weasel.
And that’s yer lot! A cracking lil program to nab the nth Fibonacci with dynamic programming. Faff with it—chuck in daft n’s, tweak it to say “Fib pile” if ya fancy. First time I ran this, I did 7 and got 13—bang on, eh! You’re a star already, mate—keep smashing it! 😊 (Mind, big n’s might overflow `long long`—it’s just a toy!)
