Jan 11 15:41 1996 fig2_5.adb Page 1 -- Function Max_Subsequence_Sum is the O(N^3) algorithm in Figure 2.5 -- A short test program is provided with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Fig2_5 is type Input_Array is array( Integer range <> ) of Integer; An_Array : Input_Array( 1..8 ) := ( 4, -3, 5, -2, -1, 2, 6, -2 ); function Max_Subsequence_Sum( A: Input_Array ) return Integer is This_Sum, Max_Sum: Integer := 0; begin for I in A'range loop for J in I..A'Last loop This_Sum := 0; for K in I..J loop This_Sum := This_Sum + A( K ); end loop; if This_Sum > Max_Sum then Max_Sum := This_Sum; end if; end loop; end loop; return Max_Sum; end Max_Subsequence_Sum; begin Put( Max_Subsequence_Sum( An_Array ) ); New_Line; end Fig2_5; Jan 11 15:41 1996 fig2_6.adb Page 1 -- Function Max_Subsequence_Sum is the O(N^2) algorithm in Figure 2.6 -- A short test program is provided with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Fig2_6 is type Input_Array is array( Integer range <> ) of Integer; An_Array : Input_Array( 1..8 ) := ( 4, -3, 5, -2, -1, 2, 6, -2 ); function Max_Subsequence_Sum( A: Input_Array ) return Integer is This_Sum, Max_Sum : Integer := 0; begin for I in A'range loop This_Sum := 0; for J in I..A'Last loop This_Sum := This_Sum + A( J ); if This_Sum > Max_Sum then Max_Sum := This_Sum; end if; end loop; end loop; return Max_Sum; end Max_Subsequence_Sum; begin Put( Max_Subsequence_Sum( An_Array ) ); New_Line; end Fig2_6; Jan 11 15:42 1996 fig2_7.adb Page 1 -- Function Max_Subsequence_Sum is the O(N log N) algorithm in Figure 2.7 -- A short test program is provided -- Max3 is implemented; it returns the maximum of three integers with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Fig2_7 is type Input_Array is array( Integer range <> ) of Integer; An_Array : Input_Array( 1..8 ) := ( 4, -3, 5, -2, -1, 2, 6, -2 ); -- Return the maximum of A, B, and C function Max3( A, B, C: Integer ) return Integer is begin if A > B then if A > C then return A; else return C; end if; else if B > C then return B; else return C; end if; end if; end Max3; function Max_Subsequence_Sum( A: Input_Array ) return Integer is Max_Left_Sum, Max_Left_Border_Sum : Integer := 0; Max_Right_Sum, Max_Right_Border_Sum : Integer := 0; Left_Border_Sum, Right_Border_Sum : Integer := 0; Center : Integer := ( A'First + A'Last ) / 2; begin if A'Length = 1 then -- Base case if A( A'First ) > 0 then return A( A'First ); else return 0; end if; end if; -- Compute the maximum for each of the two halves recursively Max_Left_Sum := Max_Subsequence_Sum( A( A'First..Center ) ); Max_Right_Sum := Max_Subsequence_Sum( A( Center+1..A'Last ) ); -- Compute the maximum sum of the sequence that includes -- the last element in the first half for I in reverse A'First..Center loop Left_Border_Sum := Left_Border_Sum + A( I ); if Left_Border_Sum > Max_Left_Border_Sum then Max_Left_Border_Sum := Left_Border_Sum; Jan 11 15:42 1996 fig2_7.adb Page 2 end if; end loop; -- Compute the maximum sum of the sequence that includes -- the first element in the second half for I in Center+1..A'Last loop Right_Border_Sum := Right_Border_Sum + A( I ); if Right_Border_Sum > Max_Right_Border_Sum then Max_Right_Border_Sum := Right_Border_Sum; end if; end loop; -- Return the maximum of the three possibilities return Max3( Max_Left_Sum, Max_Right_Sum, Max_Left_Border_Sum + Max_Right_Border_Sum ); end Max_Subsequence_Sum; begin Put( Max_Subsequence_Sum( An_Array ) ); New_Line; end Fig2_7; Dec 6 15:57 1995 fig2_8.adb Page 1 -- Function Max_Subsequence_Sum is the O(N) algorithm in Figure 2.8 -- A short test program is provided with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Fig2_8 is type Input_Array is array( Integer range <> ) of Integer; An_Array : Input_Array( 1..8 ) := ( 4, -3, 5, -2, -1, 2, 6, -2 ); function Max_Subsequence_Sum( A: Input_Array ) return Integer is This_Sum, Max_Sum : Integer := 0; begin for J in A'range loop This_Sum := This_Sum + A( J ); if This_Sum > Max_Sum then Max_Sum := This_Sum; elsif This_Sum < 0 then This_Sum := 0; end if; end loop; return Max_Sum; end Max_Subsequence_Sum; begin Put( Max_Subsequence_Sum( An_Array ) ); New_Line; end Fig2_8; Dec 6 16:55 1995 fig2_9.adb Page 1 -- Simple test program for binary search with Binary_Search; with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Fig2_9 is type Input_Array is array( Integer range <> ) of Integer; An_Array : Input_Array( 1..8 ) := ( 1, 3, 5, 7, 9, 11, 13, 16 ); -- Instantiate Binary_Search for Integers function Binary_Search is new Binary_Search( Integer, "<", Input_Array ); begin for I in 0..20 loop Put( I ); Put( " " ); Put( Binary_Search( An_Array, I ) ); New_Line; end loop; end Fig2_9; Dec 6 16:54 1995 binary_search.ads Page 1 -- Generic function Binary_Search -- returns index where X is found in A -- if X is not found, A'first - 1 is returned -- Requires: a private type Element_Type, "<", -- and an array type generic type Element_Type is private; with function "<"( Left, Right: Element_Type ) return Boolean; type Array_Of_Element is array( Integer range <> ) of Element_Type; function Binary_Search( A: Array_Of_Element; X: Element_Type ) return Integer; Dec 6 16:56 1995 binary_search.adb Page 1 -- Implementation of Binary_Search function Binary_Search( A: Array_Of_Element; X: Element_Type ) return Integer is Low : Integer := A'First; High : Integer := A'Last; Mid : Integer; begin while Low <= High loop Mid := ( Low + High ) / 2; if A( Mid ) < X then Low := Mid + 1; elsif X < A( Mid ) then High := Mid - 1; else return Mid; end if; end loop; return A'First - 1; -- Not found end Binary_Search; Dec 6 17:05 1995 fig2_10.adb Page 1 -- Function Gcd computes the greatest common divisor of M and N -- It assumes that M and N are both greater than 0 -- Procedure Fig2_10 is a simple test routine with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Fig2_10 is function Gcd( M, N : Integer ) return Integer is Tmp_M : Integer := M; -- Temporaries: Tmp_N : Integer := N; -- M and N are in parameters Remainder : Integer; begin while Tmp_N > 0 loop Remainder := Tmp_M mod Tmp_N; Tmp_M := Tmp_N; Tmp_N := Remainder; end loop; return Tmp_M; end Gcd; begin Put( Gcd( 45, 20 ) ); New_Line; Put( Gcd( 49, 30 ) ); New_Line; end Fig2_10; Dec 6 17:07 1995 fig2_11.adb Page 1 -- Function Pow computes X**N -- It works with type Super_Long_Integer, which -- for simplicity is simply Integers in this code -- Procedure Fig2_11 is a simple test routine with Ada.Text_IO; use Ada.Text_IO; with Ada.Integer_Text_IO; use Ada.Integer_Text_IO; procedure Fig2_11 is subtype Super_Long_Integer is Integer; -- Return true if X is even; false otherwise function Even( X: Integer ) return Boolean is begin return X mod 2 = 0; end Even; -- Compute X**N -- Pow is used in place of "**" for simplicity. function Pow( X, N : Super_Long_Integer ) return Super_Long_Integer is begin if N = 0 then return 1; elsif N = 1 then return X; elsif Even( N ) then return Pow( X * X, N / 2 ); else return Pow( X * X, N / 2 ) * X; end if; end Pow; begin Put( Pow( 2, 20 ) ); New_Line; end Fig2_11;