difference between fifo and lifo branch and bound in daa [closed]
I want to know the difference between first in first out and last in first out branch & bound in analysis and design of algorithm.
I want to know the difference between first in first out and last in first out branch & bound in analysis and design of algorithm.
A while back I posted on the Spigot algorithm in Pascal (and C) for calculating the first 1000 decimal places of Ο. Now converting it to Fortran is quite easy.
program piSpigot integer :: n, len integer :: i, j, k, q, x, nines, predigit integer, dimension(3500) :: a n = 1000 len = (10 * n) / 3 a = 2 nines = 0 predigit = 0 999 format(I1) do j = 1,n q = 0 do i = len,1,-1 x = 10 * a(i) + q * i a(i) = mod(x,2*i-1) q = x / (2*i-1) end do a(1) = mod(q,10) q = q / 10 if (q == 9) then nines = nines + 1 elseif (q == 10) then write(*,999,advance='no') predigit+1 do k = 1, nines write(*,999,advance='no') 0 end do predigit = 0 nines = 0 else write(*,999,advance='no') predigit predigit = q if (nines /= 0) then do k = 1,nines write(*,999,advance='no') 9 nines = 0 end do end if end if end do write(*,999,advance='no') predigit end program piSpigot
This algorithm is good, but it could be improved upon by making the array dynamic. All that really involves is reworking some code at the top of the program. In the snippet of code below, the array a
is made allocatable (Line 5), I/O is added to prompt for the number of decimal points required to be calculated, and then on Line 11 the space for a
is allocated. At the end of the program, the memory is deallocated.
program piSpigot integer :: n, len integer :: i, j, k, q, x, nines, predigit integer, dimension(:), allocatable :: a write(*,*) 'Number of decimal points? ' read(*,*) n len = (10 * n) / 3 allocate(a(len)) ... deallocate(a) end program piSpigot
The Fortran program can also be translated to Ada. Below is the Ada program. It contains some code to output the resulting value of pi to the text file piCalc1000ADA.txt
. In this code a
is a βdynamicβ array of integers, which is allocated using a declare
block. In reality a
is just of type pia
, declared at a later point in the program.
with ada.Text_IO; use Ada.Text_IO; with ada.Integer_Text_IO; use Ada.Integer_Text_IO; with ada.strings.unbounded; use ada.strings.unbounded; with ada.strings.unbounded.Text_IO; use ada.strings.unbounded.Text_IO; procedure piSpigotDYN is n, len : integer; q, x, nines, predigit : integer; type pia is array(integer range <>) of integer; infp : file_type; begin create(infp,out_file,"piCalc1000ADA.txt"); n := 1000; len := 10 * n / 3; declare a : pia(1..len); begin a := (1..len => 2); nines := 0; predigit := 0; for j in 1..n loop q := 0; for i in reverse 1..len loop x := 10 * a(i) + q * i; a(i) := x mod (2*i-1); q := x / (2*i-1); end loop; a(1) := q mod 10; q := q / 10; if q = 9 then nines := nines + 1; elsif q = 10 then put(infp,predigit+1,width=>1); for k in 1..nines loop put(infp,0,width=>1); end loop; predigit := 0; nines := 0; else put(infp,predigit,width=>1); predigit := q; if nines /= 0 then for k in 1..nines loop put(infp,9,width=>1); nines := 0; end loop; end if; end if; end loop; put(infp,predigit,width=>1); close(infp); end; end piSpigotDYN;
It might seem odd to think of a compound interest as a problem which could be solved by recursion, but it does make sense. The algorithm for calculating compound interest is of course very simple:
interest = current_balance Γ interest_rate new_balance = current_balance + interest current_balance = new_balance
Of course this calculation is done numerous times depending on how many times the interest is to be compounded. If we were to write a simple function in Ada it would look like this:
with text_io; use text_io; with ada.Integer_Text_IO; use Ada.Integer_Text_IO; with ada.Float_Text_IO; use Ada.Float_Text_IO; procedure compound is newBal, currBal, intRate, monRate : float; numMon : natural; function compound_interest(bal: float; intr: float; n: natural) return float is interest: float; newbal: float := bal; begin for i in 1..n loop interest := newbal * intr; newbal := newbal + interest; end loop; return newbal; end compound_interest; begin put("Balance ($)? "); new_line; get(currBal); skip_line; put("Interest rate (e.g. 5.3)? "); new_line; get(intRate); skip_line; put("Number of months (1-12)? "); new_line; get(numMon); skip_line; monRate := intRate / 100.0 / 12.0; newBal := compound_interest(currBal,monrate,numMon); put("The new balance is $"); put(newBal, 1, 2, 0); end compound;
Here is the program running:
Balance ($)? 1000 Interest rate (e.g. 5.3)? 5 Number of months (1-12)? 12 The new balance is $1051.16
This nonrecursive procedure is fine, but we can also solve it recursively. If we say that the balance, b
, after 0 months is the amount of the original deposit, d
, and the interest rate is r
, then we can write:
At month 0: b(0) = d At month 1 : b(1) = b(0) + b(0) * r At month 2 : b(2) = b(1) + b(1) * r ...
Then we can form a recursive definition of the form:
b(m) = b(m-1) + b(m-1) * r
Therefore we can use this to create a recursive function:
b(0) = d b(m) = b(m-1) + b(m-1) * r
Here is a recursive version of the function compound_interest()
.
function compound_interestR(bal: float; intr: float; n: natural) return float is newbal: float; begin if n = 0 then return bal; elsif n = 1 then return bal + bal * intr; else newbal := compound_interestR(bal,intr,n-1); return newbal + newbal * intr; end if; end compound_interestR;