# need the solution

Discussion in 'C Programming' started by wahid, Jan 10, 2010.

1. ### wahidGuest

• In mathematics, the Fibonacci numbers are
the numbers in the following sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144....
• By definition, the first two Fibonacci numbers
are 0 and 1, and each remaining number is the
sum of the previous two. Some sources omit
the initial 0, instead beginning the sequence
with two 1s.

• Write a program using recursion, that will
input an integer value n, and generate the first
n fibonacci numbers.

wahid, Jan 10, 2010

2. ### SeebsGuest

On 2010-01-10, wahid <> wrote:
> ? In mathematics, the Fibonacci numbers are
> the numbers in the following sequence:
> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144....
> ? By definition, the first two Fibonacci numbers
> are 0 and 1, and each remaining number is the
> sum of the previous two. Some sources omit
> the initial 0, instead beginning the sequence
> with two 1s.
>
> ? Write a program using recursion, that will
> input an integer value n, and generate the first
> n fibonacci numbers.

Come on, dude, do your own homework or at least post messages thanking
the people who take the time to contribute suggestions.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach /
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

Seebs, Jan 10, 2010

3. ### Antoninus TwinkGuest

On 10 Jan 2010 at 7:26, wahid wrote:
> â€¢ Write a program using recursion, that will input an integer value n,
> and generate the first n fibonacci numbers.

#include <stdio.h>
#include <stdlib.h>

unsigned long long int fib(unsigned int n, unsigned long long int *tbl)
{
unsigned long long int x, y;
if(tbl[n])
return tbl[n];
x = n == 0 ? 0
: n == 1 ? 1 :
fib(n - 1, tbl);
y = n <= 1 ? 0 : fib(n - 2, tbl);
if(x + y < x) {
fputs("Integer overflow\n", stderr);
exit(1);
}
return tbl[n] = x + y;
}

int main(void)
{
int i, d, rv = 0;
unsigned long long int *tbl;
fputs("Enter a Number: ", stdout);
fflush(stdout);
if(scanf("%d", &d) == 1 && d >= 1) {
if((tbl = calloc(d, sizeof *tbl)) == NULL) {
perror("malloc");
rv = 1;
} else {
fib(d - 1, tbl);
for(i = 0; i < d; i++)
printf("Fib[%d] = %llu\n", i + 1, tbl);
free(tbl);
}
}
else {
fputs("Invalid input: needed a positive integer\n", stderr);
rv = 1;
}
return rv;
}

Antoninus Twink, Jan 10, 2010
4. ### AlbertGuest

wahid wrote:
> • In mathematics, the Fibonacci numbers are
> the numbers in the following sequence:
> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144....
> • By definition, the first two Fibonacci numbers
> are 0 and 1, and each remaining number is the
> sum of the previous two. Some sources omit
> the initial 0, instead beginning the sequence
> with two 1s.
>
> • Write a program using recursion, that will
> input an integer value n, and generate the first
> n fibonacci numbers.

#include <stdio.h>

#define MAX 1000000

int known[MAX];
int fib[MAX];

int calculate(int n) {
if (known[n])
return fib[n];
else {
known[n] = 1;
return fib[n] = calculate(n - 1) + calculate(n - 2);
}
}

int main()
{
int i, n;

fib[1] = 0;
fib[2] = 1;
known[1] = known[2] = 1;
scanf("%d", &n);
calculate(n);

for (i = 1; i <= n; i++) {
if (i > 1)
putchar(' ');
printf("%d", fib);
}
putchar('\n');
return 0;
}

Albert, Jan 20, 2010
5. ### Nick KeighleyGuest

Re: need the solution

On 10 Jan, 07:26, wahid <> wrote:
> • In mathematics, the Fibonacci numbers are
> the numbers in the following sequence:
> 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144....
> • By definition, the first two Fibonacci numbers
> are 0 and 1, and each remaining number is the
> sum of the previous two. Some sources omit
> the initial 0, instead beginning the sequence
> with two 1s.
>
> • Write a program using recursion, that will
> input an integer value n, and generate the first
> n fibonacci numbers.

p-code solution

(define (fib n)
(unfold
(lambda (x) (= (car x) n))
x))))
(list 0 0 1) ))

Nick Keighley, Jan 21, 2010
6. ### Michael FoukarakisGuest

Re: need the solution

