How to resolve the algorithm Boustrophedon transform step by step in the ALGOL 68 programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Boustrophedon transform step by step in the ALGOL 68 programming language

Table of Contents

Problem Statement

A boustrophedon transform is a procedure which maps one sequence to another using a series of integer additions. Generally speaking, given a sequence:

(

a

0

,

a

1

,

a

2

, … )

{\displaystyle (a_{0},a_{1},a_{2},\ldots )}

, the boustrophedon transform yields another sequence:

(

b

0

,

b

1

,

b

2

, … )

{\displaystyle (b_{0},b_{1},b_{2},\ldots )}

, where

b

0

{\displaystyle b_{0}}

is likely defined equivalent to

a

0

{\displaystyle a_{0}}

. There are a few different ways to effect the transform. You may construct a boustrophedon triangle and read off the edge values, or, may use the recurrence relationship: The transformed sequence is defined by

b

n

=

T

n , n

{\displaystyle b_{n}=T_{n,n}}

(for

T

2 , 2

{\displaystyle T_{2,2}}

and greater indices). You are free to use a method most convenient for your language. If the boustrophedon transform is provided by a built-in, or easily and freely available library, it is acceptable to use that (with a pointer to where it may be obtained).

If your language supports big integers, show the first and last 20 digits, and the digit count of the 1000th element of each sequence.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Boustrophedon transform step by step in the ALGOL 68 programming language

Source code in the algol programming language

BEGIN # apply a Boustrophedon Transform to a few sequences                   #
    # returns the sequence generated by transforming s                       #
    PROC boustrophedon transform = ( []LONG INT s )[]LONG INT:
         BEGIN
            []LONG INT a = s[ AT 0 ];      # a is s with lower bound revised to 0 #
            [ 0 : UPB a, 0 : UPB a ]LONG INT t;
            t[ 0, 0 ] := a[ 0 ];
            FOR k TO UPB a DO 
                t[ k, 0 ] := a[ k ];
                FOR n TO k DO
                    t[ k, n ] := t[ k, n - 1 ] + t[ k - 1, k - n ]
                OD
            OD;
            [ 0 : UPB a ]LONG INT b;
            FOR n FROM 0 TO UPB b DO b[ n ] := t[ n, n ] OD;
            b
         END # boustrophedon transform # ;
    # prints the transformed sequence generated from a                       #
    PROC print transform = ( STRING name, []LONG INT a )VOID:
         BEGIN
            []LONG INT b = boustrophedon transform( a );
            print( ( name, " generates:", newline ) );
            FOR i FROM LWB b TO UPB b DO print( ( " ", whole( b[ i ], 0 ) ) ) OD;
            print( ( newline ) )
         END # print transform # ;
    BEGIN # test cases                                                       #
        print transform( "1, 0, 0, 0, ..."
                       , []LONG INT( 1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 )
                       );
        print transform( "1, 1, 1, 1, ..."
                       , []LONG INT( 1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1 )
                       );
        print transform( "1, -1, 1, -1, ..."
                       , []LONG INT( 1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1, -1,  1 )
                       );
        print transform( "primes"
                       , []LONG INT( 2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 )
                       );
        print transform( "fibnonacci numbers"
                       , []LONG INT( 1,  1,  2,  3,  5,  8, 13, 21, 34, 55, 89, 144, 233, 377, 610 )
                       );
        [ 0 : 14 ]LONG INT factorial;
        factorial[ 0 ] := 1;
        FOR i TO UPB factorial DO factorial[ i ] := i * factorial[ i - 1 ] OD;
        print transform( "factorial numbers",  factorial )
    END
END

  

You may also check:How to resolve the algorithm Parsing/Shunting-yard algorithm step by step in the zkl programming language
You may also check:How to resolve the algorithm Queue/Definition step by step in the Prolog programming language
You may also check:How to resolve the algorithm Quickselect algorithm step by step in the Raku programming language
You may also check:How to resolve the algorithm Menu step by step in the PHP programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the Mirah programming language