Consider the following function that defines F$($n$)$ for all n $>=1$:

F$(1)=1$; F$(2)=2$; F$(3)=3$; F$(4)=4$; F$(5)=5$; F$(6)=6$; and

for all n$>6,$ F$($n$)=$F$($n$-1)+$F$($n$-2)+$F$($n$-4)+$n

Do the following:

Write a divide and conquer $($recursive$)$ algorithm R$($n$)$ that calculates F$($n$)$ for any given n$>=1.$ Your algorithm also prints out how many addition operations R$($n$)$ performs $($in $$R$($n$-1)+$R$($n$-2)+$R$($n$-4)+$n$,$ there are three additions$).$

Write a dynamic programming algorithm D$($n$)$ that calculates F$($n$)$ for any given n$>=1.$ Your algorithm also prints out how many additions $(+$ operation$)$ it performs in calculating D$($n$).$

Create a table in which you tabulate the number of additions R$($n$)$ and D$($n$)$ perform for n$=5,10,15,20,25,30.$

Turn in your source codes for $1$ and $2$ above, and the result table in $3.$ You can put all of them in one file if you$$d like. Please write your programs in C$,$ C$++,$ or Java. Do not use recursion in Question $2($i$.$e$.,$ in implementing D$($n$)).$ Otherwise, penalties will apply.