Matlab help A Fibonacci sequence is generated by the following recursion, initia
ID: 3764220 • Letter: M
Question
Matlab help
A Fibonacci sequence is generated by the following recursion, initialized at some arbitrary integer values of f1 and f2:
fn = fn1 + fn2 , n 3
Write a function fib that evaluates 2 up to N sequence values with usage:
f = fib(N,f1,f2);
where f1,f2 are the two initial values. Internally, the function must use a for-loop and return the vector of values fn, 1 n N.
Run your function for N = 20, f1 = 0, f2 = 1, and plot fn vs. n. Then, repeat for f1 = 1, f2 = 3. In fact, use a semilogy plot and put both cases on the same graph.
The ratio of two successive Fibonacci numbers tends to the “golden ratio” for large n, regardless of the initial values f1, f2:
gn = fn / fn1 = (1 + 5) / 2 = 1.6180 . . .
For N = 20, f1 = 1, f2 = 3, calculate gn, 2 n N, and plot it versus n, together with the straight line at the golden ratio level.
3. Consider again the Fibonacci sequence of Eq. (2) with initial values f1 = 1, f2 = 3. Using a while-loop, determine the largest value of n such that fn < fmax, for some given maximum value. For example, choose fmax = 10^6 . Implement this question with two types of loops:
% conventional loop % forever loop
Explanation / Answer
#include <stdlib.h>
#include <stdio.h>
#include <gmp.h>
typedef struct node node;
struct node {
int n;
mpz_t v;
node *next;
};
#define CSIZE 37
node *cache[CSIZE];
// very primitive linked hash table
node * find_cache(int n)
{
int idx = n % CSIZE;
node *p;
for (p = cache[idx]; p && p->n != n; p = p->next);
if (p) return p;
p = malloc(sizeof(node));
p->next = cache[idx];
cache[idx] = p;
if (n < 2) {
p->n = n;
mpz_init_set_ui(p->v, 1);
} else {
p->n = -1; // -1: value not computed yet
mpz_init(p->v);
}
return p;
}
mpz_t tmp1, tmp2;
mpz_t *fib(int n)
{
int x;
node *p = find_cache(n);
if (p->n < 0) {
p->n = n;
x = n / 2;
mpz_mul(tmp1, *fib(x-1), *fib(n - x - 1));
mpz_mul(tmp2, *fib(x), *fib(n - x));
mpz_add(p->v, tmp1, tmp2);
}
return &p->v;
}
int main(int argc, char **argv)
{
int i, n;
if (argc < 2) return 1;
mpz_init(tmp1);
mpz_init(tmp2);
for (i = 1; i < argc; i++) {
n = atoi(argv[i]);
if (n < 0) {
printf("bad input: %s ", argv[i]);
continue;
}
// about 75% of time is spent in printing
gmp_printf("%Zd ", *fib(n));
}
return 0;
}
Output:
% ./a.out 0 1 2 3 4 5
1
1
2
3
5
8
% ./a.out 10000000 | wc -c # count length of output, including the newline
1919488
2..
#include<stdio.h>
#include<conio.h>
void main()
{
int initial_value=0,final_value=1,temp_value,count=10;
// count contains the number of elements to be generated.....
for(count=1;count<=10;count++)
{
temp_value=initial_value+final_value;
printf(" %d",initial_value);
initial_value=final_value;
final_value=temp_value;
}
getch();
}