On Jan 21, 11:38 am, Nick Keighley <>
wrote:
> On 10 Jan, 07:26, wahid <> wrote:
>
> > • In mathematics, the Fibonacci numbers are
> > the numbers in the following sequence:
> > 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144....
> > • By definition, the first two Fibonacci numbers
> > are 0 and 1, and each remaining number is the
> > sum of the previous two. Some sources omit
> > the initial 0, instead beginning the sequence
> > with two 1s.

>
> > • Write a program using recursion, that will
> > input an integer value n, and generate the first
> > n fibonacci numbers.

>
> p-code solution
>
> (define (fib n)
>     (unfold
>         (lambda (x) (= (car x) n))
> x))))
>         (list 0 0 1) ))

Pardon my ignorance, but is that style of pseudo-language similar to
any "real" one(s)? If so, which ones?

Cheers.

Michael Foukarakis, Jan 21, 2010
7. ### Nick KeighleyGuest

Re: need the solution

On 21 Jan, 10:14, Michael Foukarakis <> wrote:
> On Jan 21, 11:38 am, Nick Keighley <>
> > On 10 Jan, 07:26, wahid <> wrote:

>
> > > • In mathematics, the Fibonacci numbers are
> > > the numbers in the following sequence:
> > > 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144....
> > > • By definition, the first two Fibonacci numbers
> > > are 0 and 1, and each remaining number is the
> > > sum of the previous two. Some sources omit
> > > the initial 0, instead beginning the sequence
> > > with two 1s.

>
> > > • Write a program using recursion, that will
> > > input an integer value n, and generate the first
> > > n fibonacci numbers.

>
> > p-code solution

>
> > (define (fib n)
> >     (unfold
> >         (lambda (x) (= (car x) n))
> >         (lambda (x) (cadr x))
> > x))))
> >         (list 0 0 1) ))

>
> Pardon my ignorance, but is that style of pseudo-language similar to
> any "real" one(s)? If so, which ones?

scheme which is a lisp dialect. That's an actual program. This wahid
guy is great he's giving me a stream of little problems to solve! You
could argue my solution doesn't use recursion though.

(fib 13)
(0 1 1 2 3 5 8 13 21 34 55 89 144)

This version might be slightly clearer (if I'd wanted it to be clear
why would I write in scheme...)

(define (fib2 n)
(unfold
(lambda (x) (= (first x) n))
(lambda (x) (second x))
(lambda (x) (list (+ (first x) 1) (third x) (+ (second x)
(third x))))
(list 0 0 1) ))

Nick Keighley, Jan 21, 2010
8. ### Michael FoukarakisGuest

Re: need the solution

On Jan 21, 12:24 pm, Nick Keighley <>
wrote:
> On 21 Jan, 10:14, Michael Foukarakis <> wrote:
>
> > On Jan 21, 11:38 am, Nick Keighley <>
> > > On 10 Jan, 07:26, wahid <> wrote:

>
> > > > • In mathematics, the Fibonacci numbers are
> > > > the numbers in the following sequence:
> > > > 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144....
> > > > • By definition, the first two Fibonacci numbers
> > > > are 0 and 1, and each remaining number is the
> > > > sum of the previous two. Some sources omit
> > > > the initial 0, instead beginning the sequence
> > > > with two 1s.

>
> > > > • Write a program using recursion, that will
> > > > input an integer value n, and generate the first
> > > > n fibonacci numbers.

>
> > > p-code solution

>
> > > (define (fib n)
> > >     (unfold
> > >         (lambda (x) (= (car x) n))
> > >         (lambda (x) (cadr x))
> > > x))))
> > >         (list 0 0 1) ))

>
> > Pardon my ignorance, but is that style of pseudo-language similar to
> > any "real" one(s)? If so, which ones?

>
> scheme which is a lisp dialect. That's an actual program. This wahid
> guy is great he's giving me a stream of little problems to solve! You
> could argue my solution doesn't use recursion though.
>
> (fib 13)
> (0 1 1 2 3 5 8 13 21 34 55 89 144)
>
> This version might be slightly clearer (if I'd wanted it to be clear
> why would I write in scheme...)
>
> (define (fib2 n)
>     (unfold
>         (lambda (x) (= (first x) n))
>         (lambda (x) (second x))
>         (lambda (x) (list (+ (first x) 1) (third x) (+ (second x)
> (third x))))
>         (list 0 0 1) ))

Ah, that's neat(er). Thanks.

Michael Foukarakis, Jan 21, 2010