In this task, we define a function called fib mem, which is the memoized version
ID: 3811964 • Letter: I
Question
In this task, we define a function called fib mem, which is the memoized version of the Fibonacci function, which takes an integer n as input and returns the n-th number in the Fibonacci sequence.
• Define the Fibonacci function fib as usual.
• Define the bind and lookup functions for association lists, as we discussed in class. Recall that an association list in Scheme is just a list of pairs and each pair contains a key and a value. – (bind k v al) adds a new entry (k,v) to the beginning of association list al. – (lookup k al) returns the value for key k in al if there is an entry for k and returns #f otherwise.
• Define a global variable al for the association list used in fib mem. (define al ’())
• Finally, define fib mem. When given n, it checks whether there is an entry for n in al. If there is, it returns the value in the entry; if not, it invokes (fib n), adds the entry (n, (fib n)) in the association list, and returns (fib n).
Explanation / Answer
import java.util.*;
import java.io.*;
import java.util.HashMap;
import java.lang.*;
import java.util.Scanner;
class fib-test
{
public static vaid main(String args[])
{
HashMap<Integer,Integer> al=new HashMap<Integer,Integer>();
Scanner scan= new Scanner(System.in);
al.put(0,0);
al.put(1,1);
al.put(2,1);
al.put(3,2);
al.put(4,3);
System.out.println("Enter the key no:");
int n=scan.nextInt();
if (al.containsKey(n))
System.out.println("The fibonacci value of " +n + " is " +al.get(n));
else
{
System.out.println("Key is not present in the list. Adding this key to list");
al.put(n,fibfun(n);
System.out.println("The fibonacci value of "+ n+" is " +al.get(n));
}
}
public int fibfun(int n)
{
int n0=0, n1=1;
for(int i=2;i<n;i++)
{
n2=n0+n1;
n0=n1; n1=n2;
}
return n2;
}
}
output:
enter the key no : 2
The fibonacci value of 2 is 1
enter the key no 5
Key is not present in the list. Adding this key to list
The fibonacci value of 5 is 5
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